Czy istnieją wyniki algorytmów kwantowych lub złożoności, które prowadzą do postępu w rozwiązywaniu problemu P vs NP?

Na powierzchni algorytmy kwantowe mają niewiele wspólnego z obliczeniami klasycznymi, aw szczególności P vs NP: Rozwiązywanie problemów z NP za pomocą komputerów kwantowych nie mówi nam nic o relacjach klasycznych klas złożoności ¹ .

Z drugiej strony „alternatywny opis” klasycznej złożoności PP jako klasy PostBQP przedstawiony w tym artykule jest, o ile wiem, uważany za ważny wynik dla „klasycznej złożoności” przez „złożoność kwantową” .

W rzeczywistości Scott Aaronson, autor artykułu, pisze na końcu streszczenia:

To pokazuje, że obliczenia kwantowe mogą dostarczyć nowych i prostszych dowodów głównych wyników dotyczących obliczeń klasycznych.

Zatem moje pytanie brzmi: czy istnieją wyniki z dziedziny złożoności kwantowej, które „upraszczają” problem P w porównaniu z NP, podobnie jak w opisie kwantowym PP? Jeśli nie ma takich wyników, czy istnieje dobry powód, aby nie oczekiwać tych wyników, pomimo „sukcesu” PP?

_{1: Weź odpowiedź na to pytanie, na przykład: Czy problem P vs. NP stałby się trywialny w wyniku opracowania uniwersalnych komputerów kwantowych?}

Nie sądzę, aby istniały wyraźne powody odpowiedzi „tak” lub „nie”. Mogę jednak podać powód, dla którego PP był znacznie bardziej skłonny zaakceptować taką charakterystykę niż NP , i podać pewne intuicje, dlaczego NP może nigdy nie mieć prostej charakterystyki pod względem modyfikacji kwantowego modelu obliczeniowego.

Liczenie złożoności

Zarówno klasy NP, jak i PP można scharakteryzować pod względem liczby gałęzi akceptujących niedeterministyczną maszynę Turinga, którą możemy opisać w bardziej przyziemny sposób pod względem możliwych wyników obliczeń losowych, które wykorzystują równomiernie losowe bity. Następnie możemy opisać te dwie klasy jako:

• L  ∈  NP, jeśli istnieje algorytm randomizowany w czasie wielomianowym, który wysyła pojedynczy bit α  ∈ {0,1}, taki że x  ∈  L wtedy i tylko wtedy, gdy Pr [  α  = 1 | x  ] jest niezerowe (choć prawdopodobieństwo to może być małe), w przeciwieństwie do zera.

• L  ∈  PP, jeśli istnieje algorytm randomizowany w czasie wielomianowym, który wysyła pojedynczy bit α  ∈ {0,1}, taki że x  ∈  L wtedy i tylko wtedy, gdy Pr [  α  = 1 | x  ] jest większy niż 0,5 (choć być może tylko najmniejszą), w przeciwieństwie do bycia równym lub mniejszym niż 0,5 ( np.  o niewielką ilość).

Jednym ze sposobów zobaczenia, dlaczego tych klas nie można praktycznie rozwiązać za pomocą tego opisu probabilistycznego, jest to, że potrzeba wykładniczo wielu powtórzeń, aby być pewnym oszacowania prawdopodobieństwa dla Pr [  α  = 1 | x  ] ze względu na drobną różnicę w występujących prawdopodobieństwach.

Złożoność luk i złożoność kwantowa

Opiszmy wyniki „0” i „1” w powyższym obliczeniu jako „odrzuć” i „zaakceptuj”; i zadzwońmy do losowej gałęzi, która daje wynik odrzucenia / zaakceptowania, gałęzi odrzucającej lub akceptującej . Ponieważ każda gałąź randomizowanego obliczenia, która nie akceptuje, dlatego odrzuca, PP można również zdefiniować w kategoriach różnicy między liczbą ścieżek obliczeniowych akceptujących i odrzucających - wielkości, którą możemy nazwać luką akceptacyjną : konkretnie, czy akceptacja różnica jest dodatnia lub mniejsza lub równa zero. Przy odrobinie pracy możemy uzyskać równoważną charakterystykę dla PP, pod względem tego, czy luka akceptacji jest większa niż jakiś próg, czy mniejsza niż jakiś próg, który może być zerowy lub dowolną inną wydajnie obliczalną funkcję wejścia x .

To z kolei można wykorzystać do scharakteryzowania języków w PP pod względem obliczeń kwantowych. Z opisu PP w kategoriach obliczeń losowych o prawdopodobieństwach akceptacji (prawdopodobnie nieznacznie) większych niż 0,5, lub co najwyżej 0,5, wszystkie problemy w PP dopuszczają algorytm kwantowy w czasie wielomianowym, który ma takie samo rozróżnienie w prawdopodobieństwach akceptacji; a modelując obliczenia kwantowe jako sumę na ścieżkach obliczeniowych i symulując te ścieżki, stosując odrzucanie gałęzi dla ścieżek o wadze ujemnej i przyjmowanie gałęzi ścieżek o wadze dodatniej, możemy również wykazać, że taki algorytm kwantowy czyniący (statystycznie słabe) rozróżnienie opisuje problem w PP .

Nie jest oczywiste, że możemy zrobić to samo dla NP . Nie ma naturalnego sposobu na opisanie NP w kategoriach luk akceptacyjnych i oczywiste przypuszczenie, jak możesz spróbować dopasować go do kwantowego modelu obliczeniowego - pytając, czy prawdopodobieństwo zmierzenia wyniku „1” wynosi zero, czy też nie zero - zamiast tego daje klasę o nazwie coC ₌ P , która nie jest znana jako równa NP , i bardzo z grubsza można ją opisać jako mniej więcej tak silną jak PP, a nie zbliżoną do NP pod względem mocy.

Oczywiście pewnego dnia można jakoś scharakteryzować NP pod względem luk akceptacyjnych lub znaleźć nowe sposoby powiązania obliczeń kwantowych z liczeniem złożoności, ale nie jestem pewien, czy ktoś ma jakieś przekonujące pomysły na to, jak to się może stać.

streszczenie

Perspektywy uzyskania wglądu w sam problem P w porównaniu z NP za pomocą obliczeń kwantowych nie są obiecujące - chociaż nie jest to niemożliwe.