Gibt es Ergebnisse von Quantenalgorithmen oder Komplexität, die zu Fortschritten beim P vs NP-Problem führen?

An der Oberfläche haben Quantenalgorithmen wenig mit klassischem Rechnen und insbesondere P vs NP zu tun: Die Lösung von Problemen aus NP mit Quantencomputern sagt nichts über die Beziehungen dieser klassischen Komplexitätsklassen aus ¹ .

Andererseits wird die in diesem Artikel vorgestellte "alternative Beschreibung" der klassischen Komplexitätsklasse PP als Klasse PostBQP meines Wissens als wichtiges Ergebnis für die "klassische Komplexität" angesehen, und zwar als "Quantenkomplexität". .

Tatsächlich schreibt Scott Aaronson, der Autor des Artikels, am Ende des Abstracts:

Dies zeigt, dass Quantencomputing neue und einfachere Beweise für wichtige Ergebnisse der klassischen Berechnung liefern kann.

Meine Frage lautet daher: Gibt es Ergebnisse aus dem Bereich der Quantenkomplexität, die das P-gegen-NP-Problem "vereinfachen", ähnlich wie bei der Quantenbeschreibung von PP? Wenn es solche Ergebnisse nicht gibt, gibt es einen guten Grund, diese Ergebnisse trotz des „Erfolgs“ für PP nicht zu erwarten?

_{1: Nehmen Sie die Antwort auf diese Frage, zum Beispiel: Würde das P vs. NP-Problem durch die Entwicklung universeller Quantencomputer trivial werden?}

Ich glaube nicht, dass es eindeutige Gründe für eine Ja- oder Nein-Antwort gibt. Ich kann jedoch einen Grund angeben, warum PP eine solche Charakterisierung viel wahrscheinlicher zugab als NP , und eine Vorstellung davon, warum NP niemals eine einfache Charakterisierung in Bezug auf die Modifikation des Quantenrechenmodells haben könnte.

Komplexität zählen

Die Klassen NP und PP können beide anhand der Anzahl der akzeptierenden Zweige einer nicht deterministischen Turing-Maschine charakterisiert werden, die wir in Bezug auf die möglichen Ergebnisse einer randomisierten Berechnung, die verwendet, bodenständiger beschreiben können gleichmäßig zufällige Bits. Wir können diese beiden Klassen dann beschreiben als:

• L  ∈  NP, wenn es einen polynomzeit-randomisierten Algorithmus gibt, der ein einzelnes Bit α  ∈ {0,1} ausgibt , so dass x  ∈  L genau dann, wenn Pr [  α  = 1 | x  ] ist nicht Null (obwohl diese Wahrscheinlichkeit winzig sein kann), im Gegensatz zu Null.

• L  ∈  PP, wenn es einen polynomzeit-randomisierten Algorithmus gibt, der ein einzelnes Bit α  ∈ {0,1} ausgibt , so dass x  ∈  L genau dann, wenn Pr [  α  = 1 | x  ] ist größer als 0,5 (wenn auch möglicherweise nur um den kleinsten Betrag) und nicht gleich oder kleiner als 0,5 ( z. B.  um einen winzigen Betrag).

Eine Möglichkeit zu erkennen, warum diese Klassen mit dieser probabilistischen Beschreibung nicht praktisch gelöst werden können, besteht darin, dass exponentiell viele Wiederholungen erforderlich sind, um eine Wahrscheinlichkeitsschätzung für Pr [  α  = 1 | x  ] wegen der Kleinheit der Unterschiede in den beteiligten Wahrscheinlichkeiten.

Lückenkomplexität und Quantenkomplexität

Beschreiben wir die Ergebnisse "0" und "1" in der obigen Berechnung als "ablehnen" und "akzeptieren"; und nennen wir eine zufällige Verzweigung, die ein Zurückweisungs- / Akzeptanzergebnis ergibt, eine zurückweisende oder akzeptierende Verzweigung. Da also jeder Zweig der randomisierten Berechnung, der nicht akzeptiert, ablehnt, kann PP auch als Differenz zwischen der Anzahl der akzeptierenden und der Anzahl der abgelehnten Rechenpfade definiert werden - eine Größe, die wir als Akzeptanzlücke bezeichnen können : nämlich, ob die Akzeptanz Lücke ist positiv oder kleiner oder gleich Null. Mit ein wenig mehr Arbeit können wir eine äquivalente Charakterisierung für erhalten PP erhaltenin Bezug darauf, ob die Akzeptanzlücke größer als ein Schwellenwert oder kleiner als ein Schwellenwert ist, der Null oder irgendeine andere effizient berechenbare Funktion der Eingabe x sein kann .

Dies kann wiederum verwendet werden, um Sprachen in PP hinsichtlich der Quantenberechnung zu charakterisieren . Aus der Beschreibung von PP in Bezug auf randomisierte Berechnungen mit Akzeptanzwahrscheinlichkeiten (möglicherweise geringfügig) größer als 0,5 oder höchstens 0,5 lassen alle Probleme in PP einen Polynom-Zeit-Quantenalgorithmus zu, der die gleiche Unterscheidung in Akzeptanzwahrscheinlichkeiten aufweist; und indem wir Quantenberechnungen als Summe über Rechenpfade modellieren und diese Pfade simulieren, indem wir Verzweigungen für Pfade mit negativem Gewicht ablehnen und Verzweigungen für Pfade mit positivem Gewicht akzeptieren, können wir auch zeigen, dass ein solcher Quantenalgorithmus eine (statistisch schwache) Unterscheidung beschreibt ein Problem in PP .

Es ist nicht offensichtlich, dass wir dasselbe für NP tun können . Es gibt keine natürliche Möglichkeit, NP in Bezug auf Akzeptanzlücken und die offensichtliche Vermutung, wie Sie versuchen könnten, es in das Quantenberechnungsmodell einzufügen, zu beschreiben - indem Sie fragen, ob die Wahrscheinlichkeit für die Messung eines Ergebnisses '1' Null ist oder nicht. Null - stattdessen erhalten Sie eine Klasse mit dem Namen coC ₌ P , von der nicht bekannt ist, dass sie NP entspricht , und sie kann grob als ungefähr so ​​leistungsfähig wie PP und nicht als nahe an NP beschrieben werden .

Natürlich könnte man eines Tages eine Charakterisierung von NP in Bezug auf Akzeptanzlücken finden oder neue Wege finden, um Quantenberechnung mit der Zählung von Komplexität in Beziehung zu setzen, aber ich bin nicht sicher, ob irgendjemand eine überzeugende Vorstellung davon hat, wie dies zustande kommen könnte.

Zusammenfassung

Die Perspektiven für Einblicke in die P im Vergleich zu NP Problem selbst, über Quantencomputer sind nicht vielversprechend - aber es ist nicht unmöglich.