Search⌘ K
AI Features
Home
Courses
The Fundamentals of Quantum Computing

Time Complexity Analysis - DJ

Understand how the Deutsch-Jozsa algorithm initializes qubits, creates superpositions, applies quantum oracles, and uses phase kickback to determine if a function is constant or balanced. Learn how this quantum algorithm achieves a constant time complexity of O(1), querying the function only once.

We'll cover the following...

Initialization

Our qubits are initialized to the ∣0⟩|0\rangle state and we also have an extra qubit, ancilla, that is initialized to the ∣1⟩|1\rangle state using an XX gate. The current quantum state of our qubits can be represented as follows:

∣ψ0⟩=∣00...0⟩⊗∣1⟩=∣0⟩⊗n⊗∣1⟩|\psi_0\rangle = |00...0\rangle \otimes|1\rangle= |0\rangle^{\otimes n} \otimes|1\rangle

The equal superposition

As we’ve covered so far, the next step of the algorithm is to create an equal superposition state using all our qubits by applying the Hadamard gate HH on each qubit including the ancillary qubit. The state of our system will now become:

∣ψ1⟩=H⊗n+1∣ψ0⟩|\psi_1\rangle = H^{\otimes n+1}|\psi_0\rangle

∣ψ1⟩=12n(∣00...0⟩+...+∣11...1⟩)⊗12(∣0⟩−∣1⟩) |\psi_1\rangle = \frac{1} {\sqrt{2^{n}}}( |00...0\rangle + ... + |11...1\rangle) \otimes \frac{1} {\sqrt{2}}(|0\rangle - |1\rangle)

∣ψ1⟩=12n+1∑x=02n−1∣x⟩(∣0⟩−∣1⟩) |\psi_1\rangle = \frac{1} {\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|0\rangle - |1\rangle) ...