Unitary complexity in polynomial space

In der Welt der Informatik gibt es eine fundamentale Kluft zwischen dem, was eine Maschine schnell tun kann, und dem, was sie tun kann, wenn ihr ein riesiger Anteil an Speicher zur Verfügung steht. Seit Jahrzehnten kartieren Computerwissenschaftler diese Territorien und erstellen Kategorien für Probleme, die leicht zu lösen sind, Probleme, die schwer zu lösen sind, und Probleme, die innerhalb eines vernünftigen Zeitrahmens scheinbar unmöglich zu lösen sind. Eine zentrale Frage in diesem Feld ist, ob die Fähigkeit, mehr Speicher zu nutzen, es einem Computer ermöglicht, Probleme zu lösen, die für einen Computer mit begrenzter Zeit absolut unerreichbar sind. Obwohl wir starke Vermutungen über die Antworten haben, bleiben viele dieser Fragen unbewiesen.

Parallel zu dieser klassischen Welt existiert das Reich des Quantencomputings, in dem Maschinen die seltsamen Eigenschaften von subatomaren Teilchen nutzen, um Informationen zu verarbeiten. Hier gelten andere Regeln. Ein Quantencomputer manipuliert nicht nur Bits, die an oder aus sind; er manipuliert komplexe Wahrscheinlichkeitswellen. Dies ermöglicht es ihm, bestimmte Aufgaben auszuführen, für die ein klassischer Computer eine Ewigkeit benötigen würde. Dennoch besteht ein tiefes Mysterium fort: Beruht die Kraft des Quantencomputings auf einer völlig neuen Art von Komplexität, oder ist sie im Grunde nur eine sehr effiziente, getarnte Version des klassischen Computings? Insbesondere haben sich Forscher gefragt, ob jede mögliche Operation, die ein Quantencomputer ausführen kann, in eine Sequenz von Schritten zerlegt werden kann, die ein klassischer Computer schließlich mit den richtigen Hinweisen verstehen könnte. Wenn die Antwort ja lautet, dann wäre die einzigartige Kraft der Quantenkryptographie eine Illusion. Wenn die Antwort nein lautet, dann besitzen Quantencomputer eine fundamentale Stärke, die klassische Maschinen niemals replizieren können.

Zwei Forscher, William Kretschmer und Ewin Tang, haben kürzlich einen bedeutenden Schritt zur Klärung dieser Ungewissheit unternommen. Sie haben das Mysterium nicht vollständig gelöst, aber sie haben eine kraftvolle logische Brücke konstruiert, die die Existenz sicherer Quantenkryptographie mit einigen der ältesten, hartnäckigsten ungelösten Problemen der klassischen Informatik verbindet. Ihre Arbeit legt nahe, dass, falls sichere Quantenkryptographie in der realen Welt existiert, eines von zwei Dingen wahr sein muss: Entweder gibt es eine fundamentale Grenze dafür, wie gut wir Quantenoperationen in klassische Instruktionen übersetzen können, oder eine spezifische, jahrzehntealte Frage über die Leistungsfähigkeit klassischer Computer muss eine überraschende Antwort erhalten.

Um ihre Errungenschaft zu verstehen, muss man zuerst die Natur der Aufgabe erfassen, die sie analysieren. Stellen Sie sich einen Quantencomputer als ein Gerät vor, das ein komplexes, mehrdimensionales Objekt auf eine perfekt reversible Weise rotieren kann. Das „Unitary Synthesis Problem“ fragt, ob wir für eine solche Rotation eine Menge klassischer Instruktionen finden können, die ein Standardcomputer befolgen könnte, um diese Rotation zu reproduzieren. Wenn wir dies immer tun könnten, würde dies bedeuten, dass die Quantenwelt in gewisser Weise nur eine sehr komplizierte Version der klassischen Welt ist. Die Forscher konzentrierten sich auf eine spezifische Klasse dieser Rotationen: jene, die ein Quantencomputer unter Verwendung einer angemessenen Menge an Speicher ausführen kann. Sie fragten, ob diese spezifischen Rotationen immer durch einen klassischen Computer mit Hilfe einer Oracle synthetisiert werden könnten – was im Wesentlichen ein magischer schwarzer Kasten ist, der spezifische Fragen augenblicklich beantworten kann.

Die Autoren begannen damit, eine praktische Hürde anzugehen: Wie definiert man diese Quantenaufgaben präzise? Frühere Versuche, sie zu kategorisieren, hatten zu verwirrenden Ergebnissen geführt, teilweise weil sie zuließen, dass „Müll“ (Garbage) während der Berechnung zurückblieb. Im Quantencomputing hinterlässt eine Maschine bei der Durchführung einer Berechnung oft zusätzliche Daten, die nicht mehr benötigt werden, aber nicht einfach gelöscht werden können, ohne das Ergebnis zu stören. Einige Definitionen erlaubten diese unordentlichen Überreste, während andere einen perfekt sauberen Prozess verlangten. Kretschmer und Tang zeigten, dass dieser Unterschied bei Aufgaben mit großen Mengen an Speicher nicht von Bedeutung ist. Sie bewiesen, dass jeder unordentliche, Müll hinterlassende Quantenprozess in einen sauberen, Müll-freien Prozess umgewandelt werden kann, ohne die fundamentale Schwierigkeit der Aufgabe zu verändern. Dies war ein entscheidender Schritt, da es ihnen ermöglichte, diese komplexen Quantenoperationen mit einem Maß an mathematischer Klarheit zu behandeln, das zuvor gefehlt hatte.

Mit diesen Definitionen widmeten sie sich der Kernfrage. Sie demonstrierten, dass für jede Quantenoperation, die mit polynomiellem Platz (einer handhabbaren Menge an Speicher) ausgeführt werden kann, nur zwei Möglichkeiten bestehen. Entweder ist die Operation so komplex, dass kein klassischer Computer, egal wie clever er ist oder wie viel Hilfe er von einer Oracle erhält, sie jemals effizient synthetisieren kann. Oder die Operation ist gar nicht so schwer; sie kann effizient synthetisiert werden, wenn der klassische Computer die Erlaubnis hat, Fragen zu einer spezifischen Art von schwierigem Problem zu stellen, die als NEXP-Suchproblem bekannt ist. Diese zweite Kategorie stellt eine sehr hohe Hürde in der klassischen Komplexitätstheorie dar und repräsentiert Probleme, die exponentiell schwerer sind als die schwierigsten Probleme, die wir derzeit lösen können.

Die Implikationen dieser Erkenntnis sind tiefgreifend, insbesondere für die Zukunft der Kryptographie. Quantenkryptographie beruht auf der Idee, dass bestimmte Aufgaben, wie etwa das Erstellen eines sicheren Commitment-Schemas (eine Methode, um ein Geheimnis in einer digitalen Box zu verschließen, sodass es weder geändert noch eingesehen werden kann), für einen Angreifer unmöglich zu brechen sind. Wenn sichere Quanten-Commitments existieren, diktiert die Logik der Forscher, dass wir uns in einer ganz spezifischen Situation befinden. Entweder hat das Unitary Synthesis Problem eine negative Antwort, was bedeutet, dass es Quantenoperationen gibt, die der klassischen Synthese fundamental entzogen sind, oder eine große klassische Komplexitätsfrage muss gelöst werden. Speziell würde es implizieren, dass eine Klasse von Problemen namens BPP (Probleme, die schnell mit Zufallschancen lösbar sind) nicht gleich NEXP (Probleme, die mit exponentieller Zeit und Nichtdeterminismus lösbar sind) ist. Dies ist eine Frage, die seit über vierzig Jahren offen steht.

Einfacher ausgedrückt argumentiert die Arbeit, dass der Beweis für die Existenz sicherer Quantenkryptographie nicht nur eine Frage des Bauens besserer Quantengeräte ist. Er ist untrennbar mit den tiefsten theoretischen Grenzen der klassischen Informatik verbunden. Wenn wir die Existenz sicherer Quanten-Commitments unbedingt beweisen könnten, müssten wir gleichzeitig eine von zwei massiven, jahrzehntealten Rätseln der Informatik beantworten. Wir müssten entweder akzeptieren, dass Quantenoperationen fundamental schwerer zu simulieren sind, als wir dachten, oder wir müssten beweisen, dass eine spezifische, unglaublich leistungsfähige Art der klassischen Berechnung strikt fähiger ist als eine Standard-Randomized-Berechnung.

Die Arbeit beleuchtet auch das Verhältnis zwischen Quanten- und klassischer Leistungsfähigkeit in einem allgemeineren Sinne. Die Autoren zeigten, dass, falls wir davon ausgehen, dass das Unitary Synthesis Problem eine positive Antwort hat (dass alles synthetisiert werden kann), die Kraft von Quantencomputern mit großem Speicher eng durch die Kraft klassischer Computer begrenzt ist, die NEXP-Suchprobleme lösen. Dies deutet darauf hin, dass die „Magie“ des Quantencomputings, falls sie existiert, kein frei schwebendes Phänomen ist, sondern tief in der Struktur der klassischen Komplexität verwurzelt ist. Wenn Quantencomputer etwas wirklich Neues tun können, dann deshalb, weil sie auf eine Ebene der Schwierigkeit zugreifen, die klassische Computer selbst mit den besten Abkürzungen nicht erreichen können.

Letztendlich sagt uns diese Forschung nicht, ob die Quantenkryptographie sicher ist oder ob das Unitary Synthesis Problem lösbar ist. Stattdessen kartiert sie das Gelände zwischen diesen beiden Möglichkeiten. Sie zeigt auf, dass der Weg zum Beweis der Sicherheit von Quantensystemen durch dieselben Mauern blockiert ist, die Komplexitätstheoretikern seit einem halben Jahrhundert die Lösung ihrer schwierigsten Probleme verwehrt haben. Die Arbeit legt nahe, dass wir nicht einfach den Weg zu einem Beweis bauen können; wir müssen zuerst die fundamentalen Grenzen der Berechnung selbst verstehen. Durch die Klärung der Definitionen und die Etablierung dieser strengen Verbindungen haben Kretschmer und Tang eine klarere Sicht auf die Landschaft geschaffen und gezeigt, dass das Schicksal der Quantenkryptographie und das Bestimmung der klassischen Komplexitätstheorie auf eine Weise miteinander verwoben sind, die zuvor nicht verstanden wurde.