Czy kwantowe obliczenia adiabatyczne mogą być szybsze niż algorytm Grovera?

Udowodniono, że adiabatyczne obliczenia kwantowe są równoważne „standardowym” lub obliczeniom kwantowym opartym na modelu bramkowym. Jednak obliczenia adiabatyczne pokazują obietnice problemów związanych z optymalizacją, w których celem jest zminimalizowanie (lub zmaksymalizowanie) funkcji, która jest w jakiś sposób związana z problemem - to znaczy znalezienie wystąpienia, które minimalizuje (lub maksymalizuje) tę funkcję natychmiast rozwiązuje problem.

Wydaje mi się, że algorytm Grovera może zasadniczo zrobić to samo: przeszukując przestrzeń rozwiązania, znajdzie jedno rozwiązanie (być może z wielu rozwiązań) spełniające kryterium wyroczni, które w tym przypadku odpowiada warunkowi optymalności, w czasie , gdzieNjest rozmiarem przestrzeni rozwiązania.$O(\sqrt N)$$N$

Algorytm ten okazał się optymalny: jak Bennett i in. (1997): „klasy nie da się rozwiązać na kwantowej maszynie Turinga w czasie o ( 2 n / 2 ) ”. W moim rozumieniu oznacza to, że nie ma możliwości skonstruowania algorytmu kwantowego, który znalazłby rozwiązanie, przeszukując przestrzeń szybciej niż O ( $\rm NP$$o(2^{n/2})$, gdzieNskaluje się z rozmiarem problemu.$O(\sqrt N)$$N$

Więc moje pytanie brzmi: chociaż adiabatyczne obliczenia kwantowe są często przedstawiane jako lepsze, jeśli chodzi o problemy z optymalizacją, czy naprawdę mogą być szybsze niż ? Jeśli tak, wydaje się to przeczyć optymalności algorytmu Grovera, ponieważ dowolny algorytm adiabatyczny może być symulowany przez obwód kwantowy. Jeśli nie, jaki jest sens opracowywania algorytmów adiabatycznych, jeśli nigdy nie będą one szybsze niż coś, co możemy systematycznie konstruować z obwodami? Czy coś jest nie tak z moim zrozumieniem?$O(\sqrt N)$

Dobre pytanie. W przypadku nieustrukturyzowanego wyszukiwania adiabatyczne obliczenia kwantowe faktycznie dają dokładnie to samo Przyspieszenie N, jakie wykonuje standardowy oparty na bramce algorytm Grovera, jak udowodniono wtymważnym artykule Rolanda i Cerfa. Jest to zgodne z podaną przez ciebie równoważnością obliczeń kwantowych adiabatycznych i bramkowych.$\sqrt{N}$

(Jedna drobna poprawka do twojego pytania: masz rację, że w konfiguracji problemu wyszukiwania wyroczni musisz sformułować zapytanie jako pytanie tak / nie, na które wyrocznia może odpowiedzieć. Ale pytanie nie zostało w rzeczywistości wzięte być „robi extremize funkcji f ( x ) ?”, jak to zaproponował. Zamiast tego „jest f ( x ) mniejszy niż lub równy M ?” See slajdy 9 i 10 tutaj . to dlatego, że wyrocznią dla tych ostatnich pytanie jest uważane za bardziej realistyczny model fizycznego układu, w którym „można sobie wyobrazić, że można bezpośrednio obliczyć lub zmierzyć f ( x ) dla danego $x$$f(x)$$f(x)$$M$$f(x)$$x$, ale .)$f(x) - f_\text{min}$

Niemniej jednak istnieją dwie potencjalne zalety adiabatycznej kontroli jakości, z których obie są trudne do zbadania teoretycznego. Pierwsze jest praktyczne: budowanie dużych spójnych obwodów kwantowych jest o wiele trudniejsze niż rysowanie ich w artykule w czasopiśmie. Chociaż adiabatyczna kontrola jakości nie ma żadnej zasadniczej przewagi nad tradycyjną konfiguracją, może być znacznie łatwiej wdrożyć eksperymentalnie.

Po drugie, to samo ogromne zastrzeżenie dotyczy AQC, jak w przypadku standardowego algorytmu Grovera: dotyczy tylko wyszukiwania nieuporządkowanego lub „czarnej skrzynki”, w którym kompletnie ignorujemy korelacje między odpowiedziami, które daje wyrocznia, gdy są wprowadzane jako „podobne” lub „ powiązane zapytania. Każdy faktyczny problem wyszukiwania, na którym nam zależy, będzie z definicji miał pewną strukturę, chociaż struktura ta może być zbyt skomplikowana, abyśmy mogli to przeanalizować. Na przykład, jeśli myślimy o ekstremalizacji funkcji jako krajobrazie energii, wydaje się rozsądne, że system może łatwiej tunelować między „pobliskimi” lokalnymi minimami niż między „odległymi” minimami.

Tak więc, aby naprawdę rygorystycznie porównać względne korzyści z konfiguracji adiabatycznej i opartej na bramce w prawdziwym eksperymencie, trzeba „pokonać barierę relatywizacji” i rozważyć strukturę konkretnej funkcji, którą próbujemy ekstremalizować, co jest zwykle bardzo trudne. Utrudnia to wyciągnięcie ogólnych wniosków na temat względnych zalet tego podejścia w świecie rzeczywistym. Dlatego też tak trudno jest teoretycznie udowodnić bezwarunkowe rozdzielenie złożoności. Z tego co wiemy, w przypadku problemów w świecie rzeczywistym, a nie wyroczni, komputery kwantowe mogą być w stanie przyspieszyć wykładniczo - być może nawet w przypadku problemów z NP-zupełnością, co oznaczałoby, że NP BQP , chociaż uważa się to za bardzo mało prawdopodobne.$\subset$

Adiabatic quantum computation cannot do anything faster than circuit-based quantum computation from a computational complexity perspective. This is because there is a mathematical proof that circuit-based quantum computation can efficiently simulate adiabatic quantum computation [see section 5 of this paper].

can it really be faster than $\mathcal{O}(\sqrt{N})$?

The answer is no. This is because if AQC could do it in, say, $\mathcal{O}(\log{N})$, then circuit-based QC could also do it in $\mathcal{O}(\log{N})$ by the algorithm in section 5 of the paper I linked above. This would violate the optimality of $\mathcal{O}(\sqrt{N})$ for unstructured search.