Sagen Sie bei einem Treffen von Informatikern die Worte „Quantenüberlegenheit“, und die Augen werden wahrscheinlich rollen. Der Satz bezieht sich auf die Idee, dass Quantencomputer bald eine Schwelle überschreiten werden, an der sie relativ einfach Aufgaben ausführen können, die für klassische Computer äußerst schwierig sind. Bis vor kurzem galt für diese Aufgaben nur eine geringe Verwendung in der Praxis, daher rollt das Auge.
Aber jetzt, da der Quantenprozessor von Google angeblich nahe daran ist, dieses Ziel zu erreichen, könnte sich die bevorstehende Quantenüberlegenheit schließlich als wichtige Anwendung herausstellen: die Erzeugung reiner Zufälligkeit.
Zufälligkeit ist entscheidend für fast alles, was wir mit unserer Computer- und Kommunikationsinfrastruktur tun. Insbesondere werden damit Daten verschlüsselt und alles vor weltlichen Gesprächen, Finanztransaktionen und Staatsgeheimnissen geschützt.
Echte, überprüfbare Zufälligkeit - denken Sie an die Eigenschaft einer Folge von Zahlen, die es unmöglich macht, die nächste Zahl in der Folge vorherzusagen - ist äußerst schwer zu finden.
Das könnte sich ändern, wenn Quantencomputer ihre Überlegenheit demonstrieren. Diese ersten Aufgaben, die ursprünglich nur die Leistungsfähigkeit der Technologie demonstrieren sollten, könnten auch echte, zertifizierte Zufälligkeit erzeugen. "Wir freuen uns sehr darüber", sagte John Martinis, ein Physiker an der University of California in Santa Barbara, der die Quantencomputerbemühungen von Google leitet. "Wir hoffen, dass dies die erste Anwendung eines Quantencomputers ist."
Zufälligkeit und Entropie
Zufälligkeit und Quantentheorie gehören zusammen wie Donner und Blitz. In beiden Fällen ist der erstere eine unvermeidliche Folge des letzteren. In der Quantenwelt wird oft gesagt, dass sich Systeme in einer Kombination von Zuständen befinden - in einer sogenannten „Überlagerung“. Wenn Sie das System messen, wird es in nur einen dieser Zustände „kollabieren“. Und während die Quantentheorie es Ihnen ermöglicht, Wahrscheinlichkeiten für das zu berechnen, was Sie bei Ihrer Messung finden, ist das jeweilige Ergebnis grundsätzlich zufällig.
Physiker haben diese Verbindung genutzt, um Zufallszahlengeneratoren zu erstellen. Diese beruhen alle auf Messungen einer Art Quantenüberlagerung. Und obwohl diese Systeme für die Zufallsbedürfnisse der meisten Menschen mehr als ausreichend sind, kann es schwierig sein, mit ihnen zu arbeiten. Darüber hinaus ist es äußerst schwierig, einem Skeptiker zu beweisen, dass diese Zufallszahlengeneratoren wirklich zufällig sind. Und schließlich erfordern einige der effektivsten Methoden zur Erzeugung überprüfbarer Zufälligkeiten aufwändige Setups mit mehreren Geräten, die durch große Entfernungen voneinander getrennt sind.
Ein kürzlich vorgestellter Vorschlag, wie man Zufälligkeiten aus einem einzelnen Gerät - einem Quantencomputer - herausholt, nutzt eine sogenannte Abtastaufgabe, die zu den ersten Tests der Quantenüberlegenheit gehören wird. Stellen Sie sich vor, Sie erhalten eine Kiste mit Kacheln, um die Aufgabe zu verstehen. Auf jede Kachel sind einige Einsen und Nullen eingeätzt - 000, 010, 101 und so weiter.
Wenn es nur drei Bits gibt, gibt es acht mögliche Optionen. Es können jedoch mehrere Kopien jeder beschrifteten Kachel in der Schachtel sein. Es können 50 Kacheln mit der Bezeichnung 010 und 25 mit der Bezeichnung 001 vorhanden sein. Diese Verteilung der Kacheln bestimmt die Wahrscheinlichkeit, dass Sie eine bestimmte Kachel zufällig herausziehen. In diesem Fall ziehen Sie eine Kachel mit der Bezeichnung 010 mit doppelter Wahrscheinlichkeit heraus als eine Kachel mit der Bezeichnung 001.
ERFAHREN SIE MEHR
Der WIRED-Leitfaden für Quantum Computing
Eine Stichprobenaufgabe beinhaltet einen Computeralgorithmus, der das Äquivalent dazu hat, in eine Kiste mit einer bestimmten Verteilung von Kacheln zu greifen und eine davon zufällig zu extrahieren. Je höher die für eine Kachel in der Verteilung angegebene Wahrscheinlichkeit ist, desto wahrscheinlicher ist es, dass der Algorithmus diese Kachel ausgibt.
Natürlich greift ein Algorithmus nicht in eine wörtliche Tasche und zieht Kacheln heraus. Stattdessen wird zufällig eine Binärzahl ausgegeben, die beispielsweise 50 Bit lang ist, nachdem eine Verteilung angegeben wurde, die die gewünschte Wahrscheinlichkeit für jede mögliche 50-Bit-Ausgabezeichenfolge angibt.
Bei einem klassischen Computer wird die Aufgabe exponentiell schwieriger, wenn die Anzahl der Bits in der Zeichenfolge größer wird. Für einen Quantencomputer ist jedoch zu erwarten, dass die Aufgabe relativ einfach bleibt, unabhängig davon, ob es sich um fünf Bit oder 50 Bit handelt.
Der Quantencomputer startet mit all seinen Quantenbits - Qubits - in einem bestimmten Zustand. Angenommen, sie beginnen alle bei 0. Genau wie klassische Computer mit sogenannten Logikgattern auf klassische Bits einwirken, manipulieren Quantencomputer Qubits mit dem Quantenäquivalent, den sogenannten Quantengattern.
Aber Quantentore können Qubits in seltsame Zustände versetzen. Zum Beispiel kann eine Art von Gatter ein Qubit, das mit einem Anfangswert von 0 beginnt, in eine Überlagerung von 0 und 1 versetzen. Wenn Sie dann den Zustand des Qubits messen würden, würde es mit gleicher Wahrscheinlichkeit zufällig in 0 oder 1 kollabieren.
Noch seltsamer ist, dass Quantengatter, die auf zwei oder mehr Qubits gleichzeitig einwirken, dazu führen können, dass sich die Qubits "verwickeln". In diesem Fall werden die Zustände der Qubits miteinander verflochten, so dass die Qubits nur mit einem einzigen Quantenzustand beschrieben werden können.
Wenn Sie eine Reihe von Quantentoren zusammenstellen, und diese dann auf eine Reihe von Qubits in einer bestimmten Reihenfolge einwirken lassen, haben Sie eine Quantenschaltung erstellt. In unserem Fall können Sie zur zufälligen Ausgabe einer 50-Bit-Zeichenfolge eine Quantenschaltung erstellen, die 50 Qubits zusammen in eine Überlagerung von Zuständen setzt, die die Verteilung erfasst, die Sie neu erstellen möchten.
Wenn die Qubits gemessen werden, wird die gesamte Überlagerung zufällig zu einer 50-Bit-Zeichenfolge reduziert. Die Wahrscheinlichkeit, dass es zu einer bestimmten Zeichenfolge zusammenbricht, wird durch die Verteilung bestimmt, die von der Quantenschaltung angegeben wird. Das Messen der Qubits entspricht dem Greifen mit verbundenen Augen in die Schachtel und dem zufälligen Abtasten einer Zeichenfolge aus der Verteilung.
Wie kommen wir zu Zufallszahlen? Entscheidend ist, dass die vom Quantencomputer abgetastete 50-Bit-Zeichenfolge viel Entropie, ein Maß für Unordnung oder Unvorhersehbarkeit und damit Zufälligkeit aufweist. "Dies könnte tatsächlich eine große Sache sein", sagte Scott Aaronson, ein Informatiker an der Universität von Texas, Austin, der sich das neue Protokoll ausgedacht hatte. "Nicht, weil es die wichtigste Anwendung von Quantencomputern ist - ich denke, es ist weit davon entfernt -, sondern weil es wahrscheinlich die erste Anwendung von Quantencomputern ist, deren Implementierung technisch machbar sein wird."
Aaronsons Protokoll zur Erzeugung von Zufälligkeiten ist ziemlich einfach. Ein klassischer Computer sammelt zunächst ein paar zufällige Daten aus einer vertrauenswürdigen Quelle und generiert anhand dieser Zufälligkeit die Beschreibung einer Quantenschaltung. Die Zufallsbits bestimmen die Arten von Quantentoren und die Reihenfolge, in der sie auf die Qubits einwirken sollen. Der klassische Computer sendet die Beschreibung an den Quantencomputer, der die Quantenschaltung implementiert, die Qubits misst und die 50-Bit-Ausgangsbitfolge zurücksendet. Dabei hat es zufällig aus der von der Schaltung vorgegebenen Verteilung abgetastet.
Wiederholen Sie den Vorgang jetzt immer wieder, z. B. zehnmal für jeden Quantenschaltkreis. Der klassische Computer verwendet statistische Tests, um sicherzustellen, dass die Ausgabe-Strings viel Entropie aufweisen. Aaronson hat zum Teil in einer Arbeit mit Lijie Chen und zum Teil in einer noch zu veröffentlichenden Arbeit gezeigt, dass unter bestimmten plausiblen Annahmen, dass solche Probleme rechenintensiv sind, kein klassischer Computer eine solche Entropie annähernd in der Zeit erzeugen kann, die ein Quantencomputer benötigt Zufallsstichprobe aus einer Verteilung. Nach den Überprüfungen fügt der klassische Computer alle 50-Bit-Ausgabezeichenfolgen zusammen und führt sie einem bekannten klassischen Algorithmus zu. "Es entsteht eine lange Saite, die nahezu zufällig ist", sagte Aaronson.
Die Quantenfalle
Das Aaronson-Protokoll eignet sich am besten für Quantencomputer mit etwa 50 bis 100 Qubits. Wenn die Anzahl der Qubits in einem Quantencomputer diese Schwelle überschreitet, ist es selbst für klassische Supercomputer rechnerisch nicht mehr möglich, das Protokoll zu verwenden. Hier kommt ein weiteres Schema zur Erzeugung nachprüfbarer Zufälligkeit mit Quantencomputern ins Spiel. Es verwendet eine vorhandene mathematische Technik mit einem verbotenen Namen: eine klauenfreie Funktion für die Falltür. "Es klingt viel schlimmer als es ist", sagte Umesh Vazirani, ein Informatiker an der University of California in Berkeley, der die neue Strategie zusammen mit Zvika Brakerski, Paul Christiano, Urmila Mahadev und Thomas Vidick entwickelte.
Stellen Sie sich noch einmal eine Schachtel vor. Anstatt eine Zeichenfolge einzugeben und zu extrahieren, geben Sie diesmal eine n-Bit-Zeichenfolge ein, nennen sie x und geben eine weitere n-Bit-Zeichenfolge aus. Die Box ordnet irgendwie eine Eingabezeichenfolge einer Ausgabezeichenfolge zu. Die Box hat jedoch eine spezielle Eigenschaft: Für jedes x gibt es eine weitere Eingabezeichenfolge y, die dieselbe Ausgabezeichenfolge generiert.
Mit anderen Worten, es gibt zwei eindeutige Eingabezeichenfolgen - x und y - für die die Box dieselbe Ausgabezeichenfolge zurückgibt, z. Dieses Triplett von x, y und z heißt Klaue. Die Box ist in der Informatik eine Funktion. Die Funktion ist einfach zu berechnen, dh bei gegebenem x oder y ist es einfach, z zu berechnen. Wenn Sie jedoch nur x und z erhalten, ist es selbst für einen Quantencomputer unmöglich, y und damit die Klaue zu finden.
Die einzige Möglichkeit, an die Klaue heranzukommen, besteht darin, Insiderinformationen zu haben, die sogenannte Falltür.
Vazirani und seine Kollegen möchten mit solchen Funktionen nicht nur Quantencomputer dazu bringen, Zufälligkeiten zu erzeugen, sondern auch überprüfen, ob sich der Quantencomputer quantenmechanisch verhält - was für das Vertrauen in die Zufälligkeit von entscheidender Bedeutung ist.
Das Protokoll beginnt mit einem Quantencomputer, der n Qubits in eine Überlagerung aller n-Bit-Strings einsetzt. Dann sendet ein klassischer Computer eine Beschreibung einer Quantenschaltung, die die Funktion angibt, die auf die Überlagerung angewendet werden soll - eine klauenfreie Funktion für die Falltür. Der Quantencomputer implementiert die Schaltung, ohne etwas über die Falltür zu wissen.
In diesem Stadium tritt der Quantencomputer in einen Zustand ein, in dem sich eine Menge seiner Qubits in einer Überlagerung aller n-Bit-Folgen befindet, während eine andere Menge das Ergebnis der Anwendung der Funktion auf diese Überlagerung enthält. Die beiden Qubitsätze sind miteinander verwickelt.
Der Quantencomputer mißt dann die zweite Menge von Qubits und kollabiert zufällig die Überlagerung in eine Ausgabe, die z. Die erste Menge von Qubits kollabiert jedoch zu einer gleichen Überlagerung von zwei n-Bit-Zeichenfolgen, x und y, da beide als Eingabe für die Funktion gedient haben könnten, die zu z führte.
Der klassische Computer empfängt die Ausgabe z und führt dann eine von zwei Aktionen aus. Meistens fordert es den Quantencomputer auf, seine verbleibenden Qubits zu messen. Dadurch wird die Überlagerung mit einer 50: 50-Chance entweder in x oder in y reduziert. Das entspricht einer zufälligen 0 oder 1.
Um die Quantität des Quantencomputers zu überprüfen, fordert der klassische Computer gelegentlich eine spezielle Messung an. Die Messung und ihr Ergebnis sind so konzipiert, dass der klassische Computer mithilfe der Falltür, auf die nur er Zugriff hat, sicherstellen kann, dass das Gerät, das seine Anfragen beantwortet, tatsächlich quantitativ ist. Vazirani und Kollegen haben gezeigt, dass, wenn das Gerät die richtige Antwort auf die Sondermessung gibt, ohne zusammenbrechende Qubits zu verwenden, dies dem Herausfinden der Klaue ohne Verwendung der Falltür entspricht. Das ist natürlich unmöglich. Es muss also mindestens ein Qubit im Gerät vorhanden sein, das zufällig eine 0 oder eine 1 liefert. "[Das Protokoll] erstellt ein manipulationssicheres Qubit in einem nicht vertrauenswürdigen Quantencomputer", sagte Vazirani.
Dieses Schema ist möglicherweise schneller als das Quantenabtastprotokoll von Aaron, hat jedoch einen deutlichen Nachteil. "Mit 50 oder 70 Qubits wird es nicht praktikabel sein", sagte Aaronson.
Aaronson wartet vorerst auf das Google-System. "Ob das, was sie herausbringen werden, tatsächlich gut genug ist, um die Quantenüberlegenheit zu erreichen, ist eine große Frage", sagte er.
