Ist es bewiesen, dass die Quantenberechnung NP-Gesamtprobleme nicht besser löst als die klassische Berechnung?

14

Ist es bewiesen, dass die Quantenberechnung NP-Gesamtprobleme nicht besser löst als die klassische Berechnung, oder wird nur geglaubt?

np-complete quantum-computing kptlronyttcna
quelle

Antworten:

11

Es wird vermutet, dass NP-vollständige Probleme in der Quantenpolynomzeit nicht gelöst werden können (dh, dass sie nicht in BQP vorliegen), dies wurde jedoch nicht bewiesen. Wir erwarten in naher Zukunft keinen Beweis, da dies implizieren würde, dass sich P von NP unterscheidet.

Yuval Filmus
quelle
3
Was ist umgekehrt? Wenn sich herausstellt, dass NP-complete in BQP enthalten ist, sagt das etwas über P vs NP aus?
Kptlronyttcna
1
Im Jahr 2007 war nichts bekannt , obwohl das schon eine Weile her ist.
Yuval Filmus
1
@kptlronyttcna Ich denke, es würde nichts über P vs NP sagen, da P vs BQP ebenfalls noch nicht etabliert ist.
P.Péter