Folgen von

32

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)2n2n
  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 PSEINTSEINTBQ.PNPBQ.P

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?SEINT
Giorgio Camerani
quelle
1
@Walther: Ich stelle fest, dass Sie die Frage aktualisiert haben, um das Bit über eine exponentielle Beschleunigung hinzuzufügen, aber ehrlich gesagt ist die Unterscheidung zwischen polynomieller und exponentieller Beschleunigung etwas künstlich, und so sehe ich dies in keiner Weise wirklich als Einfluss auf die Physik.
Joe Fitzsimons
@Joe: Ich habe dieses Bit nur hinzugefügt, um zu verdeutlichen, was ich vorhatte, als ich die Frage gestellt habe (dh, dass Quanten in dem Sinne, dass erstere NP-vollständige Probleme in der Polynomzeit lösen würden, mächtiger als klassische Quanten) Letzteres noch nicht oder nie). Aber jetzt sehe ich, dass, wenn jemand die aktuelle Version der Frage liest und dann Ihre Antwort liest, er möglicherweise irregeführt ist und denkt, dass ein Satz in Ihrer Antwort falsch ist: Deshalb werde ich dieses Bit entfernen.
Giorgio Camerani
Entschuldigung, ich wollte nicht vorschlagen, dass Sie es umformulieren.
Joe Fitzsimons
@ Joe: Nein, mach dir keine Sorgen! ;-) Wirklich, ich möchte nicht, dass die Frage und ihre Antworten falsch sind: Es wäre verwirrend für die Leser und ungerecht für diejenigen, die geantwortet haben.
Giorgio Camerani
1
SEP Artikel .
Kaveh

Antworten:

18

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.

Joe Fitzsimons
quelle
16

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.

Niel de Beaudrap
quelle
1
Sicher, Möglichkeit # 2 ist nicht eine lächerliche Möglichkeit (auch, muss ich betonen, in der hypothetischen Situation , dass NPBQP ). Ihr Argument könnte aber auch verwendet werden, um für die Nummer 1 zu argumentieren. Bei einer Auswahl zwischen den drei Möglichkeiten wähle ich # 3, weil es die konservativste Möglichkeit ist. aber auch, weil ich es für wichtig halte, hervorzuheben, dass es im Prinzip gute physikalische und empirische Gründe gibt, komplexitätstheoretische Vermutungen anzustellen.
Niel de Beaudrap
3
@ Neil: Ich bin wirklich anderer Meinung. Ich halte es überhaupt nicht für konservativ (eher im Gegenteil), die Quantenmechanik für falsch, weil Quantencomputer leistungsfähig wären. Es gibt einfach keine Beweise für 1, weshalb das Argument nicht zutrifft. Es gibt enorme Belege dafür, dass Quantenberechnung zumindest prinzipiell möglich ist.
Joe Fitzsimons
1
@ Joe: Sicher, unsere QC-Modelle sind ausgezeichnete Abstraktionen von QM (was selbst eine ziemlich gute Theorie ist), soweit wir das beurteilen können. Es lässt auch im Prinzip vernünftige Fehlergrenzen zu und hofft auf eine kompositorische Fehlerkorrektur. Aber es ist schon schwer genug, alle Teile in Position zu bringen, um geräuschlose Operationen zu erzielen, nicht wahr? Auf jeden Fall sprechen wir hier von Kontrafakten, und die Bedingung hier ist ein Trottel - können Sie mir sagen, dass ein Ergebnis wie NPBQP Ihnen keine Pause geben würde, um zu denken, dass vielleicht ein großer Haken auf Sie wartet für QC irgendwo?
Niel de Beaudrap
2
3
@Neil: Eigentlich scheint jetzt 2 der Fall zu sein. Ich bezweifle wirklich BQP = P , so dass Quantenschaltungen klassisch wahrscheinlich nicht effizient simuliert werden können. Es gibt jedoch alle Anzeichen dafür, dass wir tatsächlich Quantencomputer bauen können (obwohl es schwierig ist!).
Joe Fitzsimons