Verbessern sich Quantenalgorithmen gegenüber klassischem SAT?

29

Klassische Algorithmen können 3-SAT in Zeit (randomisiert) oder 1,3303 n- Zeit (deterministisch) lösen . (Referenz: Beste obere Schranken für SAT )1.3071n1.3303n

Zum Vergleich würde die Verwendung des Grover-Algorithmus auf einem Quantencomputer eine Lösung in suchen und liefern , randomisiert. (Dies erfordert möglicherweise noch einige Kenntnisse darüber, wie viele Lösungen es möglicherweise gibt oder nicht. Ich bin mir nicht sicher, wie notwendig diese Grenzen noch sind.) Dies ist eindeutig bedeutend schlimmer. Gibt es Quantenalgorithmen, die besser sind als die besten klassischen Algorithmen (oder zumindest - fast so gut?)1.414n

Natürlich könnten die klassischen Algorithmen auf einem Quantencomputer verwendet werden, wenn genügend Arbeitsraum vorausgesetzt wird. Ich frage mich, was eigentlich Quantenalgorithmen sind.

Alex Meiburg
quelle

Antworten:

21

Ich denke, man kann eine nicht triviale Obergrenze durch Quantencomputing erhalten, indem man die randomisierten Algorithmen von Schöning für 3-SAT beschleunigt. Der Algorithmus , der in Schöning Zeit abläuft und Standardamplitude Amplifikationstechniken verwendet , kann man einen Quantenalgorithmus, der ausgeführt wird in der Zeit erhalten ( 2 / (4/3)nwas erheblich schneller ist als der klassische Algorithmus.(2/3)n=1.15n

wwjohnsmith1
quelle
1.32065n1.1492n
Diese Arbeit könnte Ihnen auch gefallen: digitalcommons.utep.edu/cgi/…
Martin Schwarz
30

In der Tat, wie wwjohnsmith1 sagte, können Sie eine Quadratwurzel-Beschleunigung über Schönings Algorithmus für 3-SAT erhalten, aber auch allgemeiner über Schönings Algorithmus für k-SAT. Tatsächlich können viele randomisierte Algorithmen für k-SAT quadratisch schneller auf einem Quantencomputer implementiert werden.

O(T(n)poly(n))T(n)n1/T(n)O(T(n))O(T(n)poly(n))

O(T(n))1/TO(T)O(T(n)poly(n))

Robin Kothari
quelle