Quantenalgorithmen für Probleme außerhalb von NP

8

Was ist über Quatum-Algorithmen für Probleme außerhalb von NP bekannt (z. B. NEXP-vollständige Probleme), sowohl theoretisch wie obere und untere Geschwindigkeitsbeschränkungen und verschiedene (Un-) Möglichkeitsergebnisse, als auch über konkrete Algorithmen für bestimmte Probleme?

Der Grund, den ich frage, ist, dass wir derzeit Processorrs mit niedrigen Qubits von 10 haben. NP-Probleme über niedrige 10s klassischer Bits können im Allgemeinen auf klassischen Computern gelöst werden. Bei Nicht-NP-Problemen könnten Probleme auftreten, die selbst in diesem Bereich nicht klassisch nachvollziehbar sind. Dies könnte eine Gelegenheit sein, einen praktischen Quantenvorteil auf aktueller Hardware zu demonstrieren. Dies erfordert nicht unbedingt, dass der Quantenalgorithmus im Allgemeinen nachvollziehbar ist, sondern nur, dass er kleinere Probleme in akzeptabler Zeit lösen kann, wo dies bei klassischen Algorithmen nicht möglich ist.

Die Idee ist, Probleme zu finden, die auf klassischen Computern viel Zeit in Anspruch nehmen, beispielsweise Größen, die auf aktuellen Quantenprozessoren darstellbar sind. Das Finden von Quantenalgorithmen, die in diesen Fällen schneller sind, wäre eine Form des Quantenvorteils, selbst wenn die Quantenalgorithmen nicht unbedingt asymptotisch überlegen wären.

algorithm speedup complexity-theory Daniel Mahler
quelle
Suchen Sie etwas, das den Complexity Zoo nachahmt, aber einen engeren Fokus nur für diese wirklich schwierigen Probleme hat?
AHusain
3
Wenn ich mich richtig erinnere, hat die Auswertung des Jones-Polynoms an bestimmten Punkten einen effizienten Quantenalgorithmus, liegt aber nicht innerhalb von NP.
DaftWullie
4
@DaftWullie Die Annäherung des Jones-Polynoms an einen bestimmten Satz von Punkten ist BQP-vollständig, was es außerhalb von NP wahrscheinlich macht, siehe Zusammenfassung von arxiv.org/abs/quant-ph/0511096
Norbert Schuch
1
@DanielMahler Quantencomputer können in PSPACE (genauer in PP) simuliert werden. NEXP ist also unerreichbar. In jedem Fall sind niedrige 10s (<~ 30) immer noch klassisch simulierbar.
Norbert Schuch
1
@NorbertSchuch Fairer Punkt. Ich denke, ich habe möglicherweise sogar außerhalb von BQP gedacht. Asymptotisch quantenunlösbare Probleme, die durch Quantenalgorithmen in angemessener Zeit für N = ~ 30 noch lösbar sind, aber keine klassischen. Diese Frage ist keine theoretisch bedeutsame Frage, da sie sich auf den aktuellen Stand sowohl der Quanten- als auch der klassischen Technologien bezieht. Es könnte immer noch interessant sein, ein Programm zu haben, das selbst bei begrenzten Problemgrößen einen überzeugenden Vorteil zeigt, aber vielleicht auch nicht. Das ist teilweise das, was ich frage.
Daniel Mahler

Antworten:

1

Die Beziehung könnte ein solches Problem sein. Die Frage ist: "Korreliert eine erste Boolesche Funktion stark mit der Fourier-Transformation einer zweiten Booleschen Funktion?" Dies wird mit Quantenabfrage gelöst, aber Aaronson und Ambainis haben gezeigt, dass man klassisch Zufallsabfragen benötigt. 1Ω(N/log⁡N)

Siehe auch den Artikel des Quanta-Magazins - nach der Arbeit von Raz und Tal liegt das Problem wahrscheinlich außerhalb der Polynomhierarchie. In Anbetracht von Norbert Schuchs Kommentar zu kann dies eine so gute Trennung sein, wie erwartet.BQP⊆PSPACE

Mark S.
quelle