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

29

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

cc.complexity-theory complexity-classes quantum-computing

— Philip White
źródło

9

Nie wiemy, czy implikuje , tak, że może być jakiś problem w którego nie ma w nawet jeśli .. .. Jest nawet otwarte pytanie, czy jest w ....

P = N P

${P}={NP}$

B Q P = P

${BQP}={P}$

B Q P

${BQP}$

P

${P}$

P = N P

${P}={NP}$

B Q P

${BQP}$

P H

${PH}$

— Tayfun Pay

4

Mówiąc bardziej ogólnie, klasa przechwytuje „wydajne” algorytmy kwantowe (kwantowy wielomianowy błąd błędu). Dlatego sformalizowanie twojego pytania przez Tayfuna jest naturalne, np. Jeśli , czy nadal występują problemy w , ale w ? I najwyraźniej jest to zgodne z naszą obecną wiedzą, że tak się dzieje.

B Q P

$BQP$

P = N P

$P=NP$

P

$P$

B Q P

$BQP$

— usul

30

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.

— Martin Schwarz
źródło

10

W rzeczywistości sam Aaronson udowodnił, że przypuszczenie, że opierał się na tej pracy, jest fałszywe. Zobacz scottaaronson.com/papers/glnfalse.pdf

— Alex Grilo

5

@AlexGrilo Niektóre wyniki w pracy były bezwarunkowe i nadal pozostają w mocy: istnieje wyrocznia separacja między relacyjnymi wersjami BQP i PH.

— Sasho Nikolov

8

Wyjaśnienie: podczas gdy „uogólniona hipoteza liniowa-Nisana” okazała się fałszywa, hipoteza, że problem sprawdzania Fouriera / „korelacji” nie występuje w PH, nadal obowiązuje. Po prostu potrzebne będzie inne podejście, aby to udowodnić. Mogę również wzmocnić mój wynik, że istnieje wyrocznia, w odniesieniu do której występują problemy z relacją BQP nie w BPP ^ PH, aby pokazać, że istnieje wyrocznia, w odniesieniu do której P = NP, ale nadal występują problemy z relacją BQP nie w BPP . Jest to proste rozszerzenie, ale niestety jeszcze go nie napisałem.

— Scott Aaronson,

9

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ń

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ń.
Istnieje wiele zadań komunikacyjnych, które powodują drastyczne obniżenie kosztów komunikacji, która jest wykorzystywana w komunikacji kwantowej.
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ń.
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.

— Joe Fitzsimons
źródło

4

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.

— joro
źródło

n^{2^{10^{3}}}

$n^{2^{10^3}}$

@SashoNikolov zwróciłem się do praktycznych . Komputer kwantowy, który efektywnie uwzględnia liczby całkowite 2048 bitów, byłby dla mnie obecnie praktyczny ze względu na klucze RSA;).

— joro

Uważam, że algorytmy sortowania według czasu można uzyskać za pomocą komputerów kwantowych.

— Baby Dragon

2

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.

— neofita
źródło