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.

In 15 min zum ersten Quantenprogramm

Obwohl Google kürzlich das Erreichen der sogenannten "Quantum Supremacy" verkündet hat, ist der Hype um den Quantencomputer aktuell noch eher überschaubar. Das mag damit zu tun haben, das zwar annähernd jeder IT-Interessierte bereits etwas über Quantencomputer gehört oder gelesen hat, wirklich verstanden haben es jedoch vermutlich die wenigsten. Vom Erstellen von Quantenprogrammen gar nicht zu reden. Wie einfach zumindest der grundlegende Einstieg in die Quatenprogrammierung in rund 10 min gelingen kann, möchte ich in diesem Post beschreiben.

Zugegeben, auch mir ging es bis vor kurzem so: mir war nicht klar, wie sich mit Qubits (Quantenbits), die 0 und 1 zur gleichen Zeit sein können, Probleme effizient lösen lassen sollen. Die meisten Erklärungen, die sich online zu diesem Thema finden, sind nämlich entweder zu oberflächlich oder gleich so mathematisch, dass es keinen Spaß mehr macht, sie nachzuvollziehen. Zudem gibt es noch recht wenige deutschsprachige Ressourcen, die vielleicht gerade bei diesem komplexen Gebiet den Einstieg erleichtern könnten (wobei natürlich jeder Informatiker auch mit Englisch klarkommen sollte).

Daher möchte ich mit diesem Blog-Post (und evtl. noch folgenden) meine persönliche Reise beim Entdecken der "Quantenrechnerei" dokumentieren und hoffentlich dem ein oder anderen Leser ein wenig das Verständnis und den Einstieg erleichtern. Hier bewegen wir uns nämlich tatsächlich im "Neuland" und können erleben, wie die Grundlagen einer Technologie geschaffen werden, die die Möglichkeiten von Computern grundlegend verändern könnte.

Als sehr hilfreich habe ich dabei empfunden, mit Quantencomputern tatsächlich zu programmieren. Moment... mit echten Quantencomputern? Sind die innendrin nicht "colder than outer space" und entsprechend super-teuer? Ja, das sind sie, und noch gibt es leider keine Quantencomputer für den Hobbykeller, doch wer ein wenig seinen Pioniergeist ausleben möchte, kann das tatsächlich: bspw. IBM bietet online einen Zugriff auf seine Quanten-Hardware an.

Das ist, wie es dieser Youtuber so schön formuliert, ein wenig so, als würde uns die NASA einen ihrer Mars-Rover steuern lassen. (Falls es letztere Idee je gegeben haben sollte, sie wurde vermutlich wegen dieses Vorfalls wieder verworfen. ;-) Daher empfiehlt es sich natürlich, einen entsprechenden Simulator (wie Qiskit) zu installieren (wie in diesem Video erklärt), um Quantenprogramme lokal testen zu können und die echten Quantencomputer nur mit sinnvollen Programmen zu behelligen.

Grundlagen

Zum Einstieg in die Quantenprogrammierung, seien einige Hintergründe in aller Kürze erläutert. Wie bereits erwähnt, verwenden Quantencomputer sogenannte Qubits, die entweder 0 oder 1 oder auch beides zugleich sein können. Dieser letztgenannte Zustand nennt sich Superposition und ist einer der Gründe, der Quantencomputer leistungsfähiger als herkömmliche Computer machen soll. 0 bzw. 1 werden bei Qubits übrigens wie folgt in der sogenannten Dirac-Noation geschrieben: |0> bzw. |1>. Das hat damit zu tun, dass die Zustände von Qubits üblicherweise Vektoren sind, muss aber hier erst einmal nicht im Detail interessieren.

Als Qubits kommen in der Praxis verschiedene Arten von Elementarteilchen in Frage, also etwa Elektronen, Protonen oder auch Photonen. Werden bspw. Elektronen verwendet, können diese über Mikrowellen manipuliert und ausgelesen werden. Einen guten ersten Eindruck dazu vermittelt z.B. dieses Video aus Australien.

Wird ein Qubit in Superposition versetzt, also im Fall eines Elektrons mit Mikrowellen "angeregt", befindet es sich gleichzeitig sowohl im Zustand 0 als auch im Zustand 1. Sobald es ausgelesen wird, muss es sich allerdings für einen Wert entscheiden: wir erinnern uns an die bedauernswerte Katze des Herrn Schrödinger (die übrigens kürzlich tot aufgefunden wurde ;-), mit deren Hilfe sich dieses physikalische Phänomen veranschaulichen lässt. Oder auch an den Doppelspaltversuch im Physik-Unterricht, wo selbst einzelne Photonen durch beide Spalten gleichzeitig zu gehen scheinen und mit sich selbst wechselwirken können.

Wie sich auf Basis einer solchen Überlagerung programmieren lassen soll, war (und ist z.T. noch immer) für mich das erste große Fragezeichen beim Verständnis der Quantencomputer.

Grafische Programmierung in der Cloud

Doch Moment, könnten wir uns diese Unbestimmt zum Einstieg nicht einfach für etwas zunutze machen, was herkömmliche Computer nicht besonders gut beherrschen? Nämlich gerade das Erzeugen von Zufallszahlen? Mit dem folgenden Zufallszahlengenerator bei der IBM Quantum Experience möchte ich nun endlich ein erstes Quantenprogramm, und wie es auf echter Quanten-Hardware ausgeführt werden kann, beschreiben.

Nach Anmeldung und Login bei IBM klicken wir dazu auf "Create a circuit", also das Erstellen eines Quantenschaltkreises, und sollten etwa folgenden Bildschirm zu sehen bekommen:

Der rechte untere Bereich zeigt uns die aktuell zur Verfügung stehenden Qubits sowie darunter eine klassische Datenleitung, die zum Auslesen der Qubits verwendet werden kann. Die bunten Kästchen darüber sind die Quantengatter (quantum gates) mit deren Hilfe die Qubits manipuliert werden können. Und ja, hier ist echter Pioniergeist gefragt, Quantencomputer werden aktuell tatsächlich auf dem Bit- oder besser gesagt Qubit-Level programmiert.

Quantengatter sind im Prinzip sehr ähnlich zu herkömmlichen Gattern, die (wir erinnern uns) zur Verarbeitung von herkömmlichen Bits verwendet werden. Allerdings gibt es einige der gewohnten Gatter (wie AND oder OR) in der Quantenwelt erst einmal nicht. Das hat damit zu tun, dass in der Quantenwelt Qubits nicht einfach so kopiert werden könne und alle elementaren Operationen eindeutig umkehrbar sein müssen. Das bedeutet, dass aus dem Ergebnis die Eingabe wieder herstellbar sein muss, was bspw. bei OR, wo sowohl 10, 01 und auch 11 das Ergebnis 1 liefern, offensichtlich nicht der Fall ist.

Doch zurück zu unserem Zufallszahlen-Generator: für diesen müssen wir mindestens ein Quantenbit in Superposition versetzen, das geht ganz einfach z.B. mit dem sogenannten Hadamard- oder kurz auch H-Gate, das im Bild an erster Stelle der blauen Kästchen steht. Dieses ziehen wir per Drag-und-Drop auf die Linie neben einem der Qubits:

Im Bild wird also das erste Qubit q[0], das sich anfangs im Zustand |0> befindet, in Superposition versetzt (und ist nun sowohl |0> als auch |1>). Nun können wir noch das letzte schwarze Kästchen zum Messen bzw. Auslesen des Qubits auf die Linie setzten und haben damit quasi unser "Quanten-Hello-World" erstellt:

Das Messgatter legt den Wert des Quantenbits auf das entsprechende klassische Bit, dabei wird, wie bereits gesagt, die Superposition des Qubits zerstört, es muss sich fest für einen Wert (also entweder 0 oder 1) "entscheiden". Die in den Schaltkreis gesetzten Gatter können übrigens angeklickt und dann ggf. mit dem kleinen "x" in der rechten oberen Ecke wieder gelöscht werden.

Um nun unseren "Quanten-Hello-World-Moment" zu erleben (das dauert bis hierhin übrigens keine 10 min) , müssen wir noch oben rechts im Bild zunächst auf "Unsaved changes" und danach auf "Run" klicken. Sodann können wir aus einem Simulator sowie einer Reihe echter Quantencomputer das gewünschte Backend zum Ausführen wählen und angeben, wie oft das Programm ausgeführt werden soll. Da sich mit nur einer Ausführung keine Zufallsverteilung wird feststellen lassen, sollten wir hier mindestens 1024 auswählen. Einige Augenblicke später erscheint dann im unteren Fensterbereich ein Link zum Ergebnis der Berechnung:

Den Trommelwirbel müssen wir uns leider selbst dazu denken (oder hier abspielen): nach einem Klick auf den gezeigten Link finden wir im unteren Bereich der folgenden Seite in etwa das folgende Bild:

Dieses zeigt uns an, bei wie vielen der 1024 Aufrufe das Qubit q[0] zufällig mit einer 0 und bei wie vielen es mit einer 1 ausgelesen wurde. Im Bild siegt die 1 mit einem knappen Vorsprung gegenüber der 0.

Um bspw. eine Zufallszahl zwischen 0 und 7 generieren zu können, erweitern wir das Programm leicht wie folgt...

... und führen es 4096 mal auf einem der echten IBM-Quantencomputer (z.B. ibmq_ourense) aus. Das liefert uns die folgende Verteilung von Zufallszahlen (Trommelwirbel nicht vergessen):

Dabei wird q[0] ganz wie in einer normalen Darstellung eines Bit-Strings auf das am weitesten rechts stehende Bit übertragen, nicht wie die obige Anordnung der Measurement-Gates implizieren könnte, auf das am weitesten links stehende.

Mit einem Klick auf das kleine Code-Symbol am linken Rand (das </>) können wir uns übrigens auch den zugehörigen QASM-Code (Quantenassembler-Code) in Textform anzeigen lassen.

Dieser sollte mehr oder weniger selbsterklärend sein, zusammenfassend sei hier aber noch einmal der Programmaufbau beschrieben: wir legen ein Quantenregister mit 5 Qubits sowie ein klassisches Register mit 5 Bits an, versetzen die ersten drei Qubits mit dem Hadamard-Gate in Superposition und erzwingen durch jeweils eine Messung eine Festlegung der Qubits auf |0> oder |1>.

Lokal programmieren

Wer, wie im bereits genannten Video beschrieben, Qiskit installiert hat, kann ein identisches Programm auch ganz einfach lokal anlegen und ausführen: dazu müssen wir ein neues Jupyter Notebook für Python3 erstellen und folgenden Python-Code eingeben:

  from qiskit import *

  qr = QuantumRegister(3)
  cr = ClassicalRegister(3)

  circuit = QuantumCircuit(qr, cr)

  circuit.h(qr[0])
  circuit.h(qr[1])
  circuit.h(qr[2])

  circuit.measure(qr, cr)
 

  circuit.draw(output='mpl')

Ein Druck auf Shift + Return führt diesen Code-Schnipsel aus und zeichnet die drei Qubits sowie das klassische Register ähnlich zum vorherigen Bild aus dem Browser:

Ohne den Parameter beim draw-Aufruf erscheint übrigens eine ebenfalls brauchbare "ASCII-Art"-Darstellung des Quantenschaltkreises. Um das Quantenprogramm selbst ausführen zu können, wird auch lokal wieder ein Simulator benötigt, dessen Ergebnisse wir mit print ausgeben können:

  simulator = Aer.get_backend('qasm_simulator')

  result = execute(circuit, backend = simulator, shots = 1024).result()

  print(result.get_counts()) 

Dies ergibt bei meinem Durchlauf folgende Ausgabe:

  {'110': 120, '000': 131, '101': 114, '111': 133, 

   '010': 120, '011': 137, '100': 130, '001': 139}

Auch ein Plotten der Ergebnisse analog zur Cloud-Variante ist mit einem weiteren Import problemlos möglich...

  from qiskit.tools.visualization import plot_histogram
  plot_histogram(result.get_counts())

...  und ergibt das folgende Bild:

Qiskit to Quantum Computer

Abschließend sei noch erläutert, wie der Aufruf des echten Quantencomputers bei IBM von Qiskit aus funktioniert (Voraussetzung ist das Hinterlegen eines Access-Tokens in Qiskit wie im Video von vorhin gezeigt), es erfordert an für sich nur den Austausch des Backends gegen einen echten Quantencomputer, wie der folgende Code-Schnipsel illustriert:

  from qiskit.tools.monitor import job_monitor

  IBMQ.load_account()
  provider = IBMQ.get_provider('ibm-q')

  qcomputer = provider.get_backend('ibmq_ourense')

  job = execute(circuit, backend = qcomputer, shots = 1024)
  job_monitor(job)
  result = job.result()

  plot_histogram(result.get_counts())

Der Job-Monitor wird hier genutzt, um den Status der Job-Verarbeitung angezeigt bekommen zu können, da die Verarbeitung je nach Auslastung des gewählten Quantencomputers einige Augenblicke in Anspruch nehmen kann. Hat schließlich alles erfolgreich geklappt, erhalten wir abermals ein bereits vertraut wirkendes Histogramm:

Dies gezeigten Beispiele sollten reichen, um einen ersten Eindruck und hoffentlich ein besseres initiales Verständnis der Quantenrechnerei zu bekommen, auch wenn das Generieren von Zufallszahlen noch kein wirklich hilfreicher Algorithmus war. Immerhin haben wir in aller Kürze einen Quantencomputer bei IBM grafisch "programmiert" und auch lokal über Qiskit Quantencode erstellt, der sich zudem leicht in die IBM-Cloud hochladen und dort ausführen lässt.

Ich hoffe, Sie haben auch ein wenig Geschmack an der "Zukunft der Computer" gefunden, ich jedenfalls werde versuchen, weiter in diese spannende Welt einzutauchen und, so es meine Zeit zulässt, auch noch weitere Artikel zu posten. Ich freue mich auch, Sie wieder als interessierten Leser begrüßen zu dürfen.

Weitere Ressourcen:

• Qiskit Textbook 
• Qiskit Docs
• Qiskit API Docs (mögliche Bausteine eines Quantenschaltkreises)