Konsekwencje

Jako amator TCS czytam popularny materiał wprowadzający na temat komputerów kwantowych. Oto kilka podstawowych elementów informacji, których nauczyłem się do tej pory:

1. Komputery kwantowe nie są znane z rozwiązywania problemów NP-zupełnych w czasie wielomianowym.
2. „Magia kwantowa nie wystarczy” (Bennett i in. 1997): jeśli odrzucisz strukturę problemu i po prostu weźmiesz pod uwagę możliwych rozwiązań, to nawet komputer kwantowy potrzebuje około $2^n$ kroków do znalezienia właściwego (przy użyciu algorytmu Grovera)$\sqrt{2^n}$
3. Jeśli kiedykolwiek zostanie znaleziony kwantowy algorytm wielomianowy dla problemu pełnego NP, musi on w jakiś sposób wykorzystać strukturę problemu (inaczej byłoby to sprzeczne z Bullett 2).

Mam kilka (podstawowych) pytań, których do tej pory nikt nie zadawał na tej stronie (być może dlatego, że są podstawowe). Załóżmy, że osoba znajduje ograniczonego błędu kwantową algorytm wielomian czasowy (lub dowolny inny problem NP-zupełny), w ten sposób umieszczając S A T w B Q P i wymuszając N P ⊆ B P P .$SAT$$SAT$$BQP$$NP \subseteq BQP$

pytania

1. Jakie byłyby teoretyczne konsekwencje takiego odkrycia? Jak wpłynie to na ogólny obraz klas złożoności? Które klasy stałyby się równe innym?
2. Taki wynik wydaje się sugerować, że komputery kwantowe miały z natury lepszą moc niż komputery klasyczne. Jakie byłyby konsekwencje takiego wyniku dla fizyki? Czy wydobyłoby trochę światła na jakiś otwarty problem w fizyce? Czy fizyka zostałaby zmieniona po podobnym wyniku? Czy wpłynęłoby to na znane nam prawo fizyki?
3. Możliwość (lub nie) wykorzystania struktury problemu w sposób wystarczająco ogólny (tj. Niezależny od konkretnej instancji) wydaje się być rdzeniem pytania P = NP. Teraz, jeśli zostanie znaleziony algorytm kwantowy wielomianowy czasowy błąd ograniczony dla i musi on wykorzystać strukturę problemu, czy jego strategia wykorzystania struktury nie byłaby użyteczna również w scenariuszu klasycznym? Czy istnieją dowody wskazujące, że taka eksploatacja struktury może być możliwa dla komputerów kwantowych, a pozostała niemożliwa dla komputerów klasycznych?$SAT$

Nie zamierzam odpowiadać na pierwsze pytanie, ponieważ ktoś taki jak Scott Aaronson, Peter Shor lub John Watrous bez wątpienia może udzielić ci o wiele bardziej wyczerpującej odpowiedzi na ten temat.

W odniesieniu do pytania 2 należy zauważyć, że w wielu przypadkach komputery kwantowe są w rzeczywistości mocniejsze niż komputery klasyczne:

1. Istnieje dość ogólne przyspieszenie wielomianowe uzyskiwane przez komputery kwantowe w porównaniu z komputerami klasycznymi w dość wielu problemach. Z punktu widzenia złożoności jest to być może nieco mniej interesujące niż przyspieszenie wykładnicze, ale jest to coś, co możemy faktycznie udowodnić.
2. Złożoność komunikacji kwantowej często może się znacznie różnić od klasycznej złożoności komunikacji dla tego samego problemu. Ponownie jest to coś, co można udowodnić (patrz na przykład gra Mermin-GHZ).
3. Kwantowe zapytania do wyroczni są często znacznie silniejsze niż klasyczne zapytania do tej samej wyroczni (patrz na przykład algorytm Deutsch-Josza).

Mając to na uwadze, wiadomo już, że komputery kwantowe są zasadniczo potężniejsze niż komputery klasyczne. Myślę, że miałbym rację mówiąc, że większość fizyków pracujących nad takimi rzeczami już założyłaby, że nie jest możliwe znalezienie klasycznego algorytmu do efektywnej symulacji każdego układu kwantowego, a więc wynik pokazujący, że NP był zawarty w BQP byłoby z pewnością zaskakujące, nie byłoby szczególnie prawdopodobne, aby zapewniło przełom w zrozumieniu jakiegokolwiek konkretnego zjawiska fizycznego. Dałoby to raczej mocniejszy dowód, że fizyka kwantowa jest trudna do symulacji.

Nie ma fundamentalnej fizyki, która byłaby zależna od złożoności obliczeniowej jej symulacji, więc znalezienie wydajnego algorytmu kwantowego dla problemu NP-zupełnego nie miałoby fundamentalnych konsekwencji dla poprawności naszego obecnego zrozumienia funkcjonowania wszechświata (chociaż jestem skłonny zgodzić się z sugestią Scotta Aaronsona, że ​​interesujące jest sprawdzenie, czy prawa fizyczne mogą wynikać z założeń obliczeniowych).

Niezwykle kuszące jest stwierdzenie, że miałoby to konsekwencje dla adiabatycznej ewolucji układów kwantowych (i myślę, że możesz otrzymać odpowiedź sugerującą dwa lub dwa), itp., Ale byłoby to nieprawidłowe, ponieważ są one kontrolowane przez określony proces fizyczny pokazując, że w zasadzie możliwe jest rozwiązanie SAT w czasie wielomianowym na komputerze kwantowym, nie powiedziałby nic o ich specyficznej ewolucji.

Jeśli chodzi o twoje ostatnie pytanie, mamy już przykłady wykorzystania struktury problemu w celu uzyskania wielomianowego algorytmu kwantowego, ale które nie prowadzą do takiego klasycznego algorytmu (na przykład faktoring). Tak więc, o ile obecnie rozumiemy, problem ze strukturą możliwą do wykorzystania w celu uzyskania algorytmu kwantowego w czasie wielomianowym nie oznacza, że ​​struktura nadaje się do wykorzystania w celu uzyskania klasycznego wielomianowego algorytmu czasu.

Scott Aaronson często lubił wskazywać (i prawdopodobnie nadal lubi wskazywać, zakładając, że nie ma już tego dość), że procesy fizyczne nie zawsze znajdują globalne minimum krajobrazu energetycznego . W szczególności, jeśli sformułujesz przykład problemu z optymalizacją pełnego NP jako problemu minimalizacji energii dla systemu fizycznego, nie ma powodu - ani teoretycznego, ani empirycznego - sądzić, że taki system fizyczny „rozluźni się” po trochę czasu na rozwiązanie problemu ( tj.  konfiguracja energii, która jest globalnym minimum). Bardziej prawdopodobne jest zrelaksowanie się do lokalnego minimum: takiego, dla którego nieco inne konfiguracje wymagają więcej energii, ale gdzie zasadniczo inna konfiguracja może mieć mniej energii.

Tak więc, chociaż udowodnienie, że NP  ⊆  BQP byłoby triumfem pierwszego rzędu - dla wszystkich teoretyków złożoności, nie tylko dla teoretyków obliczeń kwantowych - sugerowałoby to, że istnieje zupełnie nowa teoria „fizycznych” modeli obliczeń czekających na odkrycie. Czemu? Cóż, modele obliczeń można interpretować jako modele fizyki (aczkolwiek wysoce wyspecjalizowane): mianowicie, jakie zasoby obliczeniowe są fizycznie uzasadnione. Jednym z „slogany” z obliczeń kwantowych jest to, że Nature isn't classical, [darn] it^† - tak chyba można symulować mechaniki kwantowej na klasycznym komputerze, co można obliczyć skutecznie fizycznie jest prawie na pewno mocniejszy niż P . A przecież mamy dowody na to, że ma mniejszą moc niż NP; więc musiałby być również mniej wydajny niż BQP , gdyby tak się stało, że NP  ⊆  BQP .

Tak więc dowód na NP  ⊆  BQP przedstawiłby nam trylemat : albo

1. obwody kwantowe mogą być skutecznie symulowane na klasycznym komputerze, co potwierdza NP  ⊆  BQP  ⊆  P , tym samym przekraczając najśmielsze marzenia i koszmary każdego teoretyka;
2. obwodów kwantowych nie można symulować na klasycznym komputerze, ale skalowalne komputery kwantowe można budować w celu rozwiązania problemów w NP , co powoduje naprawdę gwałtowne zainteresowanie obliczeniami kwantowymi i zapewnia fizykom eksperymentalnym bezpieczeństwo w karierze w dającej się przewidzieć przyszłości;
3. istnieje inny model obliczeń, który czeka na odkrycie, pośredni między P i BQP w mocy, który opisuje (a raczej lepiej przybliża ) to, co jest wydajnie obliczalne fizycznie.

Podejrzewam, że inteligentne pieniądze byłyby na 3 miejscu, tak samo zabawne jak 1 lub 2 z akademickiego punktu widzenia.

^†  Z przeprosinami dla Feynmana, który, jak podejrzewam, nie często mielił swoje przekleństwa.