Wie man einen Quantencomputer in einen perfekten Zufallszahlengenerator verwandelt

Ein reiner, nachweisbarer Zufall ist schwer zu finden. Zwei neue Sätze zeigen, wie man aus Quantencomputern Zufallszahlenfabriken macht.

Sagen Sie bei jedem Treffen von Informatikern „Quantum Excellence“, und Sie werden wahrscheinlich sehen, wie sie mit den Augen rollen. Dieser Satz bezieht sich auf die Idee, dass Quantencomputer bald die Grenze überschreiten werden, ab der sie Aufgaben, die für klassische Computer äußerst schwierig sind, relativ einfach ausführen können. Und bis vor kurzem galten diese Aufgaben für reale Anwendungen als wenig nützlich - daher das Rollen der Augen.

Aber jetzt, da der Google-Prozessor diesem Ziel nahe sein soll, kann die bevorstehende Quantenüberlegenheit eine wichtige Verwendung haben: die Erzeugung reiner Zufälligkeit.

Zufälligkeit ist wichtig für fast alles, was in der Computer- und Kommunikationsinfrastruktur passiert. Insbesondere wird es verwendet, um Daten zu verschlüsseln, die alles von normalen Gesprächen über Finanztransaktionen bis hin zu Staatsgeheimnissen schützen.

Die reale, bestätigte Zufälligkeit - stellen Sie sie sich als eine Eigenschaft vor, die in einer Folge von Zahlen existiert und es unmöglich macht, die nächste Zahl in einer Folge vorherzusagen - ist äußerst schwer zu finden.

Diese Situation kann sich jedoch ändern, wenn Quantencomputer ihre Überlegenheit demonstrieren. Diese ersten Aufgaben, die von Anfang an lediglich die Überlegenheit der Technologie demonstrieren mussten, können auch einen echten zertifizierten Zufall ergeben. "Wir freuen uns, dies zu begrüßen", sagte John Martinis , Physiker an der University of California in Santa Barbara, der das Quantencomputerprojekt bei Google leitet. "Wir hoffen, dass dies der erste Einsatz eines Quantencomputers ist."

Zufälligkeit und Entropie

Zufälligkeit und Quantentheorie gehen Hand in Hand wie Donner und Blitz. In beiden Fällen ist Ersteres eine unvermeidliche Folge des Letzteren. In der Quantenwelt wird oft gesagt, dass sich Systeme in einer Kombination mehrerer Zustände befinden - den sogenannten "Überlagerung". Wenn Sie ein System messen, „kollabiert“ es in einen dieser Zustände. Während die Quantentheorie es Ihnen ermöglicht, die Wahrscheinlichkeiten dessen zu berechnen, was Sie bei einer Messung entdecken werden, ist das genaue Ergebnis immer grundsätzlich zufällig.

Physiker haben diesen Zusammenhang untersucht, um Zufallszahlengeneratoren zu erstellen. Sie alle stützen sich auf Messungen einer Art Quantenüberlagerung. Und obwohl für die meisten Methoden zur Erzeugung von Zufallszahlen, die Menschen benötigen, diese Systeme ausreichen, kann es schwierig sein, mit ihnen zu arbeiten. Darüber hinaus ist es sehr schwierig, dem Skeptiker die wahre Zufälligkeit dieser Zufallszahlengeneratoren zu beweisen. Schließlich erfordern einige der effektivsten Methoden zur Erzeugung einer bestätigten Zufälligkeit ausgefeilte Designs von mehreren Geräten, die durch große Entfernungen voneinander getrennt sind.


Google AI Lab stellt 2018 den Bristlecone 72-Qubit-Quantenprozessor vor

Ein neuerer Vorschlag, die Zufälligkeit von nur einem Gerät - einem Quantencomputer - zu extrahieren, verwendet das sogenannte. die Stichprobenaufgabe, die einer der ersten Tests der Quantenüberlegenheit sein wird. Um es zu verstehen, stellen Sie sich vor, Sie hätten eine Schachtel Fliesen bekommen. Auf jeder Kachel befinden sich mehrere Einheiten und mehrere Nullen - 000, 010, 101 usw.

Wenn es nur drei Bits gibt, gibt es acht mögliche Optionen. Es können jedoch mehrere Kopien jeder Kachel in der Box sein. Es können 50 Kacheln mit der Bezeichnung 010 und 25 Kacheln mit der Bezeichnung 001 vorhanden sein. Die Verteilung der Kacheln bestimmt die Wahrscheinlichkeit, dass Sie versehentlich eine bestimmte Kachel herausziehen. In unserem Fall können Sie Kachel 010 mit einer Wahrscheinlichkeit herausziehen, die doppelt so hoch ist wie Kachel 001.

Die Stichprobenaufgabe umfasst einen Computeralgorithmus, der dem zufälligen Herausziehen von Kacheln mit einer bestimmten Kachelverteilung entspricht. Je höher die für eine Kachel in der Verteilung definierte Wahrscheinlichkeit ist, desto wahrscheinlicher wird der Algorithmus diese Kachel ziehen.

Natürlich zieht der Algorithmus keine echten Kacheln aus einer echten Box. Es wird nur zufällig eine Binärzahl mit einer Länge von 50 Bit erzeugt, wobei eine Verteilung erhalten wird, die die gewünschte Wahrscheinlichkeit für jede der möglichen Zeilen mit einer Länge von 50 Bit bestimmt.

Bei einem klassischen Computer nimmt die Komplexität dieser Aufgabe mit zunehmender Anzahl von Bits in einer Zeichenfolge exponentiell zu. Für einen Quantencomputer wird jedoch erwartet, dass die Aufgabe sowohl für 5 Bits als auch für 50 ungefähr gleich bleibt.

Ein Quantencomputer beginnt damit, dass alle seine Quantenbits - Qubits - in einem bestimmten Zustand sind. Angenommen, sie beginnen alle mit 0. Wie klassische Computer mit klassischen Bits mit dem sogenannten arbeiten können. Logikgatter und Quantencomputer manipulieren Qubits unter Verwendung ihrer Quantenäquivalentquantengatter.

Quantengatter können jedoch Qubits in seltsame Zustände versetzen. Beispielsweise kann ein Gate-Typ ein Qubit, das mit einem Wert von 0 beginnt, in eine Überlagerung von 0 und 1 setzen. Wenn Sie dann den Zustand eines Qubits messen, wird es mit gleicher Wahrscheinlichkeit zufällig auf 0 oder 1 reduziert.

Selbst seltsamere Quantentore, die mit zwei oder mehr Qubits gleichzeitig arbeiten können, können dazu führen, dass sich die Qubits miteinander verwickeln. In diesem Fall sind die Zustände von Qubits miteinander verflochten, so dass nun alle diese Qubits mit nur einem Quantenzustand beschrieben werden können.

Wenn Sie eine Reihe von Quantentoren an einen Ort bringen und sie dann mit einer Reihe von Qubits in einer bestimmten Reihenfolge arbeiten lassen, ist dies eine Quantenschaltung. In unserem Fall können Sie, um eine zufällige Zeichenfolge von 50 Bit abzuleiten, eine Quantenschaltung erstellen, die 50 Qubits in eine Überlagerung von Zuständen einfügt, die die von Ihnen benötigte Verteilung beschreibt.

Beim Messen von Qubits wird die gesamte Überlagerung zufällig zu einer einzigen 50-Bit-Zeichenfolge zusammengefasst. Die Wahrscheinlichkeit, dass es in eine bestimmte Linie kollabiert, wird durch die Verteilung bestimmt, die durch die Quantenkontur bestimmt wird. Die Messung von Qubits ähnelt der Messung, bei der ein Mann mit verbundenen Augen in eine Tasche greift und versehentlich eine Linie mit der Verteilung herauszieht.


Scott Aaronson, Informatikspezialist, Universität von Texas in Austin

Und wie hängt das alles mit Zufallszahlen zusammen? Es ist wichtig, dass die vom Quantencomputer ausgewählte 50-Bit-Zeichenfolge viel Entropie, ein Maß für Unordnung oder Unvorhersehbarkeit und damit Zufälligkeit enthält. "Und dies kann in der Tat sehr schwerwiegende Folgen haben", sagte Scott Aaronson , ein IT-Spezialist an der Universität von Texas in Austin, der ein neues Protokoll entwickelte. "Nicht weil es der wichtigste Einsatz von Quantencomputern ist - ich denke, es ist weit davon entfernt -, sondern weil es so aussieht, als ob der erste Einsatz von Quantencomputern in die Praxis umgesetzt werden kann."

Aaronsons Protokoll zur Erzeugung von Zufallszahlen ist ziemlich einfach. Ein klassischer Computer sammelt zuerst einige zufällige Bits von einer vertrauenswürdigen Quelle und verwendet dann diesen „Keim der Zufälligkeit“, um eine Beschreibung der Quantenkontur zu generieren. Zufällige Bits bestimmen den Typ der Quantengatter und die Reihenfolge, in der sie auf Qubits einwirken müssen. Ein klassischer Computer sendet eine Beschreibung an einen Quantencomputer, der eine Quantenschaltung implementiert, Qubits misst und eine 50-Bit-Zeichenfolge zurücksendet. Somit stellt sich heraus, dass es zufällig aus der durch die Kontur definierten Verteilung ausgewählt wird.

Wiederholen Sie diesen Vorgang dann mehrmals - zum Beispiel zehnmal für jede Quantenschaltung. Ein klassischer Computer verwendet statistische Tests, um sicherzustellen, dass die Ausgangsleitungen eine angemessene Menge an Entropie enthalten. Aaronson hat gezeigt (teils in einer veröffentlichten Arbeit, die in Zusammenarbeit mit Lijie Chen verfasst wurde, teils in einer noch zu veröffentlichenden Arbeit ), dass unter bestimmten vernünftigen Annahmen, dass solche Aufgaben rechenintensiv sind, kein klassischer Computer eine solche Entropie erzeugen kann Zeit vergleichbar mit der Zeit, in der ein Quantencomputer eine solche zufällige Auswahl aus der Verteilung erstellt. Nach der Überprüfung sammelt der klassische Computer alle 50-Bit-Zeichenfolgen und führt sie dem bekannten klassischen Algorithmus zu. "Es produziert eine lange, fast vollkommen zufällige Saite", sagte Aaronson.

Quantenfalle

Das Aaronson-Protokoll eignet sich am besten für Quantencomputer mit einer Anzahl von Qubits von 50 bis 100. Wenn die Anzahl der Qubits diese Grenzen überschreitet, erlaubt die Komplexität der Berechnung die Verwendung dieses Protokolls selbst für klassische Supercomputer nicht. In diesem Fall tritt ein anderes Schema zum Erzeugen überprüfbarer Zufallszahlen unter Verwendung von Quantencomputern in die Szene ein. Es verwendet eine vorhandene mathematische Technik mit dem komplexen Namen Falltür klauenfrei. "Das klingt schlimmer als die Realität", sagte Umesh Wazirani , ein IT-Spezialist an der University of California in Berkeley, der eine neue Strategie entwickelte, die von Zvika Brackerski , Paul Cristiano , Urmila Mahadev und Thomas Vidik unterstützt wurde .

Stellen Sie unsere Box vor. Anstatt hineinzukommen und eine Zeichenfolge herauszuziehen, werfen wir eine Zeichenfolge mit n Bits hinein, nennen sie x und entfernen dann eine weitere Zeichenfolge mit n Bits. Das Feld stimmt irgendwie mit der Eingabe- und der Ausgabezeile überein. Es hat jedoch eine besondere Eigenschaft: Für jedes x gibt es eine weitere Eingabezeile y, die genau dieselbe Ausgabezeile erzeugt.

Mit anderen Worten, es gibt zwei eindeutige Eingabezeilen - x und y - für die das Feld dieselbe Ausgabezeile z zurückgibt. Dieses Tripel, x, y und z, wird Klaue genannt. Box in der Sprache der Informatik - eine Funktion. Diese Funktion ist einfach zu berechnen, dh für jedes x und y ist es einfach, z zu berechnen. Wenn Sie jedoch nur x und z nehmen, ist es selbst für einen Quantencomputer unmöglich, y - und die gesamte Klaue - zu finden.


Urmila Mahadev, Umesh Vazirani und Thomas Vidik

Der einzige Weg, um die ganze Klaue zu bekommen, besteht darin, einige zusätzliche Informationen zu finden, die sogenannten eine Falle.

Vazirani und Kollegen möchten mit solchen Funktionen nicht nur Quantencomputer zur Erzeugung von Zufallszahlen zwingen, sondern auch überprüfen, ob Quantencomputer tatsächlich nach Quantengesetzen arbeiten - was notwendig ist, um Vertrauen in zufällige Sequenzen aufzubauen.

Das Protokoll beginnt mit einem Quantencomputer, der n Qubits in eine Überlagerung aller n-Bit-Strings einfügt. Dann sendet der klassische Computer eine Beschreibung der Quantenkontur und bestimmt die Funktion, die auf die Überlagerung angewendet werden soll - die Fallenfunktion ohne Krallen. Ein Quantencomputer implementiert eine Schaltung, ohne etwas über die Falle zu wissen.

In diesem Stadium tritt der Quantencomputer in einen Zustand ein, in dem sich ein Satz seiner Qubits in einer Überlagerung aller n-Bit-Strings befindet und der andere das Ergebnis der Anwendung der Funktion auf diese Überlagerung enthält. Zwei Sätze von Qubits sind miteinander verwickelt.

Ein Quantencomputer, der einen zweiten Satz von Qubits misst, kollabiert zufällig eine Überlagerung zu einem bestimmten Ergebnis z. Der erste Satz von Qubits kollabiert zu einer ähnlichen Überlagerung von zwei n-Bit-Strings x und y, da jeder von ihnen als Eingabe für eine Funktion dienen kann, die z ausgibt.

Ein klassischer Computer empfängt einen Ausgabewert von z und führt dann eines von zwei Dingen aus. In den meisten Fällen bittet er den Quantencomputer, die verbleibenden Qubits zu messen. Dies kollabiert die Überlagerung bei x oder bei y mit einer Chance von 50%. Dies entspricht dem zufälligen Erhalten von 0 oder 1.

Manchmal verlangt ein klassischer Computer eine spezielle Messung, um einen Quantencomputer auf Quanten zu testen. Die Messung und ihr Ergebnis sind so konzipiert, dass ein klassischer Computer mit Hilfe einer Falle, auf die nur er Zugriff hat, sicherstellen kann, dass das Gerät, das auf seine Anforderungen reagiert, wirklich quantitativ ist. Vazirani und Kollegen haben gezeigt, dass wenn das Gerät die richtige Antwort auf eine bestimmte Dimension gibt, ohne den Zusammenbruch von Qubits zu verwenden, dies dem Auffinden einer Klaue ohne Falle entspricht. Und das ist unmöglich. Daher sollte mindestens ein Qubit (zufällig 0 oder 1) im Gerät kollabieren. "Das Protokoll erzeugt ein getestetes Qubit in einem Quantencomputer, dem wir nicht vertrauen", sagte Vazirani.

Dieses getestete Qubit liefert für jede Umfrage eine wirklich zufällige Information. Eine Folge solcher Abfragen kann verwendet werden, um lange zufällige Zeichenfolgen zu erstellen.

Dieses Schema funktioniert möglicherweise schneller als das Aaronson-Protokoll, weist jedoch einen eindeutigen Fehler auf. "Mit einer Qubit-Zahl von 50 oder 70 wird es nicht praktikabel sein", sagte Aaronson.

Aaronson wartet noch auf das Erscheinen eines Systems von Google. "Ob die Qualität dessen, was sie uns zeigen, ausreicht, um wirklich eine Quantenüberlegenheit zu erreichen, ist eine große Frage", sagte er.

Wenn das Unternehmen erfolgreich ist, liegt die garantierte Quantenzufälligkeit bereits vor unserer Haustür. "Wir glauben, dass dies ein nützlicher und vielversprechender Markt sein wird, und das möchten wir den Menschen anbieten", sagte Martinis.