Gdyby P = NP były prawdziwe, czy komputery kwantowe byłyby przydatne?

Załóżmy, że P = NP jest prawdziwe. Czy byłoby zatem jakieś praktyczne zastosowanie do budowy komputera kwantowego, takie jak szybsze rozwiązywanie określonych problemów, czy też takie ulepszenie byłoby nieistotne w związku z faktem, że P = NP jest prawdziwe? Jak scharakteryzowałbyś poprawę wydajności, która nastąpiłaby, gdyby komputer kwantowy mógł zostać zbudowany w świecie, w którym P = NP, w przeciwieństwie do świata, w którym P! = NP?

Oto wymyślony przykład tego, czego szukam:

Jeśli P! = NP, widzimy, że klasa złożoności ABC jest równa kwantowej klasie złożoności XYZ ... ale jeśli P = NP, klasa ABC i tak upada do pokrewnej klasy UVW.

(Motywacja: jestem tego ciekawy i stosunkowo nowy w dziedzinie obliczeń kwantowych; prosimy o migrację tego pytania, jeśli nie jest ono wystarczająco zaawansowane).

Artykuł „ BQP and the Polynomial Hierarchy ” autorstwa Scotta Aaronsona bezpośrednio odnosi się do twojego pytania. Jeśli P = NP, wówczas PH się załamie. Gdyby ponadto BQP były w PH, wówczas w tym przypadku nie byłoby możliwe przyspieszenie kwantowe. Z drugiej strony Aaronson dostarcza dowodów na problem z przyspieszeniem kwantowym poza PH, więc takie przyspieszenie przetrwałoby załamanie PH.

Odpowiedź jest jednoznaczna: tak. Komputery kwantowe na pewno byłyby nadal przydatne.

Komputery kwantowe nie są wyroczniami dla BQP, ale raczej urządzeniami, które przetwarzają stany kwantowe i mogą komunikować się za pomocą stanów kwantowych. Podobnie jak zdolność do tworzenia zapytań niedeterministycznych jest zasadniczo silniejsza niż zdolność do tworzenia zapytań czysto deterministycznych, niezależnie od statusu P w porównaniu z NP (i faktycznie jest to podstawa separacji wyroczni), zdolność wykonywania zapytań kwantowych a komunikacja za pomocą stanów kwantowych jest zasadniczo silniejsza niż czysto klasyczny odpowiednik.

Prowadzi to do korzyści w szerokim zakresie zastosowań

1. Możliwość zapytania o wyrocznie lub zewnętrzne bazy danych w superpozycji zapewnia możliwą do udowodnienia separację między komputerami kwantowymi a komputerami klasycznymi pod względem złożoności zapytań.
2. Istnieje wiele zadań komunikacyjnych, które powodują drastyczne obniżenie kosztów komunikacji, która jest wykorzystywana w komunikacji kwantowej.
3. Kwantowe przetwarzanie informacji pozwala na teoretycznie bezpieczne protokoły informacji dla szerszego zakresu problemów niż jest to klasycznie możliwe. Z pewnością QKD nie wymaga implementacji uniwersalnego komputera kwantowego, ale wymaga tego wiele protokołów do innych zadań.
4. Przetwarzanie wstępne i końcowe dużych splątanych stanów kwantowych pozwala na przekroczenie granicy szumu strzału w metrologii, co prowadzi do dokładniejszych pomiarów.

Oprócz argumentów złożoności istnieje jeszcze jeden praktyczny powód, dla którego chcemy komputerów kwantowych. Wiele danych przetwarzanych obecnie na klasycznych komputerach pochodzi z wykrywania świata przyrody (na przykład za pomocą CCD w aparacie cyfrowym). Jednak takie pomiary niekoniecznie wyrzucają pewne informacje o systemie, aby wynik pomiaru był wyświetlany jako klasyczny ciąg bitów (na przykład zapadające się superpozycje przestrzenne fotonów) i nie zawsze jest jasne, które informacje zostaną później uznane za najważniejsze, gdy początkowo rejestrowanie danych. Dlatego uzasadnione jest przypuszczenie, że zdolność do bezpośredniego przechowywania i przetwarzania stanów kwantowych, zamiast ich zapadania się na jakiejś podstawie przed przetwarzaniem, będzie coraz bardziej pożądana.

Zajęcie się częścią praktyczną.

$P=NP$$O(n^{2^{10^3}})$

$O(n^{10^{10000}})$

O ile mogę stwierdzić, w tym przypadku praktyczny interes będzie miał wystarczająco silny komputer kwantowy.

Istnieją badania dotyczące związku między BQP a wielomianową hierachy PH. Na przykład istnieje problem, w odniesieniu do którego BQP nie jest zawarty w PH ( http://arxiv.org/abs/0910.4698 ), i przypuszczenie, które dowodzi tego samego wyniku w nierelatywizowanym świecie ( http://arxiv.org /abs/1007.0305$P^{\# P}\subseteq BPP^{PH}$

Podsumowując, nie wiemy, jaka jest dokładna moc komputerów kwantowych, ale istnieją wyniki sugerujące, że BQP może znajdować się poza PH.