Dlaczego komputer kwantowy jest pod pewnymi względami potężniejszy niż niedeterministyczna maszyna Turinga?

Standardowe popularne konto informatyki kwantowej mówi, że komputer kwantowy (QC) działałby, dzieląc na wykładniczo wiele nieinterakcyjnych równoległych kopii siebie w różnych wszechświatach i podejmując każdą próbę weryfikacji innego certyfikatu, a następnie na końcu obliczeń , pojedynczy egzemplarz, który znalazł ważny certyfikat, „ogłasza” swoje rozwiązanie, a pozostałe oddziały magicznie znikają.

Ludzie, którzy wiedzą cokolwiek o teoretycznych obliczeniach kwantowych, wiedzą, że ta historia jest absolutnym nonsensem i że opisany powyżej szorstki pomysł bardziej odpowiada niedeterministycznej maszynie Turinga (NTM) niż komputerowi kwantowemu. Ponadto, klasa współzależności problemów, które można skutecznie rozwiązać przez NTM, to NP, a QC to BQP , a klasy te nie są uważane za równe.

Ludzie próbujący poprawić popularną prezentację słusznie wskazują, że uproszczona narracja „wielu światów” znacznie przecenia moc QC, które nie są w stanie rozwiązać (powiedzmy) problemów z NP . Koncentrują się na błędnym przedstawieniu procesu pomiarowego: w mechanice kwantowej, którego wynik mierzysz, jest regułą Borna, aw większości przypadków prawdopodobieństwo zmierzenia błędnej odpowiedzi całkowicie zaburza prawdopodobieństwo zmierzenia właściwej. (W niektórych przypadkach, takich jak wyszukiwanie w czarnej skrzynce, możemy udowodnić, że żaden sprytny obwód kwantowy nie jest w stanie pokonać reguły Born i zapewnić wykładnicze przyspieszenie.) Gdybyśmy moglimagicznie „zdecyduj, co zmierzyć”, wtedy będziemy w stanie skutecznie rozwiązać wszystkie problemy w klasie złożoności PostBQP , która jest uważana za znacznie większą niż BQP .

Ale nigdy nie widziałem, aby ktoś wyraźnie zauważył, że istnieje inny sposób, w jaki popularna charakterystyka jest błędna, co idzie w innym kierunku. Uważa się, że BQP nie jest ścisłym podzbiorem NP , ale jest nieporównywalny z nim. Istnieją problemy, takie jak sprawdzanie Fouriera, które, jak się uważa, leżą nie tylko poza NP , ale w rzeczywistości poza całą wielomianową hierarchią PH . Tak więc w odniesieniu do takich problemów popularna narracja jest raczej pod stanami, niż przecenia się siłę QC.

Moją naiwną intuicją jest to, że gdybyśmy mogli „wybrać, co zmierzyć”, popularna narracja byłaby mniej więcej poprawna, co oznaczałoby, że te superkwantowe komputery byłyby w stanie skutecznie rozwiązać dokładnie klasę NP . Ale wierzymy, że to jest złe; w rzeczywistości PostBQP = PP , który uważamy za ścisły nadzór NP .

Czy jest jakaś intuicja, co dzieje się za kulisami, która pozwala komputerowi kwantowemu (pod pewnymi względami) być potężniejszym niż niedeterministyczna maszyna Turinga? Przypuszczalnie ta moc „z natury kwantowa” w połączeniu z postselekcją (która w pewnym sensie ma już NTM) sprawia, że ​​super-QC jest o wiele silniejszy niż NTM. (Zauważ, że szukam intuicji, która bezpośrednio kontrastuje NTM i QC z postselekcją, bez „przejścia” przez klasyczną klasę złożoności PP .)

Z pseudo-fundamentalnego punktu widzenia powodem, dla którego BQP jest inaczej potężną (aby ująć frazę) klasą niż NP , jest to, że komputery kwantowe można uznać za wykorzystujące destrukcyjne zakłócenia.

Wiele różnych klas złożoności można opisać w kategoriach (mniej lub bardziej skomplikowanych właściwości) liczby przyjmujących gałęzi NTM. Biorąc pod uwagę NTM w „normalnej formie”, co oznacza, że ​​zestaw gałęzi obliczeniowych jest kompletnym drzewem binarnym (lub czymś podobnym do niego) o pewnej wielomianowej głębi, możemy rozważyć klasy języków zdefiniowane przez dokonanie następujących rozróżnień:

• Czy liczba gałęzi akceptujących jest zerowa czy niezerowa? (Charakterystyka NP .)
• Czy liczba oddziałów akceptujących jest mniejsza niż maksymalna, czy dokładnie równa maksymalnej? (Charakterystyka coNP .)
• Czy liczba oddziałów akceptujących wynosi co najwyżej jedną trzecią lub co najmniej dwie trzecie całości? (Charakterystyka BPP .)
• Czy liczba oddziałów akceptujących jest mniejsza niż połowa lub przynajmniej połowa całości? (Charakterystyka PP .)
• Czy liczba akceptujących gałęzi jest różna od dokładnie połowy, czy równa dokładnie połowie całości? (Charakterystyka klasy o nazwie C ₌ P. )

Są to tak zwane klasy liczące , ponieważ w rzeczywistości są one definiowane w kategoriach liczby gałęzi akceptujących.

Interpretując gałęzie NTM jako generowane losowo, są to pytania dotyczące prawdopodobieństwa akceptacji (nawet jeśli właściwości tych nie da się skutecznie przetestować z jakimkolwiek poziomem ufności statystycznej). Innym podejściem do opisu klas złożoności jest rozważenie zamiast tego luki między liczbą gałęzi akceptujących a liczbą gałęzi odrzucających NTM. Jeśli liczenie kumulacji gałęzi obliczeniowych NTM odpowiada prawdopodobieństwom, można by zasugerować, że anulowanie gałęzi akceptujących przeciw odrzuceniu gałęzi modeluje anulowanie obliczeniowych „ścieżek” (jak w sumach nad ścieżkami) w obliczeniach kwantowych - to znaczy jako modelowanie destrukcyjnych zakłóceń .

Najbardziej znane górne granice dla BQP , a mianowicie AWPP i PP , są łatwe do zdefiniowania w ten sposób pod względem „luk w akceptacji”. Klasa NP nie ma jednak tak oczywistej charakterystyki. Co więcej, wiele klas, które uzyskuje się z definicji pod względem luk akceptacyjnych, wydaje się mieć większą moc niż NP . Można to uznać za wskazujące, że „niedeterministyczna destrukcyjna interferencja” jest potencjalnie silniejszym zasobem obliczeniowym niż zwykły niedeterminizm; tak więc nawet jeśli komputery kwantowe nie wykorzystają w pełni tego zasobu obliczeniowego, mogą mimo to oprzeć się łatwemu ograniczeniu w klasach takich jak NP .

Ta odpowiedź została „zmigrowana” od momentu, gdy pytanie zostało zadane w dziedzinie informatyki (autor pozostaje ten sam)

Cóż, jednym z głównych powodów jest to, że nie ma żadnych algorytmów kwantowych, które rozwiązałyby trudne problemy NP w czasie wielomianowym.

Innym jest to, że adiabetyczne wyżarzanie kwantowe (jak w Dwave) może ledwo pobić klasyczne wyżarzanie kwantowe.

Ponadto większość badaczy uważa P.$\neq$NP. Wielu uważa, że ​​P$=$BQP. Jednak P.$\neq$PostBQP. Jest PostBQP$\neq$NP teraz sprzeczność? Nie. Wiemy tylko, że P$=$NP jest słabszym stwierdzeniem niż (niekoniecznie sugerując więcej!) PostBQP$=$P! Dlaczego więc tyle zamieszania wokół pytania trudniejszego niż P vs. NP!

Co do tego, dlaczego wierzyć P$=$BQP, niektórzy uważają, że jakakolwiek poprawa nie będzie asymptotyczna lub jedynie stała, jak w przypadku różnych wdrożeń.

Istnieją więc powody, by wierzyć PostBQP$\neq$NP. Ale to wszystko spekulacje i prawdopodobnie przez jakiś czas pozostają spekulacjami. Na razie możesz wierzyć, w co tylko chcesz.

Istnieją problemy, takie jak sprawdzanie Fouriera, które, jak się uważa, leżą nie tylko poza NP, ale w rzeczywistości poza całą hierarchią wielomianową. Tak więc w odniesieniu do takich problemów popularna narracja raczej rozumie, niż przecenia moc QC.

Co do tego, nie widziałem wyniku, który stwierdza, że ​​komputer kwantowy może rozwiązać to skutecznie ! Ponadto, że maszyna może szybko rozwiązać dziwne problemy (symulując się$O(n)$, na przykład) nie jest bardziej zaskakujące niż wodospad $O(n)$ (n oznacza liczbę kroków symulacji)