Time Complexity Analysis - DJ

Initialization

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

$$|\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 $H$ on each qubit including the ancillary qubit. The state of our system will now become:

$$|\psi_1\rangle = H^{\otimes n+1}|\psi_0\rangle$$

$$|\psi_1\rangle = \frac{1} {\sqrt{2^{n}}}( |00...0\rangle + ... + |11...1\rangle) \otimes \frac{1} {\sqrt{2}}(|0\rangle - |1\rangle)$$

$$|\psi_1\rangle = \frac{1} {\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|0\rangle - |1\rangle)$$ ...