Folgen von

Als TCS-Amateur lese ich populäres, sehr einführendes Material zum Thema Quantencomputing. Hier sind die wenigen grundlegenden Informationen, die ich bisher gelernt habe:

1. Es ist nicht bekannt, dass Quantencomputer NP-vollständige Probleme in der Polynomzeit lösen.
2. "Quantenmagie wird nicht genug sein" (Bennett et al. 1997): Wenn Sie die Problemstruktur verwerfen und nur den Raum von möglichen Lösungen berücksichtigen , dann benötigt sogar ein Quantencomputer ungefähr Schritte, um den richtigen zu finden (mit dem Algorithmus von Grover)$2^n$$\sqrt{2^n}$
3. Wenn jemals ein Quantenpolynom-Zeit-Algorithmus für ein NP-vollständiges Problem gefunden wird, muss er die Problemstruktur auf irgendeine Weise ausnutzen (andernfalls würde Bullett 2 widersprochen).

Ich habe einige (grundlegende) Fragen, die bisher noch niemand auf dieser Website gestellt zu haben scheint (vielleicht, weil sie grundlegend sind). Angenommen, jemand findet einen Algorithmus für die begrenzte Fehlerquantenpolynomzeit für (oder ein anderes NP-vollständiges Problem), wodurch in und impliziert wird .S A T B Q P N P ⊆ B Q $SAT$$SAT$$BQP$$NP \subseteq BQP$

Fragen

1. Was wären die theoretischen Konsequenzen einer solchen Entdeckung? Wie würde sich das Gesamtbild der Komplexitätsklassen auswirken? Welche Klassen würden welchen anderen gleichgestellt?
2. Ein solches Ergebnis scheint darauf hinzudeuten, dass Quantencomputer von Natur aus überlegen sind als klassische Computer. Was wären die Konsequenzen eines solchen Ergebnisses für die Physik? Würde es etwas Licht auf ein offenes Problem in der Physik werfen? Würde sich die Physik nach einem ähnlichen Ergebnis ändern? Wäre das physikalische Gesetz, wie wir es kennen, betroffen?
3. Die Möglichkeit (oder auch nicht), die Problemstruktur allgemein genug (dh instanzunabhängig) auszunutzen, scheint der Kern der P = NP-Frage zu sein. Wenn nun ein Zeitquantenalgorithmus mit beschränktem Fehlerpolynom für gefunden wird und er die Problemstruktur ausnutzen muss , wäre seine Strukturausnutzungsstrategie dann nicht auch im klassischen Szenario anwendbar? Gibt es Hinweise darauf, dass eine solche Strukturausnutzung für Quantencomputer möglich sein könnte, für klassische jedoch unmöglich bleibt?$SAT$

Ich werde nicht versuchen, die erste Frage zu beantworten, da jemand wie Scott Aaronson, Peter Shor oder John Watrous Ihnen in dieser Hinsicht zweifellos eine weitaus umfassendere Antwort geben kann.

In Bezug auf Frage 2 ist zu beachten, dass Quantencomputer in vielen Fällen leistungsstärker sind als klassische Computer:

1. Es gibt eine ziemlich allgemeine polynomielle Beschleunigung, die von Quantencomputern gegenüber klassischen Computern in einer Reihe von Problemen erzielt wird. Aus Sicht der Komplexität ist dies vielleicht weniger interessant als eine exponentielle Beschleunigung, aber wir können dies tatsächlich beweisen.
2. Die Komplexität der Quantenkommunikation kann für dasselbe Problem häufig erheblich von der klassischen Kommunikationskomplexität abweichen. Auch dies kann nachgewiesen werden (siehe zum Beispiel das Mermin-GHZ-Spiel).
3. Quantenabfragen an Orakel sind sehr oft weitaus leistungsfähiger als klassische Abfragen an dasselbe Orakel (siehe zum Beispiel den Deutsch-Josza-Algorithmus).

Vor diesem Hintergrund ist bereits bekannt, dass Quantencomputer grundsätzlich leistungsstärker sind als klassische Computer. Ich denke, ich würde zu Recht sagen, dass die Mehrheit der Physiker, die an solchen Dingen arbeiten, bereits davon ausgehen würde, dass es nicht möglich ist, einen klassischen Algorithmus zu finden, mit dem jedes Quantensystem effizient simuliert werden kann, und dass NP in BQP enthalten ist wäre sicherlich überraschend, wäre es nicht besonders wahrscheinlich, einen Durchbruch beim Verständnis eines bestimmten physikalischen Phänomens zu erzielen. Vielmehr würde dies einen etwas stärkeren Beweis dafür liefern, dass die Quantenphysik schwer zu simulieren ist.

Es gibt keine fundamentale Physik, die von der Komplexität der Simulation abhängt. Die Suche nach einem effizienten Quantenalgorithmus für ein NP-vollständiges Problem hätte keine fundamentalen Konsequenzen für die Richtigkeit unseres gegenwärtigen Verständnisses der Funktionsweise des Universums (obwohl ich geneigt bin) (um Scott Aaronsons Vorschlag zuzustimmen, dass es interessant ist zu sehen, ob sich aus rechnerischen Annahmen physikalische Gesetze ergeben könnten).

Es ist äußerst verlockend zu sagen, dass dies Konsequenzen für die adiabatische Entwicklung von Quantensystemen haben würde (und ich vermute, Sie könnten eine oder zwei Antworten darauf erhalten), aber dies wäre falsch, da sie von einem bestimmten physikalischen Prozess gesteuert werden , und damit zu zeigen, dass es prinzipiell möglich ist, SAT in polynomialer Zeit auf einem Quantencomputer zu lösen, würde nichts über ihre spezifische Entwicklung aussagen.

Zu Ihrer letzten Frage haben wir bereits Beispiele, bei denen die Problemstruktur genutzt wird, um einen Polynomquantenalgorithmus zu erhalten, die jedoch nicht zu einem solchen klassischen Algorithmus führen (z. B. Faktorisierung). Nach unserem derzeitigen Verständnis bedeutet ein Problem mit einer Struktur, die ausgenutzt werden kann, um einen polynomiellen Zeitquantenalgorithmus zu erhalten, nicht, dass die Struktur ausgenutzt werden kann, um einen klassischen polynomiellen Zeitalgorithmus zu erhalten.

Scott Aaronson hat oft gern darauf hingewiesen (und weist wahrscheinlich immer noch gern darauf hin, vorausgesetzt, er ist es nicht müde, dies zu tun), dass physikalische Prozesse nicht immer das globale Minimum einer Energielandschaft finden . Insbesondere wenn Sie eine Instanz eines NP- vollständigen Optimierungsproblems als ein Energie-Minimierungsproblem für ein physikalisches System formulieren , gibt es keinen Grund - weder theoretisch noch empirisch - anzunehmen, dass sich ein solches physikalisches System danach "entspannt" einige Zeit zu einer Lösung des Problems ( dh  eine Energiekonfiguration, die ein globales Minimum ist). Es wird sich mit größerer Wahrscheinlichkeit auf ein lokales Minimum beschränken: eine, bei der geringfügig unterschiedliche Konfigurationen mehr Energie erfordern, bei der jedoch eine wesentlich andere Konfiguration möglicherweise weniger Energie hat.

Der Beweis, dass NP  ⊆  BQP ein Triumph erster Ordnung ist - für alle Komplexitätstheoretiker, nicht nur für Quantenberechnungstheoretiker -, lässt also vermuten, dass es eine völlig neue Theorie "physikalischer" Berechnungsmodelle gibt, die darauf wartet, entdeckt zu werden. Warum? Nun, Rechenmodelle können als physikalische Modelle (wenn auch hochspezialisierte) ausgelegt werden: Welche Rechenressourcen sind physikalisch sinnvoll? Einer der Slogans "der Quantenberechnung ist , dass Nature isn't classical, [darn] it^† - so , wenn Sie die Quantenmechanik auf einem klassischen Computer simulieren können, was man physisch effizient berechnen kann als fast sicher ist mächtiger P . Und doch haben wir Beweise dafür, dass es weniger mächtig als NP ist; es müsste also auch weniger mächtig sein als BQP , wenn es so wäre, dass NP  ⊆  BQP .

Ein Beweis von NP  ⊆  BQP würde uns also ein Trilemma liefern: entweder

1. Quantenschaltungen können auf einem klassischen Computer effizient simuliert werden, wodurch NP  ⊆  BQP  ⊆  P bewiesen wird und die wildesten Träume und Albträume jedes Theoretikers übertroffen werden.
2. Quantenschaltungen können auf einem klassischen Computer nicht simuliert werden, aber skalierbare Quantencomputer können gebaut werden, um Probleme in NP zu lösen , was zu einem wirklich explosiven Interesse an Quantencomputern führt und dafür sorgt, dass experimentelle Physiker auf absehbare Zeit berufliche Sicherheit haben.
3. Es gibt ein weiteres Modell der Berechnung, das entdeckt werden muss und zwischen P und BQP liegt und beschreibt (oder besser approximiert ), was physikalisch effizient berechenbar ist.

Ich vermute, dass das kluge Geld auf Platz 3 landen würde, so unterhaltsam, wie entweder Nummer 1 oder Nummer 2 aus akademischer Sicht wäre.

^†  Mit Entschuldigungen an Feynman, den ich vermute, hat er seine Flüche nicht oft gehackt.