In Bernstein-Vazirani Algorithm, the role of the last qubit (here, $q_7$) is simply to dish out negative relative phases to each qubit representing a $1$ through the use of $\text{CNOT}$s.

But if we apply only $|0\rangle$ to the last qubit, we are getting the secret number $50\%$ of the time. Why are we getting this result as there is no phase kickback here, IMO?

Applying $H$-gate on $q_0$ and $\text{CNOT}$ on the $q_7$ will put both qubits in entanglement. So how $q_0$ get into $|-\rangle$ so that applying $H$ gate again will give us $1$ as output.

enter image description here


2 Answers 2


I have already answered a similar question here.

Your observation is correct. If the ancilla qubit is $|0\rangle$ and not $|-\rangle$ we will get a correct result 50% of the time. To see this, consider what follows below.

Let $f(x) = c \cdot x$ where $c$ is a secret $n$-bit string and $\cdot$ is a dot product mod 2. Also, assume we have $n+1$ qubits. The correct BV algorithm is given by the following computation:

$$\color{green}{H^{\otimes n}U_fH^{\otimes n}|0\rangle^{\otimes n}|-\rangle = |c\rangle |-\rangle.}$$

If we measure the first $n$ qubits, we recover the correct $n$-bit ket $|c\rangle$ with certainty. Note that the last $(n+1)$th qubit is $|-\rangle$.

Now, let's look at the BV algorithm where $(n+1)$th bit is $|0\rangle$.

As it was stated in my previous answer, we first rewrite $(n+1)$th qubit $|0\rangle$ in the $X$ basis: $$|0\rangle = \frac{1}{\sqrt{2}}|+\rangle + \frac{1}{\sqrt{2}} |-\rangle.$$ Then, the BV algorithm where the last $(n+1)$th qubit is $|0\rangle$ is:

\begin{align*} &H^{\otimes n}U_fH^{\otimes n}|0\rangle^{\otimes n}|0\rangle \\ &= H^{\otimes n}U_fH^{\otimes n}|0\rangle^{\otimes n} \left(\frac{1}{\sqrt{2}}|+\rangle + \frac{1}{\sqrt{2}} |-\rangle \right)\\ \tag{1} &= \frac{1}{\sqrt{2}} \color{red}{H^{\otimes n}U_fH^{\otimes n}|0\rangle^{\otimes n}|+\rangle} + \frac{1}{\sqrt{2}} \color{green}{H^{\otimes n}U_fH^{\otimes n}|0\rangle^{\otimes n}|-\rangle}. \end{align*}

From (1) it is clear we end up with the correct (green) BV algorithm with the probability $\left|\frac{1}{\sqrt{2}}\right|^2 = \frac{1}{2}$. The term highlighted in red, if measured, always outputs the $n$-bit string $|0\ldots0\rangle$ because: \begin{align*} H^{\otimes n}U_fH^{\otimes n}|0\rangle^{\otimes n}|+\rangle &= H^{\otimes n} U_f\sum_{x=0}^{2^n-1}|x\rangle |+\rangle \\ &= H^{\otimes n} \sum_{x=0}^{2^n-1}U_f|x\rangle |+\rangle\\ &= H^{\otimes n} \sum_{x=0}^{2^n-1}|x\rangle |+\rangle \\ &= |0\ldots 0 \rangle |+\rangle. \end{align*}

Hence, we can rewrite (1) as: $$\frac{1}{\sqrt{2}} \color{red}{H^{\otimes n}U_fH^{\otimes n}|0\rangle^{\otimes n}|+\rangle} + \frac{1}{\sqrt{2}} \color{green}{H^{\otimes n}U_fH^{\otimes n}|0\rangle^{\otimes n}|-\rangle} = \frac{1}{\sqrt{2}} \color{red}{|0\ldots 0\rangle |+\rangle} + \frac{1}{\sqrt{2}}\color{green}{|c\rangle |-\rangle}.$$

Therefore, we get the $n$-bit ket $|0\ldots 0 \rangle$ the other 50% of the time. You verified this experimentally, i.e. you got $0000000$ circa 50% of the time.

Intuitively speaking, having $|0\rangle$ as the last qubit gives an algorithm which produces a uniform superposition of the kets $|0\ldots 0\rangle$ and $|c\rangle$. Thus we get a correct output only half of the time. I believe you could also have the last qubit set to $|1\rangle$ and get a 50% chance of getting the correct $c$.


Consider this simpler example:

enter image description here

We have the states: $$|000\rangle \xrightarrow{H^{\otimes 2}\otimes I} \frac{1}{2}(|000\rangle + |001\rangle + |010\rangle + |011\rangle) \rightarrow \frac{1}{2}(|000\rangle +|001\rangle + |110\rangle + |111\rangle) \rightarrow \frac{1}2{}(|000\rangle+|101\rangle+|110\rangle +|011\rangle)\xrightarrow{H^{\otimes 2}\otimes I}\frac{1}{2}(|000\rangle+|011\rangle+|100\rangle-|111\rangle)$$ which explains why when we measure the first two qubits we will either get $00$ or $11$, each with equal probability. The reason why this is happening is that we entangle $q_2$ with both $q_0$ and $q_1$ (so neither of the first two qubits gets into the state $|-\rangle$ explicitly) and at the same time the state of the target qubit changes. That's why in the implementation of the Berstein-Vazirani algorithm we set the ancilla qubit to the state $|-\rangle$ so as to leave it unchanged throughout the execution of the circuit and induce the phase kickback.

  • $\begingroup$ here(circuit attached in question) even if we don't put ancilla in |−⟩ , still we are getting the secret number half of the time that is without any phase kickback (IMO), so just wanted to understand how is this weird outcome... :) $\endgroup$ Commented Jul 23, 2022 at 1:32
  • $\begingroup$ is it like beacuse q0 is '1' half of the time thus q7 is also '1' half of the time but event then q7 is not an eigenvector of operation (IMO) so phase kickback is not induced? Please correct if I am wrong... $\endgroup$ Commented Jul 23, 2022 at 1:39
  • $\begingroup$ are you sure that all 3 qubits are entangled in your answer's circuit? $\endgroup$ Commented Jul 23, 2022 at 1:44
  • $\begingroup$ @VinaySharma I'm not really sure about the intuitive explanation (if any) but the math seems to work out. Phase kickback is indeed not induced here but that doesn't mean we will never measure the actual answer. $\endgroup$ Commented Jul 23, 2022 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.