Czy jakieś algorytmy kwantowe poprawiają klasyczne SAT?

29

Klasyczne algorytmy mogą rozwiązać 3-SAT w czasie (losowo) lub (deterministycznie). (Odnośnik: najlepsze górne granice na SAT ) $1.3071^n$ $1.3303^n$

Dla porównania, użycie algorytmu Grovera na komputerze kwantowym i zapewniło rozwiązanie w losowaniu losowym . (Może to nadal wymagać pewnej wiedzy o tym, ile rozwiązań może istnieć, ale nie jestem pewien, jak konieczne są te granice.) Jest to wyraźnie znacznie gorsze. Czy istnieją jakieś algorytmy kwantowe, które działają lepiej niż najlepsze algorytmy klasyczne (a przynajmniej - prawie tak dobre?) $1.414^n$

Oczywiście klasyczne algorytmy można by zastosować na komputerze kwantowym, zakładając wystarczającą przestrzeń roboczą; Zastanawiam się z natury algorytmami kwantowymi.

quantum-computing sat exp-time-algorithms

— Alex Meiburg
źródło

21

Myślę, że można uzyskać nietrywialną górną granicę z obliczeń kwantowych poprzez przyspieszenie losowych algorytmów Schöninga dla 3-SAT. Algorytm Schöninga działa w czasie i stosując standardowe techniki amplitudy amplitudy można uzyskać algorytm kwantowy, który działa w czasie co jest znacznie szybsze niż klasyczny algorytm. $(4/3)^n$ $(2/\sqrt{3})^n=1.15^n$

— wwjohnsmith1
źródło

Fajnie, to wygląda dobrze. Pokazuje, że powinienem raz spojrzeć na klasyczne algorytmy, zanim zapytam! :) Więcej skimów sugeruje, że najlepszym randomizowanym algorytmem dla (niekoniecznie unikalnego) 3-SAT jest , więc myślę, że możemy oczekiwać od komputera kwantowego ... dzięki!

{1.32065}^{n}

$1.32065^n$

{1.1492}^{n}

$1.1492^n$

— Alex Meiburg

Możesz także polubić ten artykuł: digitalcommons.utep.edu/cgi/…

— Martin Schwarz

30

Rzeczywiście, jak powiedział wwjohnsmith1, można uzyskać przyspieszenie pierwiastka kwadratowego w stosunku do algorytmu Schöninga dla 3-SAT, ale bardziej ogólnie dla algorytmu Schöninga dla k-SAT. W rzeczywistości wiele losowych algorytmów dla k-SAT można zaimplementować kwadratowo szybciej na komputerze kwantowym.

Przyczyna tego ogólnego zjawiska jest następująca. Wiele losowych algorytmów dla k-SAT, które działają w czasie (gdzie jest jakąś wykładniczo rosnącą funkcją ), faktycznie robi coś silniejszego. U ich podstaw leży algorytm czasu wielomianowego, który daje satysfakcjonujące przypisanie, jeśli istnieje, z prawdopodobieństwem co najmniej . Z tego wynika, że jeśli powtórzysz wielokrotnie ten algorytm wieloczasowy i zaakceptujesz, jeśli którykolwiek z przebiegów zwróci rozwiązanie, otrzymasz losowy algorytm dla k-SAT działający w czasie . $O(T(n) \mathrm{poly}(n))$ $T(n)$ $n$ $1/T(n)$ $O(T(n))$ $O(T(n) \mathrm{poly}(n))$

Teraz zamiast uruchamiać ten algorytm razy , możesz uruchomić amplitudę amplitudy na tym algorytmie wieloczasowym. Wzmocnienie amplitudy jest ogólnym algorytmem kwantowym, który może decydować, czy inny algorytm akceptuje z prawdopodobieństwem 0 lub z prawdopodobieństwem używając tylko tego algorytmu. Zastosowanie amplitudy amplitudy do takiego solvera k-SAT natychmiast da algorytm kwantowy dla k-SAT z czasem działania , który jest kwadratowo szybszy (ignorując termin poli (n)). $O(T(n))$ $1/T$ $O(\sqrt{T})$ $O(\sqrt{T(n)}\mathrm{poly}(n))$

— Robin Kothari
źródło