Unitary RQL Equals RQL

Quantencomputer werden oft als Maschinen vorgestellt, die viele Möglichkeiten gleichzeitig halten und eine weite Landschaft von Ergebnissen simultan erkunden. Um diese Kraft nutzen zu können, muss ein Computer in der Lage sein, seinen Fortschritt entlang des Weges zu überprüfen, Pfade, die ins Nichts führen, zu verwerfen und die Ressourcen auf diejenigen zu konzentrieren, die vielversprechend aussehen. In der Sprache der Quantenphysik wird dieser Prüfprozess als Messung bezeichnet. Es ist der Akt, eine Information anzusehen, was das System dazu zwingt, sich für einen definitiven Zustand zu entscheiden, und es dem Computer ermöglicht, den Rest wegzuwerfen. Jahrzehntelang ist eine grundlegende Frage in der Untersuchung darüber, wie viel Speicher diese Maschinen benötigen, in der Luft gelegen: Wenn ein Computer erlaubt ist, seinen Fortschritt zu betrachten und Informationen unterwegs zu verwerfen, wird er dadurch leistungsfähiger als ein Computer, der gezwungen ist, bis zum ganz am Ende zu warten, um nachzusehen?

Die Antwort hängt stark von den Regeln des Spiels ab. Wenn der Computer erlaubt ist, auf beiden Seiten Fehler zu machen – also manchmal „Ja“ zu sagen, wenn es eigentlich „Nein“ heißen sollte, und umgekehrt – wussten Forscher bereits, dass die Fähigkeit, frühzeitig zu messen, tatsächlich keinen Vorteil bringt. Eine Maschine, die bis zum Ende wartet, kann alles tun, was eine Maschine, die früh misst, tun kann, vorausgesetzt, beide erlauben eine kleine Fehlermarge. Eine strengere Version der Regeln ändert jedoch das Bild. In diesem strengeren Szenario ist der Computer verboten, jemals eine bestimmte Art von Fehler zu machen: Er darf niemals „Ja“ sagen, wenn die Antwort eigentlich „Nein“ lautet. Er kann zwar auf der anderen Seite Fehler machen, aber die Kosten eines falsch-positiven Ergebnisses sind null. Für diesen Fall mit einseitigem Fehler war bisher unbekannt, ob die Fähigkeit, frühzeitig zu messen und Informationen zu verwerfen, irgendeinen zusätzlichen Nutzen bietet. Die Frage war, ob eine Maschine, die bei einer „Nein“-Antwort niemals falsch liegen darf, gezwungen werden könnte, bis zum Ende zu warten, ohne ihre Fähigkeit zu verlieren, Probleme effizient zu lösen.

Ein Forscher hat diese Frage nun geklärt und bewiesen, dass die Fähigkeit, frühzeitig zu messen, auch in diesem strengen Szenario nicht hilft. Er zeigte, dass jeder Quantencomputer, der mit begrenztem Speicher arbeitet, keine falsch-positiven „Ja“-Aufrufe tätigt und es erlaubt ist, zwischendurch zu messen, perfekt durch eine Maschine simuliert werden kann, die niemals misst, bis sie den allerletzten Schritt erreicht hat. Die beiden Arten von Maschinen sind in Bezug auf das, was sie lösen können, exakt gleich. Der Forscher hat dies nicht nur vorgeschlagen, sondern er hat einen rigorosen mathematischen Beweis geliefert, der eine spezifische Methode zur Umwandlung der früh messenden Maschine in eine wartende Maschine konstruiert. Dieses Ergebnis gilt für eine Vielzahl von Standard-Quanten-Bausteinen, einschließlich derer, die heute in den gängigsten Designs von Quantencomputern verwendet werden.

Der Kern der Entdeckung liegt darin, wie der Forscher mit den Informationen umging, die normalerweise verworfen würden. In einer Standardberechnung, wenn eine Maschine ein Bit misst und eine Null sieht, könnte sie den Teil des Systems, der eine Eins zeigte, verwerfen. Wenn die Maschine nicht erlaubt ist, früh zu messen, muss sie diesen verworfenen Teil am Leben erhalten, was normalerweise zusätzlichen Speicher erfordert. Der Forscher fand einen Weg, die verworfene Information am Leben zu erhalten, ohne zusätzlichen Speicher zu verwenden, indem er die gesamte Historie der Berechnung als ein einziges, vereintes Objekt behandelte. Er entwickelte eine Technik, die die Beschreibung des gesamten Systems effektiv verdoppelt, jedoch nicht durch das Hinzufügen von physischem Speicher, sondern durch die Reorganisation der Art und Weise, wie die Information gespeichert wird.

Stellen Sie sich eine Berechnung als eine lange Kette von Ereignissen vor. In der alten Denkweise, wenn der Computer ein Glied in der Kette betrachtet und beschließt, es abzuschneiden, wäre dieser Teil der Kette für immer verloren. Die neue Methode hält das abgeschnittene Glied fest verbunden, jedoch auf eine Weise, dass es das Endergebnis nicht beeinflussen kann, es sei denn, die gesamte Kette sollte erfolgreich sein. Der Forscher erreichte dies, indem er einen speziellen „Referenzzustand“ schuf, der das durchschnittliche Verhalten des Systems verfolgt. Er nutzte diese Referenz, um das Gewicht der verschiedenen Teile der Berechnung im Verlauf anzupassen. Diese Anpassung stellte sicher, dass, falls die ursprüngliche Maschine ein Problem abgelehnt hätte, die neue Maschine das Problem ebenfalls mit absoluter Gewissheit ablehnen würde, wodurch die Null-Fehler-Garantie gewahrt blieb. Gleichzeitig stellte die Methode sicher, dass, falls die ursprüngliche Maschine ein Problem akzeptiert hätte, die neue Maschine immer noch eine gute Chance hätte, es zu akzeptieren, obwohl sie gezwungen war, alle verworfenen Informationen mitzuführen.

Der Beweis beinhaltet einen klugen Trick, um mit der Tatsache umzugehen, dass das Behalten aller Informationen normalerweise die beteiligten Zahlen zu groß werden lässt, um sie handhabbar zu halten. Der Forscher führte ein System von Gewichten ein, die sich im Verlauf der Berechnung gegenseitig aufheben. Er fügte dem System bei jedem Schritt ein klein wenig zufälliges Rauschen hinzu, was kontraintuitiv klingt, aber tatsächlich verhindert, dass die Zahlen instabil werden. Dieses Rauschen ermöglicht es ihm, die verschiedenen Teile der Berechnung so zu skalieren, dass sie handhabbar bleiben. Er zeigte dann, dass der Teil der Berechnung, der dem „verworfenen“ Teil der Information entspricht, mithilfe von Standard-Quantengattern simuliert werden kann, sofern diese Gates exakte mathematische Inversen besitzen. Diese Anforderung wird durch die Standard-Gate-Sets erfüllt, die in der meisten Quantenforschung verwendet werden.

Der Forscher untersuchte auch, ob dieses Ergebnis für verschiedene Arten von Quantengattern gilt, einschließlich derer mit komplexeren mathematischen Eigenschaften. Er fand heraus, dass das Ergebnis gilt, solange die Gates zu einer bestimmten Familie von Zahlen gehören, die als CM-Felder bekannt sind. Diese Familie umfasst die Standard-Gates, die in den meisten Quantenalgorithmen verwendet werden, sowie einige exotischere. Dies bedeutet, dass die Erkenntnis nicht auf ein einzelnes, eng gefasstes Design beschränkt ist, sondern einer breiten Klasse potenzieller Quantencomputer Anwendung findet. Der Beweis erstreckt sich auch auf ein verwandtes Szenario, bei dem ein Verifizierer ein Zeugnis prüft, ein Aufbau, der oft in der Kryptographie und Komplexitätstheorie verwendet wird. In diesem Fall zeigte er, dass ein Verifizierer, der eine korrekte Antwort mit perfekter Sicherheit akzeptieren muss, ebenfalls in eine Maschine umgewandelt werden kann, die bis zum Ende wartet, ohne dabei die perfekte Sicherheit zu verlieren.

Diese Arbeit löst ein langjähriges offenes Problem in der Theorie des Quantencomputings. Sie bestätigt, dass die Kraft von Quantencomputern mit begrenztem Speicher nicht aus der Fähigkeit resultiert, ihren Fortschritt zu betrachten und Informationen zu verwerfen. Stattdessen kommt die Kraft aus der zugrunde liegenden Quantenmechanik selbst. Die Fähigkeit, frühzeitig zu messen, ist eine Annehmlichkeit, keine Notwendigkeit, für Maschinen, die bei negativen Antworten strikt korrekt sein müssen. Die Konstruktion des Forschers liefert einen Bauplan dafür, wie eine solche Maschine gebaut werden könnte, und zeigt auf, dass der zusätzliche Speicher, der für diese Umwandlung normalerweise gedacht wird, gar nicht benötigt wird. Das Ergebnis stärkt unser Verständnis der fundamentalen Grenzen der Quantenberechnung und legt nahe, dass die effizientesten Quantenalgorithmen möglicherweise gar nicht auf Zwischenmessungen angewiesen sind.

Die Auswirkungen dieser Entdeckung sind primär theoretischer Natur und helfen dabei, die Landschaft dessen zu kartografieren, was Quantencomputer können und was sie nicht können. Sie klärt die Beziehung zwischen verschiedenen Modellen der Berechnung und beseitigt eine potenzielle Quelle der Verwirrung darüber, woher der Quantenvorteil kommt. Durch den Beweis, dass die beiden Modelle äquivalent sind, hat der Forscher das Werkzeug zur Analyse von Quantenalgorithmen vereinfacht. Zukünftige Arbeiten können sich nun auf die Eigenschaften des Wartemodells konzentrieren, im Wissen, dass jedes dort gefundene Ergebnis gleichermaßen für das flexiblere Messmodell gilt. Die Arbeit behauptet nicht, eine physische Maschine gebaut zu haben, die diese Methode nutzt, noch schlägt sie unmittelbare Änderungen vor, wie heutige Quantencomputer technisch konstruiert werden. Stattdessen bietet sie ein solides mathematisches Fundament, das sicherstellt, dass die theoretischen Grenzen dieser Maschinen gut verstanden sind. Der Beweis ist vollständig und rigoros und lässt keinen Raum für Zweifel an der Äquivalenz dieser zwei Arten, eine Quantenberechnung unter den spezifizierten Einschränkungen durchzuführen.