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

Odpowiedzi:

36

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

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

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

  3. 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⊊BQP
  • P⊊NP=BQP
  • P⊊NP⊊BQP
  • P ⊊ B Q P B Q P N PP⊊NP , ale i są nieporównywalneP⊊BQPBQPNP
  • 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 PP⊊BQP⊊NPP=BQP⊊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 ⊆ N P B P P Q M A P N PP⊆BQPP⊆NPBPPQMAPNP
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