Ausgezeichnete FAQ zu Quantum Excellence von Scott Aaronson

Vor ein paar Tagen ist ein Artikelentwurf von Google über das Erreichen der Quantenüberlegenheit in einem supraleitenden Quantencomputer in das Netzwerk gelangt. Der Text selbst wurde schnell entfernt und Gerüchte und Annahmen, einschließlich fehlerhafter, vermehrten sich um ihn herum. Der Autor des Beitrags ist Professor Scott Aaronson , einer der führenden Spezialisten für Quantenalgorithmen, und hat einen ausgezeichneten Blog. Im letzten Beitrag beantwortet er die Hauptfragen zur Quantenüberlegenheit.

Vom Übersetzer. Ich bin überhaupt kein Spezialist für algorithmische Komplexität und insbesondere für Quantenalgorithmen. Aber der Beitrag schien mir zu interessant, um ihn nicht auf Habré zu diskutieren, und für Fehler in Bezug auf Begriffe oder deren ungewöhnliche Verwendung treten Sie mich bitte in PM.

Scotts Supreme Quantum Supremacy FAQ!

Sie haben bereits Geschichten gesehen - in der Financial Times , im Technology Review , in CNET , Facebook, Reddit, Twitter oder anderswo -, die über eine Gruppe von Google sprechen, die mit einem supraleitenden 53-Qubit-Computer eine Quantenüberlegenheit erreicht hat. Diese Geschichten sind leicht zu finden, ich werde sie hier nicht anhängen, da noch keine von ihnen hätte existieren sollen.

Wie die ganze Welt jetzt weiß, bereitet Google tatsächlich eine große Erklärung zur Quantenüberlegenheit vor, die in Verbindung mit einem wissenschaftlichen Artikel in einer coolen Zeitschrift geplant ist (welche? Die Auswahl ist klein - eine von zwei). Ich hoffe das passiert innerhalb eines Monats.
In der Zwischenzeit hat die NASA, in der einige der Autoren des Artikels arbeiten, versehentlich eine alte Version des Artikels auf einer öffentlichen Website veröffentlicht. Sie war für kurze Zeit dort, aber lange genug, um in der Financial Times, meiner Post und an einer Million anderer Orte zu sein. Spekulationen ohne Fakten über ihre Bedeutung werden sich voraussichtlich vermehren.

Es scheint, dass die Welt des reinen Moments der „Mondlandung“ beraubt wurde, in der die erweiterte These von Kirche-Thüring während einer Pressekonferenz durch experimentelle Beweise zerstört wird. Es wird eher wie die Flucht der Gebrüder Wright sein - über die zwischen 1903 und 1908 Gerüchte und Halbwahrheiten in den öffentlichen Raum sickerten, als Will und Orville schließlich beschlossen, ihre Flucht zu demonstrieren. (Diesmal wird zum Glück alles viel schneller geklärt!)
Dieser Beitrag ist keine offizielle Erklärung oder Bestätigung von irgendetwas. Obwohl die Blitze bereits sichtbar sind, gehört der Donner zu einer Gruppe von Google, zeitlich und örtlich ihrer Wahl.

Vielmehr möchte ich den Fluss von Fehlinformationen stoppen und hier als Blogger und "öffentlicher Intellektueller" die FAQ zu Scotts Supreme Quantum Supremacy anbieten. Sie wissen, falls Sie plötzlich neugierig auf Quantenüberlegenheit sind oder schon immer wissen wollten, was passieren wird, wenn plötzlich eine Suchfirma von Mountain View oder von einem anderen Ort hypothetisch erklärt, dass Quantenüberlegenheit erreicht wurde.

Hier ist es ohne weiteres:

B1. Was ist Quantencomputer-Exzellenz?

Oft auf einfach „Quantenüberlegenheit“ reduziert, bezieht sich der Begriff auf die Verwendung eines Quantencomputers zur Lösung einer speziellen Reihe von Problemen, deren Lösung auf einem klassischen Computer unter Verwendung eines bekannten Algorithmus um Größenordnungen länger dauern würde - und zwar nicht aus zufälligen Gründen, sondern aus aufgrund der asymptotischen Quantenkomplexität. Der Schwerpunkt liegt hier darauf, so sicher wie möglich zu sein, dass das Problem wirklich quantenweise und klassisch unerreichbar gelöst wurde, und im Idealfall können wir in naher Zukunft eine Rechenbeschleunigung erreichen (mit verrauschten, nicht universellen Quantencomputern, die wir bereits haben dort oder wird bald sein). Wenn die Aufgabe auch für etwas nützlich ist, umso besser, aber nicht notwendig. Das Wright-Flugzeug und der Fermi-Holzstapel waren für sich genommen nicht nützlich.

B2. Wenn Google wirklich eine Quantenüberlegenheit erreicht hat, bedeutet dies, dass es jetzt keinen Crack-Code gibt , da Andrew Young, ein Kandidat für die US-Präsidentschaft, kürzlich geschlossen wurde?

Nein, das tut es nicht (obwohl ich Youngs Kandidatur immer noch mag).
Es gibt zwei Probleme. Erstens haben die von Google, IBM und anderen erstellten Geräte 50 bis 100 Qubits und keine Fehlerkorrektur. Das Hacken von RSA mit dem Shore-Algorithmus erfordert mehrere tausend logische Qubits. Mit bekannten Fehlerkorrekturmethoden können dafür leicht Millionen von physischen Qubits und eine bessere Qualität als bisher benötigt werden. Es scheint mir nicht, dass jemand dem nahe steht, und wir haben keine Ahnung, wie schnell er dem nahe kommen wird.

Und das zweite Problem ist, dass wir selbst in der hypothetischen Zukunft der Qualitätskontrolle mit Fehlerkorrektur nur einige Codes brechen können, aber nicht alle, zumindest soweit wir jetzt wissen. Zufälligerweise enthalten die öffentlichen Schlüssel, die geknackt werden können, die meisten Algorithmen, die wir zum Sichern des Internets verwenden: RSA, Diffie-Hellman, elliptische Kryptographie usw. Kryptografie auf der Basis privater Schlüssel sollte jedoch nicht betroffen sein. Und es gibt auch Kryptosysteme für öffentliche Schlüssel (zum Beispiel basierend auf Gittern), von denen niemand weiß, wie man mit QC knackt, selbst nach mehr als 20 Jahren des Versuchs, und es gibt Versuche, auf diese Systeme umzusteigen. Siehe zum Beispiel meinen Brief an Rebecca Goldstein .

B3. Welche Art von Berechnungen plant Google (oder hat dies bereits getan), die als klassisch komplex angesehen werden?

Natürlich kann ich es Ihnen sagen, aber ich fühle mich gleichzeitig dumm. Die Berechnung lautet wie folgt: Der Experimentator erzeugt eine zufällige Quantenschaltung C (d. H. Eine zufällige Folge von 1-Qubit und 2-Qubit - zwischen den nächsten Nachbarn - Gates mit einer Tiefe von 20, die beispielsweise auf ein 2D-Netzwerk n = 50-60 Qubits einwirken). Danach sendet der Experimentator C an den Quantencomputer und fordert ihn auf, C auf den Anfangszustand 0 anzuwenden, das Ergebnis in der Basis {0,1} zu messen, die beobachtbare n-Bit-Sequenz (Zeichenfolge) zurückzusenden und mehrere tausend oder Millionen Mal zu wiederholen. Schließlich führt der Experimentator unter Verwendung seiner Kenntnisse von C eine statistische Überprüfung der Übereinstimmung des Ergebnisses mit der erwarteten Ausgabe vom Quantencomputer durch.

Diese Aufgabe ist im Gegensatz zur Faktorisierung von Zahlen keine der Aufgaben mit der einzig richtigen Antwort. Das Ergebnis der Operation von Schema C stellt sich als statistische Verteilung (nennen wir es D _C ) über n-Bit-Strings heraus, aus denen wir Samples auswählen müssen. Tatsächlich kann DC normalerweise 2 ⁿ Zeilen entsprechen - so viele, dass, wenn die Qualitätskontrolle wie erwartet funktioniert, sie niemals zweimal dieselbe Zeile in der Ausgabe erzeugt. Es ist wichtig, dass die Verteilung von DC nicht gleichmäßig ist. Einige Linien entstanden als Ergebnis einer konstruktiven Interferenz von Amplituden und haben daher eine höhere Wahrscheinlichkeit, andere als Ergebnis einer destruktiven und haben eine geringere Wahrscheinlichkeit. Und obwohl wir nur einen kleinen Bruchteil aller möglichen 2 ⁿ Proben erhalten, können wir die Verteilung dieser Proben statistisch auf die erwartete ungleichmäßige Verteilung überprüfen und sicherstellen, dass wir etwas erhalten, das klassisch schwer zu reproduzieren ist.

TL; DR, ein Quantencomputer wird gebeten, eine zufällige (aber bekannte) Folge von Quantenoperationen anzuwenden - nicht weil wir am Ergebnis interessiert sind, sondern weil wir zu beweisen versuchen, dass QC diese klar definierte Aufgabe besser ausführen kann als ein klassischer Computer.

B4. Aber wenn ein Quantencomputer nur Junk-Code ausführt, dessen einziger Zweck darin besteht, für die klassische Simulation schwierig zu sein, wen interessiert das dann? Ist das nicht ein großer Over-Pie mit ... nichts?

Nein. Dies ist natürlich kein Kuchen mit allem, was lecker ist, sondern zumindest ein Kuchen mit etwas.
Haben Sie zumindest ein wenig Respekt vor der Unermesslichkeit dessen, worüber wir hier sprechen, und vor welcher Art von technischem Genie, um dies in die Realität umzusetzen. Vor der Quantenüberlegenheit (KP) kicherten KP-Skeptiker einfach, dass ein Quantencomputer auch nach Milliarden von Dollar und mehr als 20 Jahren Arbeit nicht schneller als Ihr Laptop sein kann. Zumindest nicht mit Quanten. Nachdem sie die Quantenüberlegenheit in der Welt erreicht haben, lachen sie nicht mehr. Die Überlagerung von 2 ⁵⁰ oder 2 ⁶⁰ komplexen Zahlen wurde unter Verwendung einer signifikant kleineren Zeit- und Datenvolumenressource als 2 ⁵⁰ oder 2 ⁶⁰ berechnet

Ich spreche nur von der Wright-Ebene, weil die Kluft zwischen dem, worüber wir sprechen, und der Ablehnung, die ich in verschiedenen Teilen des Internets sehe, völlig unverständlich ist. Es ist, als ob Sie geglaubt hätten, es sei im Prinzip unmöglich zu fliegen, und dann haben Sie ein schwaches Holzflugzeug gesehen - es könnte Ihren Glauben nicht erschüttern, aber es sollte ihn sicherlich nicht stärken.
Hatte ich Recht und machte mir vor vielen Jahren Sorgen , dass der ständige Hype um die viel geringeren Errungenschaften des KK die Menschen ermüden und es ihnen egal sein wird, wenn endlich etwas wirklich Wertvolles passiert?

B5. Vor vielen Jahren haben Sie die Massen für ihre Begeisterung für D-Wave und ihre Behauptungen eines erstaunlichen Quantenvorteils bei Optimierungsproblemen beim Quantenglühen verantwortlich gemacht. Jetzt werfen Sie ihnen ihre mangelnde Begeisterung für Quantenüberlegenheit vor. Warum bist du so launisch?

Denn mein Ziel ist es nicht, die Begeisterung in eine klar gewählte Richtung zu lenken, sondern richtig zu sein. Hatte ich im Nachhinein nicht hauptsächlich Recht mit D-Wave, auch wenn meine Aussagen mich in einigen Kreisen sehr unbeliebt machten? Nun, jetzt versuche ich auch in Bezug auf die Quantenüberlegenheit Recht zu haben.

B6. Wenn Quantenüberlegenheitsberechnungen einfach auf Stichproben aus einer Wahrscheinlichkeitsverteilung basieren, wie kann man dann überprüfen, ob sie korrekt durchgeführt wurden?

Danke, dass Sie gefragt haben! Genau zu diesem Thema haben ich und andere in den letzten zehn Jahren viele theoretische Grundlagen entwickelt. Ich habe die Kurzversion bereits in meiner Antwort B3 erwähnt: Sie testen dies, indem Sie statistische Tests an den vom Quantencomputer ausgegebenen Stichproben durchführen, um zu überprüfen, ob sie sich um die Peaks der zufälligen Wahrscheinlichkeitsverteilung D _{C konzentrieren.} Eine bequeme Möglichkeit, dies von Google als "linearer Kreuzentropietest" zu bezeichnen, besteht darin, einfach alle Pr [C-Ausbeuten s _i ] für alle von KK zurückgegebenen Proben s ₁ , ..., s _k zu summieren und den Test dann für erfolgreich zu erklären, wenn und nur wenn die Summe ein bestimmtes Niveau überschreitet - sagen wir bk / 2 ⁿ , wobei b eine Konstante zwischen 1 und 2 ist.

Um diesen Test anzuwenden, müssen Sie alle Wahrscheinlichkeiten berechnen, die Pr [C s _i ] auf einem klassischen Computer ergibt - und der einzige bekannte Weg, dies zu tun, ist die Iteration über eine Zeit von ~ 2 ⁿ . Aber stört es jemanden? Nein, wenn n = 50 ist und Sie googeln und Zahlen wie 2 ^{50 zählen können} (obwohl Sie nicht 2 ^{1000 erhalten} , was Google überlegen ist, khe-khe). Wenn Sie beispielsweise einen Monat lang eine große Gruppe klassischer Kerne vertrieben haben, erhalten Sie das Ergebnis, dass der CC in wenigen Sekunden produziert wurde. Stellen Sie gleichzeitig sicher, dass der CC einige Bestellungen schneller ist. Dies bedeutet jedoch, dass Experimente, die auf Stichproben basieren, fast speziell für Geräte mit ~ 50 Qubits entwickelt wurden. Selbst mit 100 Qubits haben wir keine Ahnung, wie wir das Ergebnis selbst mit der gesamten auf der Erde verfügbaren Rechenleistung sicherstellen können.
(Ich stelle separat fest, dass dieses Problem nur für Stichprobenexperimente spezifisch ist, ähnlich wie es jetzt durchgeführt wird. Wenn Sie den Shor-Algorithmus zum Faktorisieren einer 2000-stelligen Zahl verwendet haben, können Sie das Ergebnis leicht überprüfen, indem Sie einfach alle Faktoren multiplizieren und ihre Einfachheit überprüfen. Genau so Wenn KK zur Simulation eines komplexen Biomoleküls verwendet wird, können Sie das Ergebnis überprüfen, indem Sie mit dem Molekül experimentieren.)

B7. Warte einen Moment. Wenn klassische Computer die Ergebnisse eines Experiments zur Quantenüberlegenheit nur in einem Modus überprüfen können, in dem klassische Computer ein Experiment noch simulieren können (wenn auch sehr langsam), wie kann man dann von „Quantenüberlegenheit“ sprechen?

Na dann du. Mit einem 53-Qubit-Chip sehen Sie eine Beschleunigung von mehreren Millionen Mal, und Sie können das Ergebnis immer noch überprüfen und auch überprüfen, ob die Beschleunigung exponentiell mit der Anzahl der Qubits wächst, genau wie es die asymptotische Analyse vorhersagt. Dies ist nicht unerheblich.

B8 Gibt es mathematische Beweise dafür, dass kein schneller klassischer Computer die Ergebnisse eines KP-Experiments auf der Grundlage von Stichproben übertreffen kann?

Im Moment nicht. Dies ist jedoch nicht die Schuld von Forschern der Quantenüberlegenheit! Solange Theoretiker nicht einmal grundlegende Hypothesen wie P ≠ NP oder P ≠ PSPACE beweisen können, können wir ohne dies die Möglichkeit einer schnellen klassischen Simulation nicht unbedingt ausschließen. Das Beste, auf das wir hoffen können, ist die bedingte Komplexität. Und wir haben einige Ergebnisse dazu, zum Beispiel einen Artikel über die Probenahme von Bosonen oder einen Artikel von Bouldand et al. über die durchschnittliche # P-Komplexität der Berechnung der Amplituden von Zufallsschaltungen oder meinen Artikel mit Lijie Chen ("Komplexitätstheoretische Grundlagen von Quantenüberlegenheitsexperimenten"). Die wichtigste offene Frage in diesem Bereich ist meiner Meinung nach der Beweis der besten bedingten Schwierigkeiten.

B9. Gibt es eine Verwendung für die Stichprobenquantenüberlegenheit?

Bis vor kurzem war die Antwort offensichtlich nein! (Und ich weiß, weil ich selbst einer dieser Leute war). In letzter Zeit hat sich die Situation jedoch geändert - zum Beispiel dank meines zertifizierten Zufälligkeitsprotokolls , das zeigt, wie KP basierend auf Stichproben unabhängig verwendet werden können, um Bits zu generieren, die selbst für einen skeptischen Dritten (unter Annahmen über Berechnungen) als zufällig erwiesen werden können. Dies hat wiederum eine Anwendung in Kryptowährung und anderen kryptografischen Protokollen. Ich hoffe, dass bald weitere solche Anwendungen kommen.

B10. Wenn Experimente zur Quantenüberlegenheit zufällige Bits alles erzeugen, warum ist das überhaupt interessant? Ist es nicht möglich, Qubits durch einfaches Messen trivial in zufällige Bits umzuwandeln?

Die Quintessenz ist, dass QC ungleichmäßig verteilte Zufallsbits erzeugt. Stattdessen wird eine Auswahl aus einer komplexen, korrelierten Wahrscheinlichkeitsverteilung über 50-60-Bit-Zeichenfolgen erstellt. In meinem Protokoll spielen Abweichungen von der Einheitlichkeit eine zentrale Rolle dabei, wie die Qualitätskontrolle den Skeptiker davon überzeugt, dass er tatsächlich zufällige Bits ausgewählt hat, anstatt im Geheimen eine Art Pseudozufallsgenerator zu verwenden.

B11. Haben jahrzehntelange quantenmechanische Experimente, zum Beispiel mit Verletzung der Bellschen Ungleichung, keine Quantenüberlegenheit bewiesen?

Dies ist eine rein lexikalische Frage. Diese Experimente zeigten andere Arten der Quantenüberlegenheit: Zum Beispiel können sie im Fall der Bellschen Ungleichung als "Quantenkorrelationsüberlegenheit" bezeichnet werden. Sie zeigten keine Überlegenheit der Quantenberechnung, d.h. die Fähigkeit, etwas zu finden, das für einen klassischen Computer unzugänglich ist (wo die klassische Simulation keine räumlichen Einschränkungen usw. aufweist). Wenn Menschen heutzutage den Ausdruck "Quantenüberlegenheit" verwenden, meinen sie Quantenberechnungsüberlegenheit.

B12. Trotzdem gibt es nicht unzählige Beispiele für Materialien und chemische Reaktionen, die klassisch schwer zu simulieren sind, und speziell konstruierte Quantensimulatoren (wie die der Lukin-Gruppe in Harvard). Warum werden sie nicht als Überlegenheit des Quantencomputers angesehen?

In den Definitionen einiger Leute werden sie berücksichtigt! Der Hauptunterschied zu einem Google-Computer besteht darin, dass er über einen voll programmierbaren Computer verfügt. Sie können eine beliebige Folge von 2-Qubit-Gates (für benachbarte Qubits) eingeben, indem Sie einfach Befehle von einem klassischen Computer eingeben.

Mit anderen Worten, KP-Skeptiker können nicht mehr spöttisch bemerken, dass Quantensysteme natürlich nur schwer klassisch zu simulieren sind, aber dies liegt einfach daran, dass die Natur im Allgemeinen schwer zu simulieren ist und Sie das im Feld gefundene zufällige Molekül nicht in einen Computer umprogrammieren können, um sich selbst zu simulieren dich selbst. Nach jeder vernünftigen Definition sind supraleitende Geräte, die von Google, IBM und anderen entwickelt wurden, Computer im wahrsten Sinne des Wortes.

B13 Haben Sie (Scott Aaronson) das Konzept der Quantenexzellenz erfunden?

Nein. Ich habe an seiner Entwicklung mitgewirkt, und so hat mir beispielsweise Sabina Hosenfelder fälschlicherweise die Urheberschaft der gesamten Idee zugeschrieben. Der Begriff "Quantenüberlegenheit" wurde 2012 von John Preskill vorgeschlagen, obwohl die Grundidee in gewissem Sinne zu Beginn der Quantenbeiträge in den frühen 80er Jahren auftauchte. 1994 wurde die Verwendung des Shore-Algorithmus zur Faktorisierung einer großen Zahl zum Hauptexperiment zum Testen der Quantenüberlegenheit, obwohl dies derzeit noch zu schwierig zu produzieren ist.

Die Schlüsselidee, dass stattdessen Stichproben verwendet werden können, wurde meines Wissens erstmals von Barbara Terhal und David DiVincenzo in einem Artikel aus dem Jahr 2002 vorgeschlagen. Die aktuellen Bemühungen um einen CP in der Stichprobe begannen um 2011, als Alex Arkhipov und ich unseren Artikel über Bosonic Sampling veröffentlichten und Bremner, Jozsa und Shepherd unabhängig voneinander einen Artikel über Modelle des Pendelns von Hamiltonianern veröffentlichten . Diese Artikel zeigten nicht nur „einfache“, nicht universelle Quantensysteme, die offensichtlich komplexe Stichprobenprobleme lösen können, sondern auch, dass die Existenz eines effektiven klassischen Algorithmus einen Rückgang der Polynomhierarchie bedeuten würde. Arkhipov und ich legten auch den Grundstein für das Argument, dass selbst ungefähre Versionen der Quantenabtastung klassisch komplex sein können.

Soweit ich weiß, entstand die Idee der „Zufallsabtastschaltung“ - das heißt, ein komplexes Abtastproblem durch zufällige Auswahl einer Folge von 2-Qubit-Gates in beispielsweise einer supraleitenden Architektur -, deren Korrespondenz im Dezember 2015 begann, zu der auch John Martinis, Hartmut Neven, gehörten , Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Jozsa, Aram Harrow, Greg Kuperberg und andere. Der Thread hatte den Titel "Herausfordernde Stichprobenprobleme mit 40 Qubits" und der Brief begann mit "Entschuldigung für Spam".Darin diskutierte ich die verschiedenen Vor- und Nachteile von drei Optionen zum Demonstrieren eines Quantenvorteils unter Verwendung von Abtastung: (1) Zufallsschaltungen, (2) Pendeln von Hamiltonianern, (3) Boson-Abtastung. Nachdem Greg Cooperberg für Option (1) eingetreten war, bildete sich schnell ein Konsens darüber, dass (1) aus technischer Sicht wirklich die beste Option wäre und dass wir es irgendwie können, wenn wir noch keine zufriedenstellende theoretische Rechtfertigung für (1) haben umgehen Sie dies.

Danach hat das Google-Team sowohl theoretisch als auch numerisch hervorragende Stichprobenverfahren durchgeführt, während Lijie Chen und ich sowie Bouland et al. lieferte unterschiedliche Beweise für die klassische Komplexität dieses Problems aus Sicht der Komplexitätstheorie.

B14. Was bedeutet dies für Skeptiker, wenn Quantenüberlegenheit erreicht wird?

Wow, ich würde jetzt nicht an ihrer Stelle sein wollen! Sie können auf die Position zurückgreifen, dass natürlich Quantenüberlegenheit möglich ist (und wer hat das anders gesagt? Nun, natürlich nicht!), Und die ganze Schwierigkeit lag immer in der Quantenfehlerkorrektur. Und tatsächlich haben einige dies von Anfang an gesagt. Und andere, mein guter Freund Gil Kalai, unter ihnen, sagten direkt in diesem Blog, dass Quantenüberlegenheit aus fundamentalen Gründen niemals erreicht werden würde. Jetzt werden sie nicht geschraubt.

B15. Und was dann?

Wenn dies wirklich zu einer Quantenüberlegenheit führt, verfügt die Google-Gruppe meiner Meinung nach über die gesamte Hardware, um mein Protokoll für die zertifizierte zufällige Bitgenerierung zu demonstrieren. Und dies ist tatsächlich eines der folgenden Dinge in ihrem Plan.
Außerdem besteht der nächste naheliegende Schritt darin, eine programmierbare Qualitätskontrolle mit 50 bis 100 Qubits für eine nützliche Quantensimulation (z. B. ein System mit einem kondensierten Materiezustand) viel schneller als jede klassische Methode zu verwenden. Und der zweite offensichtliche Schritt besteht darin, die Verwendung der Fehlerkorrektur zu demonstrieren, um das logische Qubit länger am Leben zu halten als die Lebensdauer der physischen Qubits, auf denen es basiert. Es besteht kein Zweifel, dass IBM, Google und der Rest der Spieler sich in diesen Schritten gegenseitig um den Vorrang jagen werden.