Problemy pośrednie NP z efektywnymi rozwiązaniami kwantowymi

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).

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.

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.