Wenn jemand einen universellen Quantencomputer bauen würde, hätte dies Auswirkungen auf das Problem von P vs. NP?
25
Wenn jemand einen universellen Quantencomputer bauen würde, hätte dies Auswirkungen auf das Problem von P vs. NP?
Antworten:
Nein, es wird aus mehreren Gründen absolut keine Auswirkungen geben:
Das P vs. NP-Problem betrifft eher die klassische Berechnung als die Quantenberechnung. Selbst wenn Quantencomputer NP-harte Probleme in der Polynomzeit lösen könnten (was wir nicht erwarten können), könnte es dennoch vorkommen, dass klassische Computer sie in der Polynomzeit nicht lösen können.
Universelle Quantencomputer im theoretischen Sinne sind meines Wissens bereits bekannt. Dies sind nur die Quantenanaloga von universellen Turing-Maschinen: Sie können jedes gegebene Quanten- "Programm" ausführen.
Sowohl die Quantenberechnung als auch das P vs. NP-Problem sind theoretische Begriffe. Was jemand in der physischen Welt konstruieren kann, hat überhaupt nichts damit zu tun.
Lieuwe Vinkhuijzen hat Ihre Frage anders interpretiert:
Die erwartete Antwort lautet: nein. Selbst in diesem Sinne werden physikalische Quantencomputer uns nicht in die Lage versetzen, NP-vollständige Probleme nach Belieben zu lösen.
quelle
In beiden Fällen sind keine Implikationen bekannt: Die klassische Simulation von Quantencomputern sagt nichts darüber aus, wie schwierig NP-Suchprobleme sind. Schnelle Lösungen für NP-Suchprobleme sagen nichts darüber aus, wie schnell sich Quantencomputer klassisch simulieren lassen. Folgende Szenarien sind möglich:
Der Blog eines einflussreichen theoretischen Quanteninformatikers, Scott Aaronson, trägt die Überschrift " Wenn Sie nur eine Information aus diesem Blog entnehmen: Quantencomputer würden harte Suchprobleme nicht sofort lösen, wenn Sie nur alle Lösungen auf einmal versuchen ".
quelle
In einem (als unwahrscheinlich erachteten) Szenario hätte der Bau eines universellen Quantencomputers tatsächlich Auswirkungen auf das Problem von P vs. NP.
Dies erweitert den von Yuval Filmus erwähnten Fall, "wenn Quantencomputer NP-harte Probleme in der Polynomzeit lösen könnten".
In einer solchen Situation hätte der Bau eines universellen Quantencomputers im Vergleich zu theoretischen Überlegungen Auswirkungen auf das P-gegen-NP-Problem. Es würde die Möglichkeit geben, nur mit Quantencomputern einen Beweis zu suchen / zu finden, der P gegen NP auflöst und der dann mit einem klassischen Computer verifiziert werden könnte.
Wie in den anderen Antworten bereits erwähnt, gibt es zwar keinen Beweis für die Trennung von BQP und NP-Complete, aber derzeit gibt es Beweise und Erwartungen dafür, dass Quantencomputer NP-Complete-Probleme nicht effizient lösen können.
quelle