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

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.

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

Zasadniczo problem do rozwiązania jest odwzorowany na powyższy hamiltonian. System zaczyna się od Hamiltonian $H_I = \sum_{J=1}^nh'_j\sigma_j^x$ a parametr wyżarzania $s$ służy do mapowania początkowego hamiltonianu $H_I$ na problem Hamiltonian $H_P$ za pomocą $H\left(s\right) = \left(1-s\right)H_I + 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.

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.