Phase kickback - The trick behind the Bernstein-Vazirani algorithm

It may look like a magic trick at first, that even though all the guess qubits are just controlling the CNOT gates, their value actually changed. But it's actually not. Let's see, how this worked.

For this, we will just focus on two qubits. The upper one is a guess and the lower one is the output qubit. Now we need to differentiate two cases: Either, there is no CNOT gate connecting the two qubits or there is a CNOT gate. In the former case, we will not see the guess qubit change:

Measurements

Applying the Hadamard gate H twice in direct order will lead to the original value. So the guess qubit will end up in state \(\ket{0}\) again.

Let's look at the latter case, where there is a CNOT between the two qubits:

Measurements

In this case, the state of the control qubit is affected while the state of the target qubit is unchanged. This means, by preparing our target qubit carefully, we can cause a change in the control qubit. This phenomenon is called phase kickback as the phase of the target qubit is kicked up to the control qubit.

For the curious: To further investigate this, we can also write it in the ket notation. Let's start with putting both qubits in a superposition by applying H gates to qubit 1 (in state \(\ket{0}\)) and qubit 2 (in state \(\ket{1}\)), which will lead us to the following state: $$ \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) \frac{1}{\sqrt{2}}(\ket{0} - \ket{1}) = $$ $$ \frac{1}{2}\ket{00} - \frac{1}{2}\ket{01} + \frac{1}{2}\ket{10} - \frac{1}{2}\ket{11}$$ Applying a CNOT Gate will change the phase, where the first qubit is one. $$ \frac{1}{2}\ket{00} - \frac{1}{2}\ket{01} - \frac{1}{2}\ket{10} + \frac{1}{2}\ket{11}$$ $$ = \frac{1}{\sqrt{2}}(\ket{0} - \ket{1}) \frac{1}{\sqrt{2}}(\ket{0} - \ket{1})$$ Applying a Hadamard gate H to each qubit again, will bring both qubits to state \(\ket{1}\).
We recommend performing the multiplications yourself to deepen your understanding.

Phase kickback is just one of the computational tricks used to gain an advantage over classical computers. But it illustrates how big the speed up can be when compared to traditional way of solving problems with a computer. Instead of 4 tries we just needed 1.

Find out about how this algorithm performs on a real quantum computer in the module Challenges ahead.