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

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.)

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.

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.

Addressing the practical part.

If $P=NP$, but SAT solvers run in $O(n^{2^{10^3}})$ 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(n^{10^{10000}})$ (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.

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^{\# P}\subseteq BPP^{PH}$ 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.