vs

Das zentrale Problem der Komplexitätstheorie ist wohl vs N P .$P$$NP$

Da die Natur jedoch ein Quant ist, erscheint es natürlicher, die Klassen (dh Entscheidungsprobleme, die von einem Quantencomputer in polynomieller Zeit mit einer Fehlerwahrscheinlichkeit von höchstens 1/3 für alle Fälle gelöst werden können) und Q M A zu betrachten (das Quantenäquivalent von N P ) statt.$BQP$$QMA$$NP$

Meine Fragen:

1) Würde eine Lösung für das vs N P- Problem eine Lösung für B Q P vs Q M A geben ?$P$$NP$$BQP$$QMA$

2) Treffen die drei Barrieren der Relativierung, der natürlichen Beweise und der Algebrierung auch auf das Problem vs Q M A zu?$BQP$$QMA$

1) In keiner Richtung sind Implikationen bekannt. Wir wissen, dass P = NP P = PH impliziert. Aber wir wissen nicht, ob BQP und QMA in PH sind, also könnte P vielleicht gleich NP sein, aber BQP und QMA würden immer noch nicht zusammenbrechen. (Andererseits ist zu beachten, dass QMA⊆PP⊆P ^#P , also mit Sicherheit P = P ^#P BQP = QMA implizieren würde.) Zu zeigen, dass BQP = QMA P = NP impliziert, erscheint nach dem gegenwärtigen Kenntnisstand noch hoffnungsloser .

2) Absolut, alle drei Barrieren gelten mit voller Wucht für BQP vs. QMA (und sogar für das "einfachere" Problem, P ≠ PSPACE zu beweisen). Erstens haben wir im Vergleich zu einem PSPACE-Orakel (oder sogar der geringen Ausdehnung eines PSPACE-Orakels) Folgendes

P = NP = BQP = QMA = PSPACE,

Daher werden sicherlich nicht-relativierende und nicht-algebrierende Techniken benötigt, um eine dieser Klassen zu trennen. Zweitens benötigen Sie nur eine Pseudozufallsfunktionsfamilie, die in BQP berechenbar ist. Dies ist eine formal schwächere Anforderung als eine Pseudozufallsfunktionsfamilie, die in P berechenbar ist.

Nachtrag: Lassen Sie mich etwas über eine "Metafrage" sagen, die Sie nicht gestellt, sondern angedeutet haben, warum sich die Leute immer noch auf P vs. NP konzentrieren, obwohl wir glauben, dass die Natur ein Quant ist. Persönlich habe ich P vs. NP immer als das "Flaggschiff" für eine ganze Reihe von Barrierefragen in der Komplexitätstheorie gesehen (P vs. PSPACE, P vs. BQP, NP vs. coNP, NP vs. BQP, die Existenz von Einwegfunktionen, etc), keinevon denen wir zu beantworten wissen und die alle in dem Sinne zusammenhängen, dass jeder Durchbruch mit dem einen sehr wahrscheinlich zu Durchbrüchen mit den anderen führen würde (auch wenn wir keine formalen Implikationen zwischen den Fragen haben, die wir in vielen Fällen haben machen). P vs. NP ist von Natur aus nicht grundlegender als alle anderen - aber wenn wir eine Frage auswählen müssen, um als Aushängeschild für die Komplexität zu dienen, ist dies eine gute Wahl.