Urmila Mahadev verbrachte acht Jahre in der Magistratur auf der Suche nach einer Antwort auf eine der grundlegendsten Fragen des Quantencomputers: Woher wissen wir, dass ein Quantencomputer zumindest etwas auf Quantenebene getan hat?
Im Frühjahr 2017 war Urmila Mahadev aus Sicht der meisten Doktoranden in einer guten Position. Sie hat gerade das entscheidende Problem des Quantencomputers gelöst - das Gebiet der Informatik, das seine Fähigkeiten aus den seltsamen Gesetzen der Quantenphysik bezieht. Zusammen mit ihren früheren Arbeiten ein neues Ergebnis von Mahadev, das das sogenannte beschreibt "Blind Computing" machte deutlich, "dass sie ein aufstrebender Stern ist", sagte
Scott Aaronson , IT-Spezialist an der University of Texas in Austin.
Die damals 28-jährige Mahadev war bereits in ihrem siebten Jahr an der Graduiertenschule der University of California in Berkeley - viel länger als die Zeit, die die meisten Schüler benötigen, um die Geduld zu verlieren und die Schule bereits zu beenden. Und schließlich konnte sie eine „ausgezeichnete Doktorarbeit“ schreiben, sagte
Umesh Vazirani , ihr Kurator in Berkeley.
Aber Mahadev beendete das Studium in diesem Jahr nicht. Sie betrachtet dieses Problem nicht einmal. Sie ist noch nicht fertig.
Mehr als fünf Jahre lang arbeitete sie mit einer anderen Forschungsaufgabe, die Aaronson als "eine der grundlegendsten Fragen, die im Bereich des Quantencomputers gestellt werden können" bezeichnete. Nämlich: Wenn Sie einen Quantencomputer bitten, eine Berechnung für Sie durchzuführen, woher wissen Sie, ob er Ihren Anweisungen folgt, und tut er tatsächlich etwas auf Quantenebene?
Diese Frage könnte bald aufhören, rein akademisch zu sein. Die Forscher hoffen, dass nicht viele Jahre vergehen und Quantencomputer eine exponentielle Beschleunigung bei der Lösung vieler Probleme bieten können, von der Modellierung einer Situation in der Nähe eines Schwarzen Lochs bis zur Simulation der Faltung großer Proteine.
Aber sobald ein Quantencomputer Berechnungen durchführen kann, zu denen der klassische nicht in der Lage ist, woher wissen wir, dass er sie korrekt durchführt? Wenn Sie einem gewöhnlichen Computer nicht glauben, können Sie theoretisch jeden Schritt seiner Berechnungen selbst sorgfältig studieren. Aber Quantencomputer widersetzen sich solchen Prüfungen von Natur aus. Zunächst ist ihre Arbeit äußerst kompliziert: Um eine Beschreibung des internen Zustands eines Computers aufzuzeichnen, der nur aus wenigen hundert Quantenbits oder Qubits besteht, benötigen Sie eine Festplatte, die größer als das beobachtete Universum ist.
Und selbst wenn Sie einen Ort hätten, an dem Sie diese Beschreibung schreiben könnten, könnte sie nicht auseinander genommen werden. Der interne Zustand eines Quantencomputers ist normalerweise eine Überlagerung vieler nicht quantenbezogener, sondern klassischer Zustände (wie der Schrödinger-Katze, die sowohl lebendig als auch tot ist). Sobald Sie jedoch einen Quantenzustand messen, fällt dieser sofort in einen der klassischen zusammen. Werfen Sie einen Blick in einen Quantencomputer mit 300 Qubits - und Sie werden nur 300 klassische Bits, Nullen und Einsen sehen, die Sie höflich anlächeln.
"Ein Quantencomputer ist leistungsfähig, aber mysteriös", sagte Vazirani.
Angesichts dieser Einschränkungen haben Informatiker lange darüber nachgedacht, ob ein Quantencomputer eine absolut zuverlässige Garantie dafür bieten kann, dass er wirklich das getan hat, was er behauptet zu sein. "Wird die Wechselwirkung zwischen der Quanten- und der klassischen Welt stark genug sein, um einen solchen Dialog zu ermöglichen?"
Fragte Dorit Akharonova , eine Informatikerin an der Hebräischen Universität von Jerusalem.
Im zweiten Jahr der Magistratur wurde Mahadev von dieser Aufgabe gefangen genommen, und sie versteht nicht einmal ganz, warum. In den folgenden Jahren versuchte sie, einen Ansatz für sie zu verwenden, dann einen anderen. "Ich hatte viele solcher Momente, in denen es mir so vorkam, als würde ich alles richtig machen, und dann brach alles zusammen - entweder sehr schnell oder nach einem Jahr", sagte sie.
Aber sie weigerte sich aufzugeben. Mahadev zeigte eine so unveränderliche Entschlossenheit, dass Vazirani sich zuvor noch nicht getroffen hatte. "In diesem Sinne ist Urmila absolut außergewöhnlich", sagte er.
Und jetzt, nach acht Jahren Studium, war Mahadev erfolgreich. Sie erstellte ein interaktives Protokoll, mit dem ein Benutzer, der keine Quantenfähigkeiten besitzt, dennoch eine Kryptographie verwenden kann, um einen Quantencomputer einzudämmen und ihn überall hin zu lenken, mit der vollständigen Gewissheit, dass der Quantencomputer Befehlen gehorcht. Der Mahadev-Ansatz, sagte Vazirani, gibt dem Benutzer "einen Druckhebel, den der Computer nicht loswerden kann".
"Es ist absolut erstaunlich", sagte Aaronson, dass ein Doktorand dieses Ergebnis allein erzielen könnte.
Mahadev, heute Postdoc in Berkeley, präsentierte ihr Protokoll im Oktober 2018 auf dem jährlichen
Symposium für Informatik , einer der größten Computerkonferenzen in diesem Jahr in Paris. Das Publikum zeichnete ihre Arbeit mit den Preisen "Beste Arbeit" und "Beste studentische Arbeit" aus - eine seltene Auszeichnung für einen Spezialisten für theoretische Informatik.
In einem Blogbeitrag beschrieb
Thomas Widick , ein IT-Spezialist am California Institute of Technology, der in der Vergangenheit mit Mahadev zusammengearbeitet hatte, ihr Ergebnis als „eine der herausragendsten Ideen, die in den letzten Jahren an der Schnittstelle von Quantencomputer und theoretischer Informatik entstanden sind“.
Forscher auf dem Gebiet der Informatik sind nicht nur von der Leistungsfähigkeit des Mahadev-Protokolls begeistert, sondern auch von einem radikal neuen Ansatz, der zur Bewältigung dieses Problems beiträgt. Die Verwendung der klassischen Kryptographie im Quantenfeld sei "eine wirklich innovative Idee", schrieb Vidik. "Ich denke, dass viele andere Ergebnisse auf diesen Ideen wachsen werden."
Langer Weg
Mahadev wuchs in Los Angeles in einer Familie von Ärzten auf und studierte an der University of Southern California, wo sie von einem Gebiet in ein anderes zog. Zunächst war sie nur davon überzeugt, dass sie selbst keine Ärztin werden wollte. Dann interessierte sie sich sehr für den Kurs der theoretischen Informatik, der von Leonard Aidleman, einem der Schöpfer des berühmten RSA-Verschlüsselungsalgorithmus, unterrichtet wurde. Sie trat in die Graduiertenschule in Berkeley ein und gab in einer Begründung an, dass sie sich für alle Aspekte der theoretischen Informatik interessierte - außer für Quantencomputer.
"Es war etwas völlig Fremdes, von dem ich die geringste Ahnung hatte", sagte sie.
In Berkeley änderte sie jedoch bald ihre Meinung unter dem Einfluss der verfügbaren Erklärungen von Wazirani. Er führte sie in die Suche nach einem Protokoll zur Bestätigung des Quantencomputers ein, und diese Aufgabe „ließ ihre Fantasie wirklich funktionieren“, sagte Vazirani.
"Die Protokolle sind wie Rätsel", erklärte Mahadev. "Es ist einfacher für mich als bei anderen Fragen, denn hier können Sie sofort über die Protokolle nachdenken, sie in Teile zerlegen und beobachten, wie sie funktionieren." Sie wählte diese Aufgabe für ihre Promotion und begann einen "sehr langen Weg", wie Vazirani sagte.
Wenn ein Quantencomputer ein Problem lösen kann, zu dem der klassische nicht in der Lage ist, bedeutet dies nicht automatisch, dass die Lösung schwer zu überprüfen ist. Nehmen wir zum Beispiel das Problem der Faktorisierung großer Zahlen - es wird angenommen, dass ein großer Quantencomputer es effizient lösen kann, aber gleichzeitig über die Fähigkeiten eines klassischen Computers hinausgeht. Aber selbst wenn ein klassischer Computer die Zahl nicht faktorisieren kann, kann er leicht überprüfen, ob das Quantenergebnis korrekt ist - er muss nur alle Faktoren multiplizieren und prüfen, ob sie die richtige Antwort geben.
Informatiker glauben jedoch (und haben kürzlich einen Schritt unternommen, um zu beweisen), dass viele Aufgaben, die ein Quantencomputer lösen könnte, keine solche Funktion haben. Mit anderen Worten, ein klassischer Computer kann sie nicht nur nicht lösen, sondern auch nicht erkennen, ob die vorgeschlagene Lösung korrekt ist. Infolgedessen fragte
Daniel Gottsman , ein theoretischer Physiker am Waterloo Perimeter Institute, im Jahr 2004, ob es möglich sei, ein Protokoll zu entwickeln, mit dem ein Quantencomputer einem Nicht-Quantenbeobachter beweisen könne, dass er tatsächlich das erreicht habe, was er behauptete.
Seit vier Jahren finden Quantencomputerforscher eine teilweise Antwort. Zwei verschiedene Teams haben
gezeigt, dass ein Quantencomputer seine Berechnungen beweisen kann, jedoch nicht gegenüber einem rein klassischen Verifizierer, sondern gegenüber einem, der Zugriff auf einen anderen, sehr kleinen Quantencomputer hat. Die Forscher verbesserten diesen Ansatz später, indem sie zeigten, dass der Tester nur die Fähigkeit benötigte, den Zustand von jeweils einem Qubit zu messen.
Und 2012 zeigte ein Forscherteam, zu dem auch Vazirani gehörte, dass ein vollständig klassischer Verifizierer Quantenberechnungen verifizieren kann, wenn sie von zwei Quantencomputern durchgeführt wurden, die nicht miteinander kommunizierten. Ihr Ansatz wurde jedoch speziell für ein solches Szenario entwickelt, und die Aufgabe schien in eine Sackgasse zu geraten, sagte Gottsman. "Ich denke, es gab wahrscheinlich Leute, die dachten, dass es keinen Weg mehr gibt, weiter zu gehen."
Um diese Zeit stand Mahadev vor dem Problem der Bestätigung. Zunächst versuchte sie, ein „bedingungsloses“ Ergebnis zu erzielen, ohne anzugeben, was ein Quantencomputer kann und was nicht. Nachdem sie einige Zeit erfolglos an der Aufgabe gearbeitet hatte, schlug Vazirani stattdessen die Möglichkeit vor, "Post-Quanten" -Kryptographie zu verwenden - das heißt Kryptographie, deren Aufbrechen laut Forschern die Fähigkeiten selbst von Quantencomputern übersteigt, obwohl dies sicher ist Sie wissen es nicht. (Methoden wie der RSA-Algorithmus zum Verschlüsseln von Online-Übertragungen sind nicht postquant - ein großer Quantencomputer kann sie knacken, da ihre Sicherheit auf der Schwierigkeit beruht, große Zahlen zu berücksichtigen).
Während Mahadev und Vazirani 2016 an einer anderen Aufgabe arbeiteten, gelang ihnen ein Durchbruch, der sich in Zukunft als entscheidend erweisen wird. Zusammen mit
Paul Cristiano , einem IT-Spezialisten bei OpenAI, einem in San Francisco ansässigen Unternehmen, entwickelten sie eine Möglichkeit, mithilfe der Kryptographie einen Quantencomputer in einen „geheimen Zustand“ zu versetzen - einen Zustand, der von einem klassischen Verifizierer beschrieben wird, nicht jedoch vom Quantencomputer selbst .
Ihre Prozedur basiert auf einer "Trap" -Funktion - eine, die einfach auszuführen, aber schwer umzukehren ist, es sei denn, Sie haben einen geheimen kryptografischen Schlüssel. (Zu diesem Zeitpunkt wussten die Forscher noch nicht, wie man eine geeignete Falle herstellt - dies kam später). Die Funktion muss außerdem die Eigenschaft „zwei in eins“ haben. Dies bedeutet, dass für jeden Satz von Ausgabedaten zwei verschiedene Sätze von Eingabedaten vorhanden sind. Zum Beispiel können wir uns eine Funktion vorstellen, die Zahlen quadriert - zusätzlich zur Zahl 0 gibt es für jedes Ergebnis (zum Beispiel 9) zwei entsprechende Eingangsnummern (3 und -3).
Mit einer ähnlichen Funktion können Sie einen Quantencomputer wie folgt in einen geheimen Zustand versetzen. Zunächst bitten Sie den Computer, eine Überlagerung aller möglichen Eingabedaten der Funktion zu erstellen (dies mag für den Computer als schwierige Aufgabe erscheinen, ist aber in der Tat einfach). Dann weisen Sie den Computer an, die Funktion auf diese gigantische Überlagerung anzuwenden, und erstellen einen neuen Zustand, der eine Überlagerung aller möglichen Ausgaben der Funktion darstellt. Überlagerungen von Eingabe und Ausgabe werden verwechselt, was bedeutet, dass die Messung einer von ihnen sofort die andere beeinflusst.
Anschließend befehlen Sie dem Computer, den Endzustand zu messen und das Ergebnis zu melden. Bei einer Messung wird der Status auf einen der möglichen Sätze von Ausgabedaten reduziert, und der Eingabezustand wird entsprechend reduziert, da sie verwirrt sind. Wenn wir beispielsweise die Quadratfunktion verwenden und der Ausgabezustand 9 ist, wird die Eingabe auf Überlagerung 3 und reduziert -3.
Denken Sie jedoch daran, dass wir eine Trap-Funktion verwenden. Wir haben einen geheimen Schlüssel für die Falle, so dass wir die beiden Zustände, aus denen die Eingabeüberlagerung besteht, ziemlich leicht herausfinden können. Ein Quantencomputer kann nicht. Und er kann die Eingabeüberlagerung nicht einfach messen, um herauszufinden, woraus sie besteht, da eine solche Messung sie noch weiter kollabiert und dem Computer eine von zwei Optionen lässt, ohne die andere berechnen zu können.
Im Jahr 2017 verstand Mahadev, wie die Trap-Funktionen, auf denen die Secret-State-Methode basiert, mithilfe der Kryptografie namens
Learning with Errors (LWE) erstellt werden. Mithilfe dieser Trap-Funktionen konnte sie eine Quantenversion des „blinden“ Computing erstellen, mit der Benutzer von Cloud-Computing-Systemen ihre Daten verbergen können, sodass Cloud-Computer sie nicht lesen können, selbst wenn sie Berechnungen mit ihnen durchführen. Kurz darauf haben Mahadev, Wazirani und Cristiano gemeinsam mit Vidik und
Zwika Brackerski (vom Weizmann-Institut in Israel) die Qualität dieser Funktionen weiter verbessert und mithilfe der Secret-State-Methode eine garantierte Methode entwickelt, mit der ein Quantencomputer
nachweislich Zufallszahlen erzeugen kann.
Mahadev hätte den Abschluss bereits auf der Grundlage solcher Ergebnisse erhalten können, aber sie beabsichtigte, weiter zu arbeiten, bis sie das Bestätigungsproblem gelöst hatte. "Ich habe nie über eine Veröffentlichung nachgedacht, weil mein Ziel überhaupt keine Veröffentlichung war", sagte sie.
Manchmal übte die Unsicherheit in der Fähigkeit, dieses Problem zu lösen, Druck auf sie aus. Aber sie sagte: "Ich habe Zeit damit verbracht, Dinge zu lernen, die mich interessieren, so dass dieser Zeitvertreib nicht als Verschwendung bezeichnet werden kann."
In Stein gemeißelt
Mahadev versuchte, verschiedene Ansätze für die Methode des geheimen Zustands zu verwenden, um ein Bestätigungsprotokoll zu organisieren, aber für einige Zeit führte dies zu nichts. Und dann kam ihr eine Idee: Die Forscher hatten bereits gezeigt, dass der Tester einen Quantencomputer überprüfen kann, wenn er in der Lage ist, Quantenbits zu messen. Per Definition hat der klassische Verifizierer keine solche Möglichkeit. Aber was wäre, wenn ein klassischer Tester einen Quantencomputer dazu bringen könnte, selbst Messungen durchzuführen und ihre Ergebnisse ehrlich zu melden?
Die Schwierigkeit wird sein, wie Mahadev verstanden hat, dass der Quantencomputer verspricht, eine bestimmte Messung durchzuführen, bevor er herausfindet, um welche Messung der Inspektor ihn bitten wird - andernfalls wird es für den Computer sehr einfach sein, ihn zu täuschen. Hier kommt die Secret-State-Methode ins Spiel. Das Mahadev-Protokoll erfordert, dass ein Quantencomputer zuerst einen geheimen Zustand erzeugt und ihn dann mit dem Zustand verwechselt, den er messen muss. Und erst dann weiß der Computer, welche Messung durchgeführt werden muss.
Da der Computer die dem Inspektor bekannten internen Details des geheimen Zustands nicht kennt, zeigte Mahadev, dass der Quantencomputer in keiner Weise betrügen konnte, ohne Zweifel zu lassen. Tatsächlich, schrieb Vidik, sind die Qubits, die ein Computer messen muss, "auf einem kryptografischen Stein geschnitzt". Wenn die Messergebnisse wie ein korrekter Beweis aussehen, kann der Inspektor daher sicher sein, dass dies der Fall ist.
„Das ist eine wundervolle Idee! - schrieb Vidik. "Sie schlägt mich jedes Mal, wenn Urmila sie erklärt."
Mahadevs Bestätigungsprotokoll - zusammen mit einem Zufallszahlengenerator und einer blinden Verschlüsselung - hängt von der Annahme ab, dass Quantencomputer LWE nicht knacken können. Bisher wird LWE allgemein als der führende Kandidat für die Post-Quanten-Kryptographie angesehen, und bald kann das Nationale Institut für Standards und Technologie ihn als neuen kryptografischen Standard genehmigen, um diejenigen, die zu Rissen neigen, durch einen Quantencomputer zu ersetzen. Dies garantiert jedoch nicht, dass es tatsächlich sicher gegen Quantencomputer ist, warnte Gottsman. "Aber bisher ist alles klar", sagt er. "Noch hat niemand Beweise für die Möglichkeit gefunden, es zu brechen."
In jedem Fall macht das Vertrauen des Protokolls in die LWE Mahadev auf jeden Fall zu einer erfolgreichen Arbeit, schrieb Vidik. Der einzige Weg, wie ein Quantencomputer das Protokoll austricksen kann, besteht darin, dass jemand aus der Welt des Quantencomputers herausfindet, wie man LWE knackt, was an sich schon eine bemerkenswerte Leistung sein wird.
Es ist unwahrscheinlich, dass das Mahadev-Protokoll in absehbarer Zeit auf einem echten Quantencomputer implementiert wird. Bisher benötigt er aus praktischer Sicht zu viel Rechenleistung. In Zukunft kann sich dies jedoch ändern, wenn Quantencomputer wachsen und Forscher dieses Protokoll rationalisieren.
Es ist unwahrscheinlich, dass das Protokoll beispielsweise in den nächsten fünf Jahren erscheint, aber "es ist keine solche Science-Fiction", sagte Aaronson. "Zu diesem Thema wird es bereits möglich sein, in der nächsten Phase der Entwicklung von Quantencomputern zu überlegen, ob alles so läuft, wie es sollte."
Und angesichts der Geschwindigkeit, mit der sich dieses Gebiet entwickelt, kann diese Phase früher als erwartet beginnen. Immerhin, so Vidik, glaubten die Forscher erst vor fünf Jahren, dass noch viele Jahre vergehen würden, bis Quantencomputer kein Problem lösen könnten, zu dem klassische Computer nicht in der Lage sind. "Und jetzt", sagte er, "glauben die Leute, dass dies in ein oder zwei Jahren passieren wird."
Makhadev, der ihr Lieblingsproblem gelöst hatte, blieb in einem etwas verwirrten Zustand. Mahadev sagt, dass sie gerne verstehen würde, was genau dieses Problem für sie so geeignet gemacht hat. « - , ». , , , , , , .
« , , — . – ».