Czy problem P vs. NP stałby się trywialny w wyniku opracowania uniwersalnych komputerów kwantowych?

25

Gdyby ktoś zbudował uniwersalny komputer kwantowy, czy miałoby to jakikolwiek wpływ na problem P i NP?

complexity-theory complexity-classes quantum-computing

— Barte
źródło

3

Jestem prawie pewien, że już o to pytano, ale nie mogę go znaleźć. Czy ktoś może?

— David Richerby,

6

Pomocna lektura w formie komiksu.

— Dan Bryant

36

Nie, nie będzie absolutnie żadnych konsekwencji z kilku powodów:

Problem P vs. NP dotyczy obliczeń klasycznych, a nie obliczeń kwantowych. Nawet jeśli komputery kwantowe mogłyby rozwiązać problemy NP-trudne w czasie wielomianowym (czego nie oczekujemy, że będą w stanie to zrobić), nadal klasyczne komputery nie są w stanie rozwiązać ich w czasie wielomianowym.
Uniwersalne komputery kwantowe, w sensie teoretycznym, są (zgodnie z moją najlepszą wiedzą) już znane. To tylko kwantowe analogi uniwersalnych maszyn Turinga: mogą one wykonywać dowolny dany „program” kwantowy.
Zarówno obliczenia kwantowe, jak i problem P vs. NP są pojęciami teoretycznymi. To, co ktoś może zbudować w świecie fizycznym, nie ma absolutnie żadnego wpływu na cokolwiek z nim związanego.

Lieuwe Vinkhuijzen podał inną interpretację twojego pytania:

Czy komputery kwantowe będą w stanie skutecznie rozwiązywać problemy NP-zupełne?

Oczekiwana odpowiedź to: nie. Więc nawet w tym sensie fizyczne komputery kwantowe nie umożliwią nam rozwiązania problemów NP-zupełnych do woli.

— Yuval Filmus
źródło

17

Żadne implikacje nie są znane w żaden sposób: klasyczna symulacja komputerów kwantowych nie mówi nam nic o trudnościach wyszukiwania NP; szybkie rozwiązania problemów związanych z wyszukiwaniem NP nie mówią nam nic o tym, jak szybko klasycznie można symulować komputery kwantowe. Możliwe są następujące scenariusze:

$P=NP=BQP$
$P=NP\subsetneq BQP$
$P\subsetneq NP=BQP$
$P\subsetneq NP\subsetneq BQP$
$P\subsetneq NP$ , ale i są nieporównywalne $P\subsetneq BQP$ $BQP$ $NP$
Problemy NP wymagają klasycznej siły brutalnej, ale są rozwiązywane przez szybkie (choć niekoniecznie wielomianowe) algorytmy kwantowe

Blog jednego z wpływowych teoretycznych informatyków kwantowych, Scotta Aaronsona, ma nagłówek „ Jeśli weźmiesz tylko jedną informację z tego bloga: komputery kwantowe nie rozwiążą natychmiastowych problemów z wyszukiwaniem, po prostu wypróbowując wszystkie rozwiązania na raz ”.

— Lieuwe Vinkhuijzen
źródło

1

Tęskniłeś i , z których każdy może być możliwe.

P ⊊ B Q P ⊊ N P

$P\subsetneq BQP \subsetneq NP$

P = B Q P ⊊ N P

$P=BQP\subsetneq NP$

— A Simmons,

2

@ASimmons Prawda! Wszelkie przypuszczenia, które respektują zwykłe i są dopuszczalne. Jeśli wprowadzimy klasy i , które są obowiązkowe, aby właściwie opowiedzieć historię, w jaki sposób komputery kwantowe odnoszą się do pytania vs , otrzymamy wykładniczą liczbę możliwych sposobów, w jakie te klasy mogą się ze sobą odnosić. Mamy nadzieję, że wkrótce przycinimy niektóre z tych światów.

P \subseteq B Q P

$P\subseteq BQP$

P \subseteq N P

$P\subseteq NP$

B P P

$BPP$

Q M A

$QMA$

P

$P$

N P

$NP$

— Lieuwe Vinkhuijzen

0

W jednym (uważanym za mało prawdopodobnym) scenariuszu zbudowanie uniwersalnego komputera kwantowego rzeczywiście miałoby wpływ na problem P vs. NP.

To rozszerza się na przypadek wspomniany przez Yuval Filmusa, „jeśli komputery kwantowe mogłyby rozwiązać problemy NP-trudne w czasie wielomianowym”.

W takiej sytuacji zbudowanie uniwersalnego komputera kwantowego w porównaniu z teoretycznym rozumowaniem jednego z nich miałoby implikacje dla problemu P vs NP. Umożliwiłoby to po prostu użycie komputerów kwantowych do wyszukiwania / znalezienia dowodu, który rozwiązuje P w porównaniu z NP, który mógłby następnie zostać zweryfikowany przez klasyczny komputer.

Jednak, jak wspomniano w innych odpowiedziach, chociaż nie ma dowodu oddzielającego BQP od NP-zupełnego, obecnie istnieją dowody i oczekiwania, że komputery kwantowe nie będą w stanie skutecznie rozwiązać problemów z NP-zupełnym.

— PPenguin
źródło

„Pozwoliłoby to na użycie komputerów kwantowych do wyszukiwania / znalezienia dowodu, który rozwiązuje P w porównaniu z NP, który mógłby następnie zostać zweryfikowany przez klasyczny komputer”. Zasadniczo zautomatyzowane sprawdzanie jest uważane gdzieś pomiędzy nieobliczalnym a nierozstrzygalnym. Ponieważ QC nie jest bardziej „mocny” (pod względem obliczalności) niż maszyna Turinga, a jedynie „szybszy” przy niektórych problemach, nie rozumiem, jak moglibyśmy oczekiwać praktycznych algorytmów kwantowych wspomagających lub automatyzujących dowodzenie P w porównaniu z NP. Czy mógłbyś to rozwinąć?

— Dyskretna jaszczurka