Wenn P = NP wahr wäre, wären Quantencomputer nützlich?

29

Angenommen, P = NP ist wahr. Wäre es dann eine praktische Anwendung, einen Quantencomputer zu bauen, um bestimmte Probleme schneller zu lösen, oder wäre eine solche Verbesserung irrelevant, wenn man davon ausgeht, dass P = NP wahr ist? Wie würden Sie die Effizienzverbesserung charakterisieren, die eintreten würde, wenn ein Quantencomputer in einer Welt mit P = NP gebaut werden könnte, im Gegensatz zu einer Welt mit P! = NP?

Hier ist ein Beispiel dafür, wonach ich suche:

Wenn P! = NP, sehen wir, dass die Komplexitätsklasse ABC gleich der Quantenkomplexitätsklasse XYZ ist ... aber wenn P = NP ist, kollabiert die Klasse ABC trotzdem zur verwandten Klasse UVW.

(Motivation: Ich bin neugierig und für Quantencomputer relativ neu. Bitte migrieren Sie diese Frage, wenn sie nicht ausreichend fortgeschritten ist.)

Philip White
quelle
9
Wir wissen nicht , ob impliziert B Q P = P , so dass es möglicherweise ein Problem in seinem B Q P , die nicht in ist P auch wenn P = N P .... Es ist sogar auch eine offene Frage , ob oder nicht B Q P ist in P H ....P=NPBQP=PBQPPP=NPBQPPH
Tayfun Pay
4
Grundsätzlich erfasst die Klasse "effiziente" Quantenalgorithmen (Bounded-Error-Quantenpolynom-Zeit). Deshalb ist Tayfuns Formalisierung Ihrer Frage die natürliche, zB wenn P = N P , gibt es immer noch Probleme nicht in P , noch in B Q P ? Und anscheinend stimmt es mit unserem gegenwärtigen Wissen überein, dass dies geschieht. BQPP=NPPBQP
Usul

Antworten:

30

Die Arbeit " BQP and the Polynomial Hierarchy " von Scott Aaronson geht direkt auf Ihre Frage ein. Wenn P = NP, dann würde PH zusammenbrechen. Wenn weiterhin BQP in PH wäre, dann wäre in diesem Fall keine Quantenbeschleunigung möglich. Andererseits gibt Aaronson Hinweise auf ein Problem mit der Quantenbeschleunigung außerhalb von PH, so dass eine solche Beschleunigung einen Zusammenbruch von PH überleben würde.

Martin Schwarz
quelle
10
Eigentlich hat Aaronson selbst bewiesen, dass die Vermutung, dass er auf dieser Arbeit basiert, falsch ist. Siehe scottaaronson.com/papers/glnfalse.pdf
Alex Grilo
5
@AlexGrilo Einige der Ergebnisse in der Veröffentlichung waren bedingungslos und stehen noch: Es gibt eine Orakeltrennung zwischen relationalen Versionen von BQP und PH.
Sasho Nikolov
8
A clarification: while the "Generalized Linial-Nisan Conjecture" turned out to be false, the conjecture that the Fourier Checking / "Forrelation" problem is not in PH still stands. It's just that some other approach will be needed to prove it. Also, I can strengthen my result that there exists an oracle relative to which there are BQP relation problems not in BPP^PH, to show that there exists an oracle relative to which P=NP, but there are still BQP relation problems not in BPP. It's a straightforward extension, but unfortunately I haven't written it up yet.
Scott Aaronson
9

The answer is an unequivocal yes. Quantum computers would definitely still be useful.

Quantencomputer sind kein Orakel für BQP, sondern Geräte, die Quantenzustände verarbeiten und unter Verwendung von Quantenzuständen kommunizieren können. Ebenso wie die Fähigkeit, nicht deterministische Abfragen durchzuführen, wesentlich leistungsfähiger ist als die Fähigkeit, rein deterministische Abfragen unabhängig vom Status von P vs NP (und tatsächlich ist dies die Wurzel der Orakeltrennungen) durchzuführen, die Fähigkeit, Quantenabfragen durchzuführen und mit Quantenzuständen zu kommunizieren ist wesentlich mächtiger als das rein klassische Gegenstück.

Dies führt zu Vorteilen in einer Vielzahl von Anwendungen

  1. Die Fähigkeit, Orakel oder externe Datenbanken in Überlagerung abzufragen, bietet eine nachweisbare Trennung zwischen Quantencomputern und klassischen Computern in Bezug auf die Komplexität von Abfragen.
  2. Es gibt eine Vielzahl von Kommunikationsaufgaben, bei denen die Kommunikationskosten, die für die Quantenkommunikation verwendet werden, drastisch gesenkt werden.
  3. Die Quanteninformationsverarbeitung ermöglicht informationstheoretisch sichere Protokolle für ein breiteres Spektrum von Problemen, als dies klassisch möglich ist. Sicherlich erfordert QKD keine Implementierung eines universellen Quantencomputers, aber viele Protokolle für andere Aufgaben.
  4. Durch die Vor- und Nachbearbeitung von großen verschränkten Quantenzuständen können Sie die Rauschgrenze in der Messtechnik überschreiten, was zu genaueren Messungen führt.

Neben den Komplexitätsargumenten gibt es einen weiteren praktischen Grund, sich für Quantencomputer zu entscheiden. Ein Großteil der Daten, die heutzutage auf klassischen Computern verarbeitet werden, stammen aus der Wahrnehmung der natürlichen Welt (z. B. über das CCD in einer Digitalkamera). Solche Messungen werfen jedoch notwendigerweise einige Informationen über das System weg, um das Messergebnis als klassische Bitfolge wiederzugeben (zum Beispiel das Zusammenfallen räumlicher Überlagerungen von Photonen), und es ist nicht immer klar, welche Informationen später als die wichtigsten angesehen werden erstmaliges Aufzeichnen der Daten. Es ist daher vernünftig anzunehmen, dass die Fähigkeit, Quantenzustände direkt zu speichern und zu verarbeiten, anstatt sie auf einer bestimmten Basis vor der Verarbeitung zu kollabieren, zunehmend wünschenswert wird.

Joe Fitzsimons
quelle
4

Addressing the practical part.

If P=NP, but SAT solvers run in O(n2103) this will be of no practical interest on current hardware.

On April 1st Doron Zeilberger proved (jokingly) that P is equal to NP. From the paper "Alas the complexity of our algorithm is O(n1010000) (with the implied constant being larger than the Skewes number)."

As far as I can tell sufficiently powerful quantum computer will be of practical interest in this case.

joro
quelle
But quantum computers might not offer any speedup over a SAT solver that takes time n2103 either.
Sasho Nikolov
@SashoNikolov I addressed practical. Quantum computer which factors 2048 bit integers efficiently would be of practical interest to me as of now because of RSA keys ;).
joro
I believe that one can get linear time sorting algorithms with quantum computers.
Baby Dragon
2

There are studies in the relation between BQP and the polynomial hierachy PH. For instance, there is a problem relative to which BQP is not contained in PH (http://arxiv.org/abs/0910.4698), and a conjecture that proves the same result in an unrelativized world (http://arxiv.org/abs/1007.0305). See also the problem of BosonSampling, that is sampling from the probability outcome of photons coming out from a beam splitter network, is thought to be classically hard while can be implemented by a rather simple quantum systems which is not even a universal quantum computer (look for the paper Aaronson, Arkhipov - The Computational Complexity of Linear Optics). It is another hint that quantum computing is stongher than PH: indeed, if a classical computer can efficiently solve BosonSampling with an oracle for a PH problem, then P#PBPPPH which imply the polynomial hierarchy would collapse.

In conclusion, we don't know what is the exact power of quantum computers but there are results suggesting that BQP might be outside PH.

neophyte
quelle