Konsekwencje

33

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 2n kroków do znalezienia właściwego (przy użyciu algorytmu Grovera)2n
  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 .SATSATBQPNPBQP

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
Giorgio Camerani
źródło
1
@Walther: Zauważyłem, że zaktualizowałeś pytanie, aby dodać trochę o przyspieszeniu wykładniczym, ale szczerze mówiąc, rozróżnienie między przyspieszeniami wielomianowymi i wykładniczymi jest nieco sztuczne, więc nie widzę, żeby miało to jakikolwiek wpływ na fizykę.
Joe Fitzsimons,
@Joe: Dodałem ten fragment tylko po to, aby wyjaśnić, co miałem na myśli, gdy zadałem pytanie (tj. Kwant wydawałby się silniejszy niż klasyczny w tym sensie, że ten pierwszy rozwiązałby problemy NP-zupełne w czasie wielomianowym, podczas gdy ten ostatni jeszcze nie lub nigdy). Ale teraz widzę, że jeśli ktoś przeczyta bieżącą wersję pytania, a następnie przeczyta twoją odpowiedź, może się mylić i pomyśleć, że zdanie w twojej odpowiedzi jest złe: dlatego zamierzam to usunąć.
Giorgio Camerani
Przepraszam, nie chciałem zasugerować, żebyś to przeredagował.
Joe Fitzsimons,
@Joe: Nie, nie martw się! ;-) Naprawdę, nie chcę, aby pytanie i odpowiedzi były źle dopasowane: byłoby to mylące dla czytelników i niesprawiedliwe dla tych, którzy odpowiedzieli.
Giorgio Camerani,
1
Artykuł SEP .
Kaveh

Odpowiedzi:

18

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.

Joe Fitzsimons
źródło
16

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.

Niel de Beaudrap
źródło
1
Jasne, możliwość nr 2 nie jest śmieszną możliwością (nawet, muszę podkreślić, w hipotetycznej sytuacji, że NPBQP ). Ale twój argument może być również użyty do argumentowania za numerem 1. Mając wybór między trzema możliwościami, wybieram # 3, ponieważ jest to najbardziej konserwatywna możliwość; ale także dlatego, że uważam, iż należy podkreślić, że istnieją zasadniczo dobre fizyczne i empiryczne powody do dokonywania teoretycznych domniemań złożoności.
Niel de Beaudrap,
3
@Neil: Naprawdę się nie zgadzam. Nie uważam, aby twierdzenie, że mechanika kwantowa jest w ogóle konserwatywne (a wręcz przeciwnie), jest prawdopodobnie błędne, ponieważ komputery kwantowe byłyby potężne. Po prostu nie ma dowodów na 1, dlatego argument nie miałby zastosowania. Istnieje ogromny dowód, że obliczenia kwantowe są, przynajmniej w zasadzie, możliwe.
Joe Fitzsimons,
1
@Joe: Jasne, nasze modele QC są doskonałymi abstrakcjami QM (co samo w sobie jest dość dobrą teorią), o ile możemy powiedzieć. Zasadniczo dopuszcza także rozsądne granice błędów i ma nadzieję na korektę błędu. Ale wystarczająco trudno jest umieścić wszystkie elementy na miejscu, aby uzyskać bezszelestne operacje, prawda? W każdym razie rozmawiamy tutaj o przeciwnych faktach, a warunek jest tutaj doosy - czy możesz mi powiedzieć, że wynik taki jak NPBQP nie dałby ci chwili do zastanowienia się, że być może czeka na Ciebie duży haczyk gdzieś na QC?
Niel de Beaudrap,
2
3
@ Neil: Właściwie wydaje się, że teraz 2. Naprawdę wątpię w BQP = P , więc obwodów kwantowych prawdopodobnie nie da się skutecznie symulować klasycznie. Są jednak wszelkie oznaki, że faktycznie możemy budować komputery kwantowe (choć jest to trudne!).
Joe Fitzsimons,