Dlaczego kwantowego wyżarzania nie można opisać modelem bramkowym?

21

To pytanie, które zainspirowało mnie do zadawania na podstawie tego pytania , które stwierdza, że ​​wyżarzanie kwantowe jest zupełnie innym modelem obliczeniowym niż zwykły model obwodu. Słyszałem to już wcześniej i rozumiem, że model bramkowy nie ma zastosowania do wyżarzania kwantowego, ale nigdy do końca nie rozumiałem, dlaczego to jest ani jak analizować obliczenia, które może wykonać annealer. Jak rozumiem z kilku rozmów (niektóre same przez falę D!), Odgrywa w tym fakt, że annealery są ograniczone do określonego hamiltonianu.

Emily Tyhurst
źródło

Odpowiedzi:

18

Kwantalizator, taki jak maszyna D-Wave, jest fizyczną reprezentacją modelu Isinga i jako taki ma „problematyczny” hamiltonian w postaci

H.P.=jot=1nhjotσjotz+ja,jotjotjajotσjazσjotz.

Zasadniczo problem do rozwiązania jest odwzorowany na powyższy hamiltonian. System zaczyna się od Hamiltonian H.ja=jot=1nhjotσjotx a parametr wyżarzania s służy do mapowania początkowego hamiltonianu H.ja na problem Hamiltonian H.P. za pomocą H.(s)=(1-s)H.ja+sH.P. .

Ponieważ jest to wyżarzanie, proces jest przeprowadzany wystarczająco powoli, aby pozostać w pobliżu stanu podstawowego układu, podczas gdy hamiltonian różni się od stanu problemu, wykorzystując tunelowanie, aby pozostać w pobliżu stanu podstawowego, jak opisano w odpowiedzi Nata .

Dlaczego nie można tego wykorzystać do opisania modelu bramy QC? Powyżej jest kwadratowy problem optymalizacji binarnej (QUBO) , który jest trudny do NP ... Rzeczywiście, oto artykuł mapujący szereg problemów NP do modelu Isinga . Każdy problem w NP można odwzorować na dowolny trudny NP w czasie wielomianowym, a faktoryzacja liczb całkowitych jest rzeczywiście problemem NP.

Cóż, temperatura jest niezerowa, więc nie będzie w stanie gruntu przez wyżarzanie, w wyniku czego rozwiązanie jest nadal tylko przybliżone. Lub, innymi słowy, prawdopodobieństwo niepowodzenia jest większe niż połowa (prawie wcale nie ma przyzwoitego prawdopodobieństwa sukcesu w porównaniu z tym, co powszechna QC uważa za „przyzwoitą” - sądząc z wykresów, które widziałem, prawdopodobieństwo sukcesu dla obecna maszyna wynosi około a sytuacja będzie się pogarszać wraz ze wzrostem wielkości), a algorytm anneal nie jest ograniczony błędem. W ogóle. W związku z tym nie ma możliwości dowiedzenia się, czy masz właściwe rozwiązanie z czymś takim jak rozkład liczb całkowitych.0.2%

To, co (w zasadzie) robi, to bardzo szybko zbliżyć się do dokładnego wyniku, ale to nie pomaga w niczym, gdzie wymagany jest dokładny wynik, ponieważ przejście od „prawie poprawnej” do „poprawnej” jest nadal niezwykle trudne ( tzn. prawdopodobnie nadal NP w ogóle, gdy pierwotnym problemem jest NP) problem w tym przypadku, ponieważ parametry, które są / dają „prawie poprawne” rozwiązanie, niekoniecznie będą dystrybuowane gdziekolwiek w pobliżu parametrów, które są / dają prawidłowe rozwiązanie.

Edytuj dla wyjaśnienia: oznacza to, że annealer kwantowy (QA) wciąż potrzebuje czasu wykładniczego (choć potencjalnie krótszy czas wykładniczy), aby rozwiązać problemy NP, takie jak rozkład liczb całkowitych, gdzie uniwersalna QC przyspiesza wykładniczo i może rozwiązać to samo problem w czasie wielorakim. To sugeruje, że kontrola jakości nie może symulować uniwersalnej kontroli jakości w czasie wielofazowym (w przeciwnym razie mogłaby rozwiązać problemy w czasie wielorakim, których nie mogłaby). Jak wskazano w komentarzach, to nie jest to samo, co stwierdzenie, że kontrola jakości nie może dać takiego samego przyspieszenia w innych problemach, takich jak wyszukiwanie w bazie danych.

Mithrandir24601
źródło
1
Jeśli dobrze rozumiem, zasadniczo mówisz, że annealer kwantowy nie może opisać obwodu kwantowego, ponieważ problem ze znalezieniem minimum arbitralnego hamiltonianu jest trudny NP. Nie rozumiem tej implikacji. Symulacja obwodów kwantowych jest również generalnie trudna do symulacji klasycznej (patrz np. 1610.01808 )
glS
1
Ponadto wiadomo, że niektóre problemy rozwiązywane za pomocą algorytmów wyrażonych jako obwody kwantowe można rozwiązać również za pomocą wyżarzania kwantowego. Godnym uwagi przykładem jest wyszukiwanie w bazie danych (patrz np. Sekcja II z 1006.1696 ). Oznacza to, że w pewnym sensie można w niektórych okolicznościach zmapować obwód wodny w problem wyżarzania. Czy to również nie unieważnia twojego trzeciego akapitu (a konkretnie twierdzenia, że [tego nie można użyć do opisania modelu bramy QC )
glS
1
@glS nie, wcale, wcale - wciąż trwa wykładniczy czas, aby znaleźć min (jak w artykule w drugim komentarzu) problemu trudnego dla NP, więc podczas gdy występują problemy w P (np. wyszukiwanie w bazie danych), gdzie przyspieszenie może być w stanie dopasować się do uniwersalnego QC, rozwiązanie problemu NP wciąż wymaga czasu wykładniczego, aby znaleźć się w granicach błędu, przy czym uniwersalny QC może być w stanie rozwiązać ten sam problem w czasie wielorakim, np. rozkład na czynniki całkowite. Ponieważ QA nie może tego zrobić, QA nie może symulować uniwersalnej QC w czasie
wielofazowym
Ok, ale to nie to, co mówisz w odpowiedzi (a przynajmniej nie wprost). Z odpowiedzi wygląda na to, że mówisz, że QA nigdy nie może być użyte do rozwiązania problemu rozwiązanego przez model QC bramki. Jest to zupełnie inne niż stwierdzenie, że QA nie może skutecznie rozwiązać problemu trudnego dla NP (który czasami może zostać rozwiązany przez obwód kwantowy ... chociaż nie sądzę, że zostało to udowodnione, ponieważ nie wiemy, czy faktoring jest naprawdę Według mnie trudna NP i większość innych problemów, w których wykazano przewagę kwantową, nie są problemami decyzyjnymi.
glS
Dokonałem edycji, która, mam nadzieję, wyjaśnia wszystko. Nie wiadomo, czy P = NP, czy nie, jasne, ale nadal jest to konkretny przykład, że QC jest wykładniczo szybszy, zgodnie z obecną wiedzą
Mithrandir24601
16

Wyżarzanie jest bardziej analogową taktyką.

Istotą jest to, że masz dziwną funkcję, którą chcesz zoptymalizować. Więc odbijacie się od niego. Początkowo „ temperatura ” jest bardzo wysoka, tak że wybrany punkt może się bardzo odbijać. Następnie, gdy algorytm „ ochładza się ”, temperatura spada, a odbijanie staje się mniej agresywne.

Ostatecznie ustala się na lokalne optymima, które idealnie są optymalne jak globalne optymima.

Oto animacja symulowanego wyżarzania (nie kwantowa):

Ale to prawie ta sama koncepcja wyżarzania kwantowego :

Natomiast logika bramkowa jest znacznie bardziej cyfrowa niż analogowa. Zajmuje się kubitami i operacjami logicznymi, a nie tylko znalezieniem wyniku po chaotycznym podskakiwaniu.

Nat
źródło
Dzięki, to wyjaśnia mi pewne ograniczenia. Czy znasz jakieś problemy, których nie można przeformułować jako problem wyżarzania (wiem, że Wikipedia stwierdziła, że ​​algorytm Shora nie był możliwy, ponieważ jest to problem „wspinania się na wzgórze”, ale jeśli wiesz więcej o jego szczegółach, ja bardzo chciałbym je usłyszeć :)
Emily Tyhurst
2
@EmilyTyhurst Technicznie, każdy problem można opisać w kategoriach wspinaczki. Pozostaje jeszcze pytanie, jak dobrze zachowuje się ten problem, gdy jest opisany w formacie wspinaczkowym. Problemy, które nie pasują dobrze, mogą być bardzo brzydkie. W przypadku problemów zupełnie niewypukłych wspinaczka po wzgórzach byłaby w najlepszym wypadku poszukiwaniem siły.
Nat
@EmilyTyhurst Hah opps, źle odczytał swój komentarz w przeciwnym kierunku. xD Ale tak, możesz przeprowadzić symulowane wyżarzanie na komputerze kwantowym, tak jak na klasycznym komputerze. Zatem przypuszczam, czy to, co nazywamy „ wyżarzaniem kwantowym ”, staje się bardziej kwestią semantyki.
Nat
2
@EmilyTyhurst Tak, na pewno wszystkie są wymienne. Chodzi mi o to, że jest to koncepcja kompletności Turinga - jeśli mamy jakąś kompletną logikę, możemy z niej zbudować prawie wszystko.
Nat
1
Ważnym punktem wyżarzania kwantowego jest adiabatyczna zmiana hamiltonianu, aby stan pozostawał przez cały czas stanem podstawowym (zmieniającego się) hamiltonianu, a ty otrzymujesz gs końcowego hamiltonianu, który jest celem protokołu . Jak to się ma do opisywanych tu „skoków”? Ten artykuł ( 1006.1696 ) może być interesujący w tym względzie (konkretnie ostatnia część drugiej kolumny pierwszej strony).
glS