Problemy pośrednie NP z efektywnymi rozwiązaniami kwantowymi

27

Peter Shor pokazał, że dwa z najważniejszych problemów pośrednich NP, faktoring i dyskretny log, są w BQP. Natomiast najbardziej znany algorytm kwantowy dla SAT (poszukiwanie Grovera) zapewnia jedynie kwadratową poprawę w porównaniu z klasycznym algorytmem, co sugeruje, że problemy z całkowitą NP są wciąż trudne do rozwiązania na komputerach kwantowych. Jak wskazują Arora i Barak, istnieje również problem w BQP, który nie jest znany z NP, co prowadzi do przypuszczenia, że ​​obie klasy są nieporównywalne.

Czy jest jakaś wiedza / przypuszczenie, dlaczego te pośrednie problemy NP występują w BQP, ale dlaczego SAT (o ile wiemy) nie jest? Czy inne problemy NP-pośrednie podążają za tym trendem? W szczególności, czy izomorfizm grafów w BQP? (ten nie działa dobrze w Google).

Huck Bennett
źródło
4
Przypuszczam, że powinienem odpowiedzieć na pytanie, dlaczego niektóre problemy pośrednie NP występują w BQP, a inne nie są znane. Jedyną rzeczą, którą naprawdę mogę śmiało powiedzieć, jest to, że problemy znane z BQP dzielą się na różne klasy, aw ramach każdej klasy w rozwiązaniu stosowane są ogólnie te same techniki. Zobacz dwa linki w moim poprzednim komentarzu
Peter Shor,
1
Każdy problem z kompletnym BQP służy jako przykład problemu w BQP, który nie jest znany z NP.
Robin Kothari,
2
Odnośnie algorytmu izomorfizmu grafu kwantowego: tuvalu.santafe.edu/~moore/qip-slides.pdf .
Huck Bennett,
1
BQP-complete? Czy ktoś może przytoczyć problem z kompletnym BQP?
Cem Powiedz

Odpowiedzi:

32

Graficzny izomorfizm nie występuje w BQP. Dużo pracy włożono w próbę wprowadzenia tego. Bardzo intrygująca obserwacja jest taka, że ​​izomorfizm grafów mógłby zostać rozwiązany, gdyby komputery kwantowe rozwiązałyby nieabelowy problem ukrytej podgrupy dla grupy symetrycznej (faktoring i log dyskretny są rozwiązywane przez za pomocą problemu ukrytej podgrupy abelowej, który z kolei rozwiązuje się poprzez zastosowanie kwantowej transformaty Fouriera na grupach abelowych).

Jednym ze sposobów, w jaki ludzie próbowali rozwiązać izomorfizm grafów, było zastosowanie kwantowej transformaty Fouriera dla grup nieabelowych. Istnieją algorytmy kwantowej transformaty Fouriera dla wielu grup nieabelowych, w tym dla grupy symetrycznej. Niestety, wydaje się, że zastosowanie kwantowej transformaty Fouriera dla grupy symetrycznej do rozwiązania izomorfizmu grafowego może być niemożliwe; napisano o tym wiele artykułów, które pokazują, że to nie działa, biorąc pod uwagę różne założenia dotyczące struktury algorytmu. Te dokumenty prawdopodobnie znajdziesz w Google.

Peter Shor
źródło
1
Zgaduję, że problemy, które zadałem na temat zaliczenia do kategorii 2 (QFT / HSP) w pytaniu MathOverflow, i to jest kluczowa wspólność. Dzięki!
Huck Bennett,
10
To miła ankieta na temat wszystkiego, co powiedział Peter arxiv.org/abs/0812.0380
Marcos Villagra
Z wynikiem prof. Babai na temat izomorfizmu grafów, co jest złożonością komputerowego algorytmu kwantowego na GI?
XL _At_Here_There
W tej chwili nie mamy żadnych algorytmów kwantowych, które działałyby lepiej niż algorytmy klasyczne.
Peter Shor,
20

Ludowa odpowiedź brzmi, że faktoring jest „ustrukturyzowany” w taki sposób, że nie występują ogólne problemy z kompletnym NP, i dlatego udało nam się znaleźć przewagę kwantową tylko w przypadku problemów pośrednich.

Prawdopodobnie prostszą wersją twojego pytania jest spojrzenie nie na złożoność obliczeniową, ale na złożoność zapytań funkcji boolowskich. Tutaj możemy powiedzieć pewne rzeczy, które można udowodnić, na przykład fakt, że przyspieszenie wielobiegunowe jest możliwe tylko dla funkcji częściowych (udowodnione w http://arxiv.org/abs/quant-ph/9802049 ), a nie dla funkcji, które są symetryczne w danych wejściowych i wyniki (udowodnione w http://arxiv.org/abs/0911.0996 ).

Wyniki te nie rzucają bezpośrednio światła na pytanie BQP vs. NP, ale czy myślę, że są znaczące kroki w kierunku ustalenia, gdzie jest przewaga kwantowa.

Aram Harrow
źródło