Quantum Computing ist faszinierend, kontraintuitiv, mehr als 30 Jahre alt und dennoch irgendwie futuristisch. Was es nicht ist, ist Zauberei.

Die für eine breite Öffentlichkeit bestimmten Artikel über Quantencomputer tragen fast alle Überschriften von Sensationsmeldungen die ich sehr irreführend finde. Sie bringen die Leute dazu zu denken "das ist nur etwas für Wissenschaftler, mir reicht wenn ich es vielleicht eines Tages benutzen kann". Aber Quantencomputer müssen nicht mit kontroversen, provokativen Aussagen irgendwie mystifiziert werden. Sie sind auch nüchtern betrachtet sehr beeindruckend. 

Sicher, das Thema Quantum Computing ist wirklich nichts für Otto Normalverbraucher oder Lieschen Müller, aber ein interessierter Leser kann durchaus mehr verstehen, als manche Medien zu glauben scheinen, und sich einen guten Eindruck davon verschaffen, worum es bei der Sache eigentlich geht.

Wenn Sie bis jetzt noch nie etwas von Quantencomputern gehört haben, ist dieser Artikel wahrscheinlich nicht der beste Einstieg. Auf der anderen Seite habe ich noch nirgendwo eine gute Einführung gefunden, also können Sie der Sache auch gleich hier und jetzt eine Chance geben.

Die absoluten Grundlagen ganz kurz zusammengefasst

Um über einen ganzen neuen Typ von Computer nachzudenken, müssen wir zuerst das allgemeine Konzept "Computer" von den tatsächlichen Maschinen trennen, die wir jeden Tag benutzen. Das Gleiche gilt für den Begriff "Bit". Von nun an bezeichnen wir die uns vertrauten Maschinen als “klassische Computer” und deren Bits als “klassische Bits” und verwenden eine etwas abstraktere Definition für die beiden ursprünglichen Begriffe: 

Ein Bit ist eine Entität, auf die man eine Operation anwenden kann, die "Lesen" (oder "Messen") genannt wird. Die Ausgabe der Leseoperation ist binär, was heißt, sie hat genau zwei mögliche Werte (meistens 0 und 1).

Ein Logikgatter ist ein Operator den man auf ein oder mehrere Bits anwenden kann, um ihre interne Eigenschaften zu verändern und kombinieren. Was für interne Eigenschaften vorhanden sind, kommt darauf an, welche Art Bits benutzt werden.

Ein Computer ist eine Maschine, die Bits und Logikgatter verwendet, um Algorithmen auszuführen. Will heißen, dass ein Computer (sobald er für einen bestimmten Algorithmus programmiert wurde) eine binäre Sequenz (eine Reihe von 0 und 1) als Eingabe erhält und diese benutzt um eine Menge von Bits vorzubereiten, die dann eine Reihe von Logikgattern durchlaufen, wo sie verändert und kombiniert werden. Am Ende werden die Bits gelesen und die resultierende binäre Sequenz wird vom Computer als Ausgabe des Algorithmus zurückgegeben. Das reduziert den Computer nun zwar auf seinen Prozessor, aber das ist genau der interessante Teil hier.

Stellen Sie sich nun vor, wir würden jetzt den Kern eines Atoms als “Bit” verwenden und die Richtung des Kern-Spins messen, um das Bit zu "lesen" (wodurch wir entweder "Spin-Up" oder "Spin-Down" als Ausgabe erhalten). 

Das wäre ein Beispiel für ein sogenanntes Qubit (oder "Qbit", "QBit", "Q-Bit" usw.). Das "bit" in "Qubit" ist nach wie vor die Abkürzung für "binary digit", was sich auf die Art der Ausgabe der Messung bezieht (zwei mögliche Werte), während das "Qu" in "Qubit" eine Abkürzung für "quantum" ist, was darauf hinweist, dass das Konzept auf dem Verhalten bestimmter Quantensysteme (wie dem Atomkern) basiert. Ein Computer, der Qubits als Bits verwendet, wird Quantencomputer genannt.

Mehr als nur neue Hardware

Jedes Mal, wenn neue Materialien und Technologien die klassischen Computer schneller und leistungsfähiger machen, wird die Mathematik, um sie zu entwerfen und zu kontrollieren, ein bischen komplizierter. Tief im inneren aber ist die mathematische Grundlage, die die Computeralgorithmen von heute antreibt, im Wesentlichen immer noch die von Alan Turing in den 30er und 40er Jahren entwickelte Theorie.

Quantum Computing hingegen verändert das Spiel komplett. Das Konzept an sich sagt nichts über die Geschwindigkeit der Berechnungen oder die Größe der Maschinen aus. Tatsächlich sind die experimentellen Quantencomputer, die wir heute haben, gigantische Monster, die nur davon träumen können, einmal im herkömmlichen Sinne so schnell zu werden wie Ihr Smart-Toaster. Allerdings ist die Mathematik, die hinter dem Quantencomputer steht, völlig anders als beim klassischen Computer und erlaubt komplett neue Ansätze, um Probleme zu lösen, anstatt nur die alten Ansätze zu beschleunigen.

Nun, zur Sache!

(Nicht ganz so) klassische Computer

Bisher wurden wir dadurch verwöhnt, dass die Computer, die wir heute benutzen, uns erlauben, das Bit in der Maschine und das in einem Algorithmus als dasselbe zu betrachten. Mit anderen Worten, die physikalische Implementierung und das theoretische Konzept sind sich so ähnlich, dass die Trennung der beiden selten von Bedeutung ist. Dasselbe gilt für den Zustand eines Bits (d.h. die Werte seiner internen Eigenschaften) und die Ausgabe der Leseoperation. Wir stellen uns ein Bit wie etwas vor, das 0 oder 1 ist, und es zu lesen bedeutet nur, es "anzuschauen", um herauszufinden, welchen der beiden Werte es denn nun hat. Wie wir sehen werden, zwingen uns Qubits und ihre Fremdheit dazu, genau dieses Konzept aus einer neuen Perspektive zu betrachten.

Im Prozessor in Ihrem Laptop, Smartphone, Tablet, etc. werden Bits als Spannungsdifferenzen an elektrischen Leitungen implementiert. Wir können eine “hohe” Spannung an einer Leitung erreichen, indem wir eines ihrer Enden an eine Spannungsquelle anschließen und eine “niedrige” Spannung, indem wir sie wieder davon trennen. 

Der Vorgang des Verbindens und Trennens erfolgt jedoch nicht sofort und die Spannungsdifferenz auf der Leitung springt auch nicht einfach zwischen Minimum und Maximum. Wenn die Leitung angeschlossen wird, steigt die Spannung allmählich von einem niedrigen Wert über einen kontinuierlichen Bereich bis zu einem hohen Wert an. Der niedrige Wert ist nicht immer derselbe, aber es gibt einen Bereich von niedrigen Werten, die wir als 0 akzeptieren. Der hohe Wert ist auch nicht immer derselbe, aber es gibt einen Bereich von hohen Werten, die wir als 1 akzeptieren. Zwischen den Bereichen der akzeptablen Spannungen für 0 und für 1 gibt es aber eine Grauzone, in der Messungen nicht genau genug wären.

Nun könnten wir eine Art von Bit erfinden, das dem Verhalten dieser Leitungen ähnlicher ist und es Wibit (für “Wire-Bit”) nennen. 

Ein Wibit hätte einen Zustand, der einer Zahl in dem Intervall $\left[0,V_{\max }\right]$ entspricht. Um nun ein Wibit zu "lesen" oder "messen" legen wir zwei spezielle Werte $V_{\mathrm{low}}$ und $V_{\mathrm{high}}$ fest für die gilt $0\le V_{\mathrm{low}}<V_{\mathrm{high}}\le V_{\max }$ und dann bilden wir alle Werte in $\left[0,V_{\mathrm{low}}\right]$ auf 0 ab, alle Werte in $\left[V_{\mathrm{high}},V_{\max }\right]$ auf 1 und alle Werte in $\left(V_{\mathrm{low}},V_{\mathrm{high}}\right)$ würden zufällig auf 0 oder 1 abgebildet, wobei höhere Werte wahrscheinlicher eine 1, Niedrigere wahrscheinlicher eine 0 ergeben würden.

Doch als ob das nicht kompliziert genug wäre, kommt nun noch die Tatsache ins Spiel, dass wenn wir zwei Leitungen sehr dicht nebeneinander auf einem Chip platzieren, diese sich gegenseitig zu beeinflussen beginnen. 

Ein Strom durch eine Leitung erzeugt ein elektromagnetisches Feld, das wiederum einen Strom in der anderen Leitung erzeugen kann. Um dies in unseren Wibits zu berücksichtigen, müssten wir konzeptionell die Möglichkeit hinzufügen, dass zwei oder mehr Wibits irgendwie miteinander verbunden sind. 

Leider haben wir in der Realität in Wibits nie einen Nutzen gefunden und stattdessen ihre Komplexität sogar als unseren Feind betrachtet. Aus diesem Grund werden zahllose Ressourcen investiert, damit sich die elektrischen Leitungen weniger wie Wibits und mehr wie klassische Bits verhalten. Wir kontrollieren sorgfältig den Abstand zwischen Leitungen, um das "Übersprechen" zu reduzieren und wählen sorgfältig die Momente, in denen die Spannung gemessen wird, um sicherzustellen, dass sie nicht im grauen Bereich liegt. 

Bei Qubits stellte sich nun heraus, dass wir deren Eigenheiten zu unserem Vorteil ausnutzen können, weshalb wir sie bereitwillig akzeptiert haben.

Weder 0 noch 1 noch beides gleichzeitig...

Es ist schwierig, eine Einführung in das Thema Quantencomputer zu finden, die nicht eine Variation des folgenden Satzes enthält: "im Gegensatz zu einem klassischen Bit, das nur 0 oder 1 sein kann, kann ein Qubit 0 oder 1 oder beides zugleich sein!". Sie sehen, selbst in diesem Text steht nun eine Version drin.

Was hat es damit auf sich? Ein Qubit hat unter Bestimmten Voraussetzungen eine Eigenschaft die man seinen “Zustand” nennt. Dieser Zustand ist... nun ja, ein Punkt auf der Einheitskugel eines zweidimensionalen komplexen Hilbert-Raums.

Okay, der Raum und die Einheitskugel sind beide ziemlich schwer vorstellbar und sogar unmöglich zu zeichnen (daher hier auch keine Grafik). Und lassen Sie sich nicht vom Wort "Kugel" täuschen: Diese Kugel sieht gar nicht wie ein gewöhnlicher Ball aus. Also müssen wir das Konzept für Nicht-Mathematiker tatsächlich vereinfachen, aber es gibt trotzdem keinen Grund so weit wie "0 und 1 gleichzeitig" zu gehen!

Für eine weniger radikale Vereinfachung, ersetzen wir oben einfach das Wort "komplex" durch "real". Die Einheitssphäre eines zweidimensionalen realen Hilbert-Raums ist nämlich nur ein gewöhnlicher Kreis, so dass wir eine Analogie zwischen unserem vereinfachten Qubit und einem Kompass machen können, indem wir den Zustand des Qubits mit der Richtung vergleichen, in die die Nadel zeigt. 

Wir wählen uns jetzt zwei spezielle Zustände, sagen wir "Osten" und "Süden" (sie müssen nur 90 Grad auseinander liegen), die durch die Messoperation auf 0 bzw. auf 1 abgebildet werden. Das Ergebnis der Messoperation ist zufällig, aber der Zustand des Qubits bestimmt wie die Wahrscheinlichkeit 0 und die Wahrscheinlichkeit 1 zu messen ist. 

Mit anderen Worten, wenn wir das Qubit messen, werfen wir im Grunde eine Münze, aber eine die nicht unbedingt gleich häufig auf jede Seite landet. Welche Seite bevorzugt wird und wie uneben die Wahrscheinlichkeiten sind, entscheidet die Nadel des Kompasses. Wenn die Nadel nach Osten zeigt, gibt die nächste Messung definitiv eine 0 aus. Wenn sie fast nach Osten zeigt, aber nicht ganz (wie im Bild oben), wird sie mit einer hohen Wahrscheinlichkeit eine 0 eventuell aber doch eine 1 ausgeben. Wenn die Nadel genau nach Südosten zeigt wird die Ausgabe die Hälfte der Zeit 0 und die Hälfte der Zeit 1 sein.

Zwei Aspekten sind insbesondere zu beachten: Erstens, ergeben Sätze wie "der Zustand des Qubits ist 0" oder "der Zustand des Qubits ist 1" überhaupt keinen Sinn. Der Zustand eines Qubits ist eine "Himmelsrichtung" und keine Binärziffer. Zweitens, da Zustände Vektoren sind (mit 2 Koordinaten in unserer vereinfachten Analogie), können sie u.a. durch Addition kombiniert werden, sodass alle möglichen Zustände als Kombinationen aus den beiden ausgewählten Richtungen Osten und Süden dargestellt werden können. Wir schreiben, zum Beispiel:

Wer will, kann jetzt gern einen Thread starten, um zu diskutieren, ob Südosten "Süden und Osten zur gleichen Zeit" oder "weder Süden noch Osten" ist. Bei dieser Diskussion ginge es aber wohl weniger um die Informatik als vielmehr um die Sprache. Das Wichtige zu verstehen ist, dass der Zustand eines Qubits ein Punkt auf einem Kreis ist (nur eben kein Kreis, den man zeichnen kann).

Anmerkung: Wenn Sie schon mal etwas über Quantum Computing gelesen haben, werden Sie gemerkt haben, dass ich das Wort Superposition bisher vermieden habe. In diesem Kontext ist Superposition nur eine alternative Bezeichnung für "Kombination". Genauer gesagt, "lineare Kombination". Gerade haben wir zum Beispiel Nordwesten als lineare Kombination (d.h., als Superposition) von Osten und Süden dargestellt. Dieses Wort ist sehr wahrscheinlich eine Quelle von Verwirrung beim Thema Quantenphysik. Noch schlimmer ist die Verwendung des Wortes "Messung" wenn es um Quantenzustände geht. Man sollte immer vorsichtig mit der physikalischen Terminologie umgehen und die Konzepte nicht zu stark mit den Bedeutungen verbinden, die die entsprechende Worte in der Alltagssprache annehmen.

Was macht den Quantencomputer denn nun so mächtig?

Der Zustand eines Qubits ist also viel mehr als nur ein "Bit" an Information. Es werden 4 reelle Zahlen $a$, $b$, $c$, und $d$ (die zusammen 2 komplexe Zahlen darstellen) benötigt, um ihn zu beschreiben. Diese können jeden beliebigen Wert haben, solange sie folgende Bedingung erfüllen:

$$a^2+b^2+c^2+d^2=1$$ $$\mathrm{(Normalisierungsbedingung)}$$

Sind Quantencomputer deshalb so mächtig? Nein, sorry, dass ich hier enttäuschen muß. Zuallererst besteht das Problem, dass der Messvorgang ja am Ende immer noch nur eine 0 oder 1 ausgibt, so dass wir dabei eine Menge an Information verlieren. 

Zweitens, selbst wenn wir irgendwie den vollen Zustand eines Qubits ermitteln könnten (was wir nicht können), sind 4 reelle Zahlen pro Qubit wirklich nicht viel. Wir stellen reelle Zahlen inzwischen mit 64 klassischen Bits dar und das ist normalerweise mehr als genug für unsere Bedürfnisse. Darüber hinaus impliziert die Normalisierungsbedingung, dass wir nur den Wert von 3 der 4 Zahlen plus dem Vorzeichen des letzten kennen müssen, also würden wir nur $64x3+1=193$ klassische Bits benötigen, um jedes Qubit zu codieren.

Dies mag eine große Zahl sein, aber es ist eine Konstante und würde daher die Anzahl der klassischen Bits, die benötigt werden, um einen Quantencomputer zu simulieren in eine lineare Beziehung zu den verwendeten Qubits stellen. Nicht genug, um die Welt auf den Kopf zu stellen.

Was ist mit der Tatsache, dass der Messvorgang zufällig ist, während es das Lesen eines klassischen Bits nicht ist? Ist das das Besondere? Nein, leider ebenfalls nicht. Das Simulieren von Zufälligkeit ist mit klassischen Computern nicht schwer. Natürlich ist es kein echter Zufall aber es ist wieder nah genug dran für unsere Bedürfnisse. 

Erinnern Sie sich, wie ich schrieb, dass Qubits nicht immer einen Zustand haben? Wenn sie den nämlich immer hätten, wären Quantencomputer längst als teure, langsamere Versionen von klassischen Computern verworfen worden. 

Wenn Sie einen Quantencomputer bauen und die Qubits im Register vom Rest der Welt isolieren, hat die Sammlung von Qubits im Register immer einen Zustand. Aber Untermengen (einschließlich einzelner Qubits) haben nur Zustände, wenn sie nicht mit den anderen "verschränkt" sind. Falls Sie jetzt darauf warten, dass ich definiere, was Verschränkung bedeutet, haben Sie es gerade verpasst. 

Die Definition besagt, dass eine Anzahl von Qubits verschränkt ist, wenn keine Untermenge von ihnen einen eigenen Zustand hat. Das bedeutet in der Praxis, dass das Messen jedes einzelnen Qubits nacheinander keine Folge von unabhängigen Operationen ist. Jede Messung hat einen Einfluss auf die Ausgabe aller weiteren Messungen.

Warum ist das so interessant? Weil die Zustände einer verschränkten Sammlung von Qubits eine viel höhere Freiheitsgradanzahl als die Zustände einer unverschränkten Sammlung mit gleich vielen Qubits hat.

Die Anzahl der nötigen Parameter um den Zustand mehrerer Qubits zu beschreiben ist nicht proportional zur Anzahl der Qubits sondern zur Anzahl der möglichen Messergebnisse. Für ein einzelnes Qubit sind die möglichen Ergebnisse 0 und 1, damit brauchen wir 2 komplexe Zahlen um seinen Zustand zu beschreiben (erinnern Sie sich an den zweidimensionalen komplexen Hilbert-Raum?). Für 3 Qubits sind die möglichen Ausgaben 000, 001, 010, 011, 100, 101, 110 und 111. Man braucht also 8 komplexe Zahlen für die Beschreibung des Zustands. Für $n$ Qubits benötigen wir $2^n$ komplexe Zahlen um den Zustand der Sammlung zu beschreiben. 

Wenn eine Sammlung von $n$ Qubits hingegen völlig unverschränkt ist (das heißt, jedes der Qubits hat seinen eigenen Zustand), kann man den Zustand der Sammlung als Kombination dieser individuellen Zustände darstellen, sodass man nur $2n$ komplexe Zahlen braucht. Selbst bei niedrigen Werten wie $n=50$ ist der Unterschied bereits enorm zwischen $2n=100$ und $2^n=\mathrm{1\text{'}125\text{'}899\text{'}906\text{'}842\text{'}624}$.

Weiterhin kommt die zusätzliche Freiheit nicht nur von der Anzahl an Parametern. Verschränkung kann selbst bei $n=2$ (sodass $2n=2^n$) neue Zustände ermöglichen: Stellen Sie sich vor, Sie haben 2 Qubits $a$ und $b$ und diese sind nicht verschränkt, haben also jeweils ihren eigenen Zustand. Qubit $a$ hat eine Wahrscheinlichkeit $P_a\left(0\right)$ eine 0 zu messen und $P_a\left(1\right)=1-P_a\left(0\right)$ für eine 1. Genauso definieren wir $P_b\left(0\right)$ and $P_b\left(1\right)$. 

Wie ist nun die Wahrscheinlichkeit für jede mögliche Ausgabe des Paares? Einfach:

$$\begin{array}{l}{P}_{ab}\left(00\right)=P_a\left(0\right)x{P}_b\left(0\right)\\ P_{ab}\left(01\right)=P_a\left(0\right)x{P}_b\left(1\right)\\ P_{ab}\left(10\right)=P_a\left(1\right)x{P}_b\left(0\right)\\ P_{ab}\left(11\right)=P_a\left(1\right)x{P}_b\left(1\right)\end{array}$$

Beachten Sie, das wenn $P_{ab}\left(00\right)=0$ ist, ist mindestens $P_{ab}\left(01\right)$ oder $P_{ab}\left(10\right)$ auch 0, egal wie man die Zustände für $a$ und $b$ wählt.

Wenn nun $a$ und $b$ verschränkt sind, wird der Zustand des Paares $ab$ von 4 unabhängigen komplexen Zahlen beschrieben, eine für jede mögliche Ausgabe und kann damit einfach so gesetzt werden, dass:

$$\begin{array}{l}{P}_{ab}\left(00\right)=0\\ P_{ab}\left(01\right)=1/2\\ P_{ab}\left(10\right)=1/2\\ P_{ab}\left(11\right)=0\end{array}$$

In anderen Worten können wir $a$ und $b$ so verschränken, dass für jedes von ihnen das Messergebnis eine gleiche Wahrscheinlichkeit hat 0 oder 1 zu sein. Wenn wir aber beide messen, erhalten wir garantiert zwei unterschiedliche Werte. Das zeigt wie die Verschränkung die Menge der möglichen Zustände für mehrere Qubits erweitern kann.

Wie man keine Werte einer Funktion berechnet

Eine weitere sehr vereinfachte Erklärung zu Quantencomputern lautet in der Regel: 

"Wenn Sie die Werte einer Funktion $f$ mit einem klassischen Computer berechnen möchten, haben Sie keine andere Wahl, als jeden Wert einzeln zu berechnen. Ein Quantencomputer kann alle Werte auf einmal berechnen!“

Das ist nun etwas schwerer zu erklären, aber ich werde mein Bestes geben. Den Ursprung hat das Ganze in einer Routine, die häufig in Quantencomputer-Algorithmen als ersten Schritt verwendet wird. Wir nennen sie jetzt mal den "Alle Werte”-Trick. Folgendes ist eine kurze Beschreibung davon, ohne in die mathematische Theorie hinein zu gehen:

Nehmen wir an, eine Funktion $f$ benötigt 3 binäre Ziffern als Eingabe und gibt 2 binäre Ziffern aus. Das Erste was wir brauchen ist ein Logikgatter, welches $f$ entspricht aber auf Zustände von Qubits angewendet wird (und es kann je nach Komplexität schwierig sein, so ein Gatter zu bauen aber wir nehmen an, wir haben es geschafft).  Wir bereiten den Quantencomputer mit 5 Qubits vor: 3 entsprechen den Eingabeparametern der Funktion, die anderen 2 den Ausgabeparametern. Zuerst laufen die 3 Eingabe-Qubits durch sogenannte Hadamard-Gatter, die dafür sorgen dass alle möglichen Messergebnisse für diese 3 Qubits genau gleich wahrscheinlich sind (in Kompass-Terminologie: alle 3 Nadeln werden nach Südosten gerichtet). Danach laufen alle 5 Qubits durch das Gatter, das $f$ entspricht, was dafür sorgt, dass die Eingabe- mit den Ausgabe-Qubits verschränkt werden. Fertig. 

Das Ergebnis sind 5 verschränkte Qubits mit folgender Eigenschaft: Werden alle 5 Qubits gemessen und ergibt die Messung die binäre Sequenz $abcde$, so haben wir die Garantie, dass $f\left(abc\right)=de$ gilt.

Es ist übrigens egal in welcher Reihenfolge die Qubits gemessen werden. Man kann sogar zuerst die Ausgabe-Qubits messen (mit Ergebnis $de$) und danach die Eingabe-Qubits messen (mit Ergebnis $abc$) und auch so hat man die Garantie, dass $f\left(abc\right)=de$ gilt.

Dieser Trick bewirkt, dass die gesamte Funktion $f$ in die Verschränkung der Qubits einbezogen wird. Hier wird mit "gesamte Funktion" tatsächlich die komplette Abbildung gemeint, also die Sammlung aller Paare von Eingabewert und entsprechendem Ausgabewert.

Es sollte nicht allzu überraschend sein, dass das möglich ist. Schließlich besteht der Zustand der 5 Qubits aus mehreren reellen Zahlen und eine einzige reelle Zahl würde schon ausreichen um alle Ein- und Ausgabe-Wertepaare von $f$ darzustellen. Denken Sie daran, dass die Dezimaldarstellung einer reellen Zahl beliebig viele Ziffern enthalten kann (sogar unendlich viele) und wir können diese Ziffern benutzen um Information zu kodieren, genauso wie wir Dateien mit Binärziffern auf unseren Festplatten kodieren.

Es ist sehr beeindruckend, dass all diese Informationen so schnell encodiert wurden, indem die Qubits durch ein einzelnes Gatter geschickt wurden. Nun existiert dieses spezielle Gatter normalerweise nur theoretisch und wird in der Praxis durch eine Reihe von kleineren, einfacheren Gattern ersetzt. Dadurch hängt die Anzahl der Operationen, die auf die Qubits angewendet werden letztlich doch von der Komplexität der Funktion $f$ ab.

Haben wir nun jeden Wert von $f$ berechnet, als wir die Funktion in der Verschränkung der Qubits codiert haben? Oder haben wir in dem Moment gar keinen Wert von $f$ berechnet, und später genau einen Wert berechnet, als wir die Messung vorgenommen haben? Das ist wohl wieder eine Frage für einen Foren-Thread.

Obwohl die Ansicht "jeden Wert berechnet" technisch nicht falsch ist, ist sie sehr irreführend. Es lässt die Sache so erscheinen, als ob der Zweck des Tricks wäre, überhaupt Werte von $f$ zu erhalten und das ist eine sehr naive Herangehensweise.

Das Berechnen von Werten einer Funktion unter Verwendung dieses Ansatzes wäre völlig sinnlos, da sie mit einem klassischen Computer und mit viel weniger Aufwand leicht simuliert werden könnte:

Um die Messung der ersten 3 Qubits zu simulieren, erstelle zufällig eine binäre Sequenz $abc$. Um die Messung der 2 verbleibenden Qubits zu simulieren, berechne $f\left(abc\right)$.

Der "Alle Werte"-Trick ergibt nur Sinn, wenn direkt danach keine Messung folgt. Zumindest keine Messung aller Qubits. Ich versuche dies unten durch ein Beispiel zu erklären.

Die richtigen Fragen stellen

Der berühmte Algorithmus, den Peter Shor in den 90er Jahren geschrieben hat (der die RSA-Verschlüsselung durch Quantum Computing bricht), ist eines der besten Beispiele dafür, wie und wofür ein Quantencomputer verwendet werden kann. 

Im Kern des Problems haben wir wieder eine Funktion $f$, nämlich modulare Potenzierung. Das heißt, wir haben eine Zahl $b$ (ein Teil einer geheimen Nachricht, codiert und verschlüsselt) und eine Zahl $n$ (der öffentliche RSA-Schlüssel) und $f$ wird durch

$$f\left(x\right)=b^{x}modn$$

definiert. Der Algorithmus beginnt mit dem "Alle Werte"-Trick, aber wir führen noch keine Messung aller Qubits vor. Eine vollständige Messung würde lediglich irgendeinen Wert von $f$ ergeben, und das hätten wir auch mit einem klassischen Computer hinbekommen. Stattdessen manipulieren wir geschickt weiter den Zustand der Qubits (und damit die Wahrscheinlichkeiten der verschiedenen Messergebnisse).

Das Endziel ist die Periode von $f$ zu entdecken, d.h. die kleinste positive Zahl $r$, für die gilt $f\left(x+r\right)=f\left(x\right)$ für jedes beliebige $x$. Mit der Periode $r$ kann man dann die geheime Nachricht entschlüsseln, auch ohne den öffentlichen Schlüssel zu faktorisieren. (Wenn Sie wissen wollen, wie das geht, schauen Sie sich diesen Artikel an, den wir als Einführung in die RSA-Verschlüsselung geschrieben haben.)

Nach der Anwendung des "Alle Werte"-Tricks, messen wir nur die Ausgabe-Qubits und bekommen dadurch irgendeinen Wert $y$, der uns eigentlich gar nicht interessiert. Nun, wie wir oben beschrieben haben, wenn wir jetzt die restlichen Qubits messen würden (werden wir aber noch nicht), würden wir garantiert einen Wert $x$ bekommen für den gilt $f\left(x\right)=y$.

Wie viele solche Werte $x$ gibt es denn? Erstmal zählen wir wie viele Ergebnisse für die Messoperation (der restlichen Qubits) überhaupt möglich wären ohne die Bedingung, dass sie auf $y$ abgebildet werden müssen. Das ist einfach 2 hoch "Anzahl der Eingabe-Qubits", und diese Zahl nennen wir ab jetzt $I$ (wie "Input"). Da aus jedem Interval von $r$ Eingabewerte genau ein Wert die Bedingung $f\left(x\right)=y$ erfüllt, stellen wir fest, dass es insgesamt $I/r$ Werte gibt, die jetzt noch mögliche Messergebnisse sind. Anders gesagt, von den Parametern im Zustand der restlichen Qubits sind genau $I/r$ ungleich 0.

Durch die Verwendung weiterer Logikgatter, bringen wir die Qubits zu einem neuen Zustand wo die neuen Parameter Kombinationen aus den alten Parametern sind und die Messergebnisse die am Wahrscheinlichsten sind sind die, die sehr nah an Vielfachen von $I/r$ liegen. Jetzt messen wir endlich die Eingabe-Qubits.

Wir sind noch Meilen weit vom Schluss -- man braucht noch eine Menge schwierige Mathematik um die Periode aus dem Messergebnis zu berechnen -- aber der Quantencomputer hat seine Aufgabe erledigt. Ab hier können wir mit einem klassichen Computer weitermachen.

Wie ich schon sagte, Quantum Computing ist nicht für jeden. Aber vor der phantastisch-mysteriösen Fassade, sollte man sich verabschieden. Quantum Computing ist auch ganz nüchtern betrachtet schwierig genug.