In welchen konkreten Fällen übertreffen Quantencomputer ihre klassischen Pendants? Das ist eine schwer zu beantwortende Frage, zum Teil, weil die heutigen Quantencomputer knifflige Dinger sind, geplagt von Fehlern, die sich häufen und ihre Berechnungen verderben können.
In gewisser Hinsicht haben sie es natürlich bereits getan. 2019 Physiker bei Google angekündigt die sie mit einer 53-Qubit-Maschine erreichten Quantenhoheit, ein symbolischer Meilenstein, der den Punkt markiert, an dem ein Quantencomputer etwas leistet, das über die Reichweite eines praktischen klassischen Algorithmus hinausgeht. Ähnlich Demonstrationen von Physikern der University of Science and Technology of China folgten bald darauf.
Aber anstatt sich auf ein experimentelles Ergebnis für eine bestimmte Maschine zu konzentrieren, wollen Informatiker wissen, ob klassische Algorithmen mit den immer größer werdenden Quantencomputern mithalten können. „Die Hoffnung ist, dass sich die Quantenseite schließlich vollständig zurückzieht, bis es keine Konkurrenz mehr gibt“, sagte er Scott Aaronson, Informatiker an der University of Texas, Austin.
Diese allgemeine Frage ist immer noch schwer zu beantworten, wiederum teilweise wegen dieser lästigen Fehler. (Zukünftige Quantenmaschinen werden ihre Unvollkommenheiten mit einer Technik namens kompensieren Quantenfehlerkorrektur, aber diese Fähigkeit ist noch ein weiter Weg.) Ist es möglich, den erhofften unkontrollierbaren Quantenvorteil auch mit unkorrigierten Fehlern zu erzielen?
Die meisten Forscher vermuteten, dass die Antwort nein war, aber sie konnten es nicht für alle Fälle beweisen. Nun, in einem Krepppapier Auf dem Preprint-Server arxiv.org gepostet, hat ein Team von Informatikern einen großen Schritt in Richtung eines umfassenden Nachweises getan, dass eine Fehlerkorrektur für einen dauerhaften Quantenvorteil beim Random Circuit Sampling notwendig ist – das maßgeschneiderte Problem, mit dem Google die Quantenüberlegenheit demonstrierte. Sie taten dies, indem sie einen klassischen Algorithmus entwickelten, der Stichprobenexperimente mit Zufallsschaltungen simulieren kann, wenn Fehler vorhanden sind.
„Das ist ein schönes theoretisches Ergebnis“, sagte Aaronson und betonte, dass der neue Algorithmus für die Simulation realer Experimente wie denen von Google praktisch nicht nützlich sei.
Bei Random-Circuit-Sampling-Experimenten beginnen die Forscher mit einer Reihe von Qubits oder Quantenbits. Anschließend manipulieren sie diese Qubits zufällig mit Operationen, die als Quantengatter bezeichnet werden. Einige Gatter bewirken, dass Paare von Qubits verschränkt werden, was bedeutet, dass sie einen gemeinsamen Quantenzustand haben und nicht separat beschrieben werden können. Wiederholte Gate-Schichten bringen die Qubits in einen komplizierteren verschränkten Zustand.
Um mehr über diesen Quantenzustand zu erfahren, messen die Forscher dann alle Qubits im Array. Dies führt dazu, dass ihr kollektiver Quantenzustand zu einer zufälligen Folge gewöhnlicher Bits zusammenbricht – 0 und 1. Die Zahl der möglichen Ergebnisse wächst rasant mit der Zahl der Qubits im Array: Bei 53 Qubits wie in Googles Experiment sind es fast 10 Billiarden. Und nicht alle Saiten sind gleich wahrscheinlich. Das Abtasten von einer Zufallsschaltung bedeutet, dass solche Messungen viele Male wiederholt werden, um ein Bild der Wahrscheinlichkeitsverteilung zu erstellen, die den Ergebnissen zugrunde liegt.
Die Frage des Quantenvorteils ist einfach diese: Ist es schwierig, diese Wahrscheinlichkeitsverteilung nachzuahmen? mit einem klassischen Algorithmus das keine Verschränkung verwendet?
In 2019 Forscher erwies sich dass die Antwort für fehlerfreie Quantenschaltkreise ja lautet: Es ist in der Tat schwierig, ein zufälliges Schaltkreis-Sampling-Experiment klassisch zu simulieren, wenn es keine Fehler gibt. Die Forscher arbeiteten im Rahmen der Computational Complexity Theory, die die relative Schwierigkeit verschiedener Probleme klassifiziert. Auf diesem Gebiet behandeln Forscher die Anzahl der Qubits nicht als eine feste Zahl wie 53. „Stellen Sie sich das vor als n, was eine Zahl ist, die zunehmen wird“, sagte Aram Egge, Physiker am Massachusetts Institute of Technology. „Dann möchten Sie fragen: Machen wir Dinge, bei denen der Aufwand exponentiell ist? n oder Polynom in n?” Dies ist die bevorzugte Methode, um die Laufzeit eines Algorithmus zu klassifizieren – wann n groß genug wird, ein exponentieller Algorithmus n weit hinter jedem polynomialen Algorithmus zurück n. Wenn Theoretiker von einem Problem sprechen, das für klassische Computer schwer, aber für Quantencomputer einfach ist, beziehen sie sich auf diese Unterscheidung: Der beste klassische Algorithmus benötigt exponentielle Zeit, während ein Quantencomputer das Problem in polynomieller Zeit lösen kann.
Doch dieses Papier von 2019 ignorierte die Auswirkungen von Fehlern, die durch unvollkommene Gatter verursacht wurden. Dies ließ den Fall eines Quantenvorteils für zufälliges Schaltungsabtasten ohne Fehlerkorrektur offen.
Wenn Sie sich vorstellen, die Anzahl der Qubits kontinuierlich zu erhöhen, wie es die Komplexitätstheoretiker tun, und Sie auch Fehler berücksichtigen möchten, müssen Sie entscheiden, ob Sie auch weiterhin weitere Schichten von Gattern hinzufügen – die Schaltungstiefe erhöhen, wie Forscher sagen. Angenommen, Sie halten die Schaltungstiefe konstant bei beispielsweise relativ flachen drei Schichten, während Sie die Anzahl der Qubits erhöhen. Sie werden nicht viel Verschränkung bekommen, und die Ausgabe wird immer noch für die klassische Simulation zugänglich sein. Wenn Sie andererseits die Schaltungstiefe erhöhen, um mit der wachsenden Anzahl von Qubits Schritt zu halten, werden die kumulativen Auswirkungen von Gate-Fehlern die Verschränkung auswaschen, und die Ausgabe wird wieder einfach klassisch zu simulieren sein.
Aber dazwischen liegt eine Goldilocks-Zone. Vor dem neuen Papier war es noch eine Möglichkeit, dass der Quantenvorteil hier überleben könnte, auch wenn die Anzahl der Qubits zunahm. In diesem Fall mit mittlerer Tiefe erhöhen Sie die Schaltungstiefe extrem langsam, wenn die Anzahl der Qubits wächst: Auch wenn die Ausgabe durch Fehler stetig verschlechtert wird, kann es immer noch schwierig sein, jeden Schritt klassisch zu simulieren.
Das neue Papier schließt diese Lücke. Die Autoren leiteten einen klassischen Algorithmus zur Simulation von Random Circuit Sampling ab und bewiesen, dass seine Laufzeit eine Polynomfunktion der Zeit ist, die benötigt wird, um das entsprechende Quantenexperiment durchzuführen. Das Ergebnis schmiedet eine enge theoretische Verbindung zwischen der Geschwindigkeit klassischer und quantenmechanischer Ansätze zur Zufallsschaltungsabtastung.
Der neue Algorithmus funktioniert für eine große Klasse von Schaltungen mittlerer Tiefe, aber seine zugrunde liegenden Annahmen brechen für bestimmte flachere zusammen und hinterlassen eine kleine Lücke, in der effiziente klassische Simulationsmethoden unbekannt sind. Aber nur wenige Forscher hegen die Hoffnung, dass sich zufällige Schaltungsabtastungen in diesem verbleibenden schmalen Fenster als schwierig erweisen werden, klassisch zu simulieren. „Ich gebe ziemlich kleine Chancen“, sagte er Bill Feffermann, Informatiker an der University of Chicago und einer der Autoren des Theoriepapiers von 2019.
Das Ergebnis deutet darauf hin, dass die zufällige Schaltungsabtastung nach den strengen Standards der Theorie der Rechenkomplexität keinen Quantenvorteil bringt. Gleichzeitig verdeutlicht es, dass polynomiale Algorithmen, die Komplexitätstheoretiker wahllos effizient nennen, in der Praxis nicht unbedingt schnell sind. Der neue klassische Algorithmus wird mit abnehmender Fehlerrate zunehmend langsamer, und bei den niedrigen Fehlerraten, die in Quantenüberlegenheitsexperimenten erreicht werden, ist er viel zu langsam, um praktikabel zu sein. Ohne Fehler bricht es vollständig zusammen, sodass dieses Ergebnis nichts widerspricht, was die Forscher darüber wussten, wie schwierig es ist, im idealen, fehlerfreien Fall eine zufällige Schaltungsabtastung klassisch zu simulieren. Sergio Boixo, der Physiker, der Googles Quantenüberlegenheitsforschung leitet, sagt, er betrachte das Papier „eher als eine schöne Bestätigung der zufälligen Schaltungsabtastung als alles andere“.
In einem Punkt sind sich alle Forscher einig: Der neue Algorithmus unterstreicht, wie entscheidend die Quantenfehlerkorrektur für den langfristigen Erfolg des Quantencomputings sein wird. „Das ist am Ende des Tages die Lösung“, sagte Fefferman.
