Quantum code vividly explained: the Bernstein-Vazirani Algorithm

A brief preliminary remark: Since I have hardly found any material that approaches this algorithm from an intuitive rather than a mathematical perspective, I decided to write this post in English, as I thought it might be useful for a larger audience. If there is sufficient demand I can translate it to German later. And if happen to understand German and are an absolute beginner, you might read this post first.

On my quest to quantum computing, I approached the Bernstein-Vazirani Algorithm, which is about finding a secret bit string encoded in a box, as a first example of a "quantum supreme" algorithm. The idea is that we are not allowed to look inside the box and have to guess the number. If the box would give us simply a yes or no answer for our guesses, we would need as many attempts as there are possible combinations of bits in the worst case, which for n bits this would be 2ⁿ.

For clarification, let us consider an example where there are three bits and the secrect string is 110. We can just try to blindly guess it as follows:

 000 = 110? -> no

 001 = 110? -> no

 010 = 110? -> no

... until on the 7th try:

 110 = 110? -> yes

For the quantum algorithm example, the box is supposed to be a little more supportive as it does a bitwise AND of the secret and our guess, however, it does not simply return the result of this AND operation, but merely a single bit, which gives us the result of the AND operation summed up, with an implicit modulo 2, of course. 

Let us clarify this with another example:

 000 AND 110 = 000: 0 + 0 + 0 -> 0

 001 AND 110 = 000: 0 + 0 + 0 -> 0

...

 111 AND 110 = 110: 1 + 1 + 0 -> 0 (here we can see the modulo 2 at work)

Since the box each time just returns one bit, we now can find out the secret in 3 (or in the general case in n) attempts by just setting one bit after the other to 1 and accumulating the output of the box:

 100 AND 110 = 1 -> first bit must be 1 

 010 AND 110 = 1 -> middle bit must be 1

 001 AND 110 = 0 -> last bit must be 0

First Quantum Circuit
How would we build a circuit like this for a quantum computer? Unfortuntately, I find most explanations on the web either quite complicated and mathematical or so superficial that they just demonstrate the algorithm, but give no intuition how it actually works in a quantum computer. Hence, to begin with, I would first like to implement a classical solution on a quantum computer.

This is relatively simple as we can wire the secret string via CNOT gates to our output bit, measure the output bit, and try setting one after the other input bit to 1. The circuit may look as follows on the IBM Quantum Experience (in this case I tried setting q[2] to one):

 

Obviously (when you are fine with the basics of this notation), the result should be |1> in case of the above example, because q[2], which is set to |1>  by the X gate, triggers just one flip from |0> to |1> for q[3]:

How does it work? I think that should be easy to grasp. Everytime when there is a |1> in the secret string, we wire the according bit to the output bit. In this case, the output bit gets flipped every time when there is an actual one |1> on one of the input bits.

This gives us the desired effect of the secret box. I told you it was simple. However, we still have to do n attempts in order to find out the correct solution for the secret.

Quantum Supremacy

How can the quantum computer do better? Well, you probably have guessed it by now, we need to use superposition in order to do try all possible combinations at once and then "cheat" a bit and take a glance on all the input bits again to get the desired output after one shot.  
(This is the point where I still wonder why we are not allowed to do this in the classic case as well? just take the result of the whole AND operation?)

Starting from the circuit we had before, this is also quite simple as we would just put our input bits into superposition with Hadamard gates like so...

... and "sandwhich" them in order to reverse the superposition effect. And, of course, we also measure them afterwards:

However, this alone does not do the trick (completely). Since we are using superposition, it only delivers a correct result in about 50% of all attempts, which is of course not very helpful for just one shot. The following image illustrates that the success rate can become even worse on a real device due to the various possible errors.

A quick side note to the thoughtful reader: this should make you suspicious as the target of the CNOT gates is q[3] and not q[0], q[1], and q[2]. This is exactly the place where the quantum magic kicks in as I will explain shortly.

Fortunately, it turns out that we actually can do better than this and retrieve the result in one shot. We just need to set our output bit (usually called ancilla in this context) to |1> and bring it into superposition as well:

A quick peak into the simulator's results underlines this claim:

And even the real device delivers a pretty clear picture this time:

This is the moment where most explanations that I have found on the Web so far (and that motivated me to explain it in a more vivid way) usually drift off into linear algebra for an explanation. And as a quantum of solace to all you computer programmers who does not use this on a daily basis: You are not alone. (Although the math is actually not too bad once one understood the effects of quantum physics. It turns out, even a 17 year old girl can understand it, regadless of the math, her post is nicely readable and has a similar line of argument like mine.)

So, how does it work?

Well, how does it work? Apparently through some "quantum magic" as I hinted upon above and I will try to break it down as good as I can: First of all, we need to learn about something that is called entanglement and accept it. Entanglement means that we can have two elementary particles that are in superposition (remember: they are in |0> and |1> at the same time) entangled with each other, move them far apart from each other then, measure one of them, and instantly see the other's state being determined as well.

And if you just cannot believe me, it has been experimentally proven that this happens really instanteneously and hence "faster than light". Unfortunately, we cannot transmit any information with this "mechanism". Entanglement by the way is basically that thing that was called "spooky action at a distance" by Einstein and made him say that "god doesn't throw dice" when he digged deeper into it. I particularly like Bohr's reply to Einstein: "Stop telling god what to do!" :-) Over there at Youtube is a nice video where Philip Ball explains this phenomenon, just in case you are interested to learn more about it.

Let's get back to our quantum business, how would this help us in building a quantum computer? Well, basically, the CNOT gate with a control bit in superposition creates entanglement and this is used to get the result into our quantum circuit from above. Remember, this is exactly what we have built there: qubits in superposition connected by CNOT gates.

As I understand it, in the Bernstein-Vazirani algorithm (and many others) the target qubit (q[3] in our case) creates something like a feedback effect (called the phase kickback) on the control qubit(s), i.e. on q[1] and q[2] in our example. Let's look at the circuit again to avoid the need for scrolling around:

Although this entanglement does not change the actual value of q[1] and q[2] (as they are in superposition), it influences the pase of their wave function (I hope, I phrased this correctly as a non-physicist), which eventually forces q[1] and q[2] to collapse to a 1 as soon as they are sent through the second Hadamard gate and measured.

Examining and visualizing Kickback

We can more easily see this when we simply reduce the circuit to one control bit, which always will end up as 1 after we have run the program:

As this is probably as surprising to you as it was to me, I played around with this in Qiskit a bit more, in order to get a visual feedback for what is going on with the help of the so-called Bloch sphere. Very briefly, a Bloch sphere is a visual interpretation of a qubit. The following image shows two qubits, the left one is in |0>, which vividly is "spin down" and the right quibit is in |1>, which apparently means "spin up".

Here is the minimum code to create this image with Qiskit in a Jupyter notebook, just seven lines:

 from qiskit import *
 from qiskit.visualization import plot_bloch_multivector

 circuit = QuantumCircuit(2,2)
 circuit.x(1)

 statevec_simulator = Aer.get_backend("statevector_simulator")
 statevec = execute(circuit, backend=statevec_simulator).result().get_statevector()
 plot_bloch_multivector(statevec)

Now let's see what happens when we put these qubits into superposition using circuit.h(0)and circuit.h(1) on them:

We can clearly see that both of them are now in a state between |0> and |1> as they have been rotated around the y axis. However, the first qubit has a positive x value now, while the second one has a negative value. (Rotate your screen counterclockwise if you find it hard to see this.)

And now (drum roll) let us try out what happens when we visualize the previous simple circuit with the phase kickback on a Bloch sphere. First, we completely rebuild it in Qiskit (don't forget the two imports from above if you want to follow along):

 circuit = QuantumCircuit(2,2)

 circuit.x(1)
 circuit.h(0)
 circuit.h(1)
 circuit.barrier()

 circuit.cx(0,1)
 circuit.barrier()

 circuit.h(0)
 circuit.h(1)

 circuit.draw(output='mpl')

Then, let's take a snapshot of our two qubits before each of the two barriers. The first one of course looks familiar and is not very exiting:

However, the second one is interesting, as it illustrates how the phase (i.e. the sign on the x axis) of our control qubit (on the left) has changed through the kickback from the target qubit:

If we now apply Hadamard gates to both qubits and measure, of course, both qubits will yield a 1.

This approach of playing around with the Bernstein Vazirani algorithm (inspired by this little video series) helped me to develop a vivid intuition how it might work in a real quantum computer. I hope you were able to follow along and maybe you might want to leave a thumbs comment up in this case.

Finally, a disclaimer, I am "just" a (rather practical) computer scientist and neither a mathematician nor a physicist, so if you spot any errors or have any ideas how to improve the presentation of the post, please get in touch and let me know.

After having this written, I discovered another nice video that explains Qiskit with the Bernstein-Vazirani algorithm in a quite similar fashion.