Kiedy dowiemy się, że osiągnięta została supremacja kwantowa?

22

Termin „supremacja kwantowa” - w moim rozumieniu - oznacza, że ​​można tworzyć i uruchamiać algorytmy do rozwiązywania problemów na komputerach kwantowych, których nie da się rozwiązać w realistycznych czasach na komputerach binarnych. Jest to jednak dość niejasna definicja - co w tym kontekście można by uznać za „realistyczny czas”? Czy musi to być ten sam algorytm, czy tylko ten sam problem? Nie można z pewnością symulować komputerów kwantowych o określonych rozmiarach.

blalasaadri
źródło

Odpowiedzi:

17

Termin quantum supremacy ten niekoniecznie oznacza, że ​​można uruchomić algorithmsjako taki na komputerze kwantowym, który jest niepraktyczny na klasycznym komputerze. Oznacza to po prostu, że komputer kwantowy może coś zrobić , trudno będzie zasymulować klasycznemu komputerowi.

Możesz zapytać (i słusznie), co mam na myśli, mówiąc o czymś zrobionym przez komputer kwantowy, który nie jest algorithm. Rozumiem przez to, że komputer kwantowy może wykonać proces, który

  • niekoniecznie ma bardzo dobrze rozumiane zachowanie - w szczególności bardzo niewiele rzeczy możemy udowodnić w tym procesie;

  • w szczególności proces ten nie „rozwiązuje” żadnego praktycznego problemu - odpowiedź na obliczenia niekoniecznie odpowiada na pytanie, które Cię interesuje.

Kiedy mówię, że proces niekoniecznie ma dobrze zrozumiałe zachowanie, nie oznacza to, że nie wiemy, co robi komputer: będziemy mieli dobry opis wykonywanych operacji. Ale niekoniecznie będziemy mieli dogłębne zrozumienie skumulowanego wpływu na stan systemu tych operacji. (Obietnica obliczeń kwantowych została pierwotnie zaproponowana, ponieważ systemy mechaniki kwantowej są trudne do symulacji , co oznaczało, że może ona być w stanie symulować inne systemy, które są trudne do symulacji.)


Możesz zapytać, o co chodzi z tym, żeby komputer kwantowy zrobił coś, co trudno jest zasymulować, jeśli jedynym powodem jest tylko , że jest to trudne do symulacji. Powodem tego jest: pokazuje dowód zasady. Załóżmy, że możesz budować układy kwantowe z 35 kubitami, z 40 kubitami, z 45 kubitami, 50 kubitów itd. - każdy zbudowany zgodnie z tymi samymi zasadami inżynierii, każdy z nich można symulować w praktyce i każdy zachowuje się tak, jak symulacja przewiduje(do dobrych tolerancji), ale gdzie każda symulacja wymaga znacznie więcej zasobów niż poprzednia. Następnie, gdy masz system na 55 lub 60 kubitów, którego nie możesz symulować za pomocą największego na świecie superkomputera, możesz argumentować, że masz architekturę, która buduje niezawodne komputery kwantowe (na podstawie rozmiarów, które możesz symulować) i które mogą być używane do budowy komputerów kwantowych na tyle dużych, że żadna znana technika symulacji nie jest w stanie przewidzieć ich zachowania (i gdzie być może żadna taka technika nie jest nawet możliwa).

Ten etap sam w sobie niekoniecznie jest użytecznyna wszystko, ale jest to warunek konieczny, aby móc rozwiązać ciekawe problemy na komputerze kwantowym szybciej niż na klasycznym komputerze. Fakt, że na tym etapie niekoniecznie możesz rozwiązać „interesujące” problemy, jest jednym z powodów, dla których ludzie są czasami niezadowoleni z terminu „supremacja”. (Istnieją inne powody związane z konotacjami politycznymi, które moim zdaniem są uzasadnione, ale nie na temat tutaj.) Jeśli wolisz, nazwij to „ascendencją kwantową”, co oznacza, że ​​oznacza to punkt, w którym technologie kwantowe zdecydowanie stają się znaczące w moc, nie narażając się jeszcze na niebezpieczeństwo wymiany telefonu komórkowego w kieszeni, komputerów stacjonarnych, a nawet koniecznie superkomputerów przemysłowych - ale jest to kwestia interesująca w krzywej rozwojowej dowolnej kwantowej technologii obliczeniowej.


Ale podstawową kwestią jest to, że tak, „supremacja kwantowa” polega właśnie na „niemożności symulowania komputerów kwantowych o określonych rozmiarach” lub przynajmniej niemożności symulowania określonych procesów, które można im zlecić, i ten test porównawczy zależy nie tylko od technologii kwantowej, ale od najlepszej dostępnej technologii klasycznej i najlepszych dostępnych technik klasycznych. Jest to rozmyta granica, która, jeśli poważnie podchodzimy do spraw, będziemy mieć pewność, że minęły rok lub dwa po tym fakcie. Ale jest to ważna granica do przekroczenia.

Niel de Beaudrap
źródło
Jako przypis: jeśli chodzi o pytanie „Czy to musi być ten sam algorytm?”, Komputer kwantowy może osiągnąć przewagę nad komputerem klasycznym tylko przy użyciu radykalnie innego algorytmu. Powód jest prosty: komputery kwantowe nie osiągnęłyby przewagi, wykonując operacje szybciej (z pewnością nie w obecnym stanie rozwoju, a być może nie kiedykolwiek), ale wykonując mniej operacji, które nie odpowiadają sensownym operacjom, które mógłby wykonać konwencjonalny komputer być do zrobienia.
Niel de Beaudrap
Tak więc, aby się upewnić: dzięki ogłoszeniu przez Google 72- kubitowego układu Bristlecone i największej liczby kubitów symulowanych według mojej wiedzy, wynoszącej 56 kubitów, możemy to osiągnąć, gdy tylko Google udowodni swój chip?
blalasaadri
2
Pod warunkiem, że kubity w układzie Google są wystarczająco stabilne, a wskaźniki błędów w operacjach wystarczająco niskie, że można by wykonać wystarczająco dużo operacji, aby wykonać coś, co trudno klasycznie zasymulować przed dekompresjami pamięci - to tak, to może być pierwszy zdarzenie „ascendencji kwantowej”. Zasadniczo sensowne jest mówienie o dominacji każdej architektury, której przykładem jest Bristlecone Google. Ale jako element historycznych ciekawostek ciekawie byłoby zauważyć, kto był pierwszy, a Google może być pierwszym.
Niel de Beaudrap
7

Pojęcie supremacji kwantowej wprowadzone przez Preskill w 2012 r. ( 1203,5813 ) można zdefiniować w następującym zdaniu:

Mamy zatem nadzieję przyspieszyć początek ery supremacji kwantowej, kiedy będziemy mogli wykonywać zadania z kontrolowanymi układami kwantowymi, wykraczając poza to, co można osiągnąć za pomocą zwykłych komputerów cyfrowych.

Lub, jak to ujęła wikipedia, supremacja kwantowa jest potencjalną zdolnością kwantowych urządzeń komputerowych do rozwiązywania problemów, których klasyczne komputery praktycznie nie potrafią .

Należy zauważyć, że nie jest to dokładna definicja w sensie matematycznym. Można precyzyjnie stwierdzić, w jaki sposób złożoność danego problemu skaluje się z wymiarem danych wejściowych (powiedzmy, liczbę kubitów, które mają być symulowane, jeśli mamy do czynienia z problemem symulacji). Następnie, jeśli okaże się, że mechanika kwantowa pozwala na bardziej efektywne rozwiązanie tego samego problemu (i, co najważniejsze, jesteś w stanie to udowodnić), oznacza to, że urządzenie kwantowe może zademonstrować (a raczej udowodnić) wyższość kwantową ( lub przewagę kwantową , lub jak wolisz to nazwać, patrz na przykład dyskusja w komentarzach tutaj ).


Więc w świetle powyższego, kiedy dokładnie można twierdzić, że osiągnął reżim kwantowy ? Pod koniec dnia nie ma jednej magicznej liczby, która doprowadziłaby cię od „klasycznie symulowanego reżimu” do „reżimu kwantowej supremacji”, a jest to raczej ciągłe przejście, w którym gromadzi się coraz więcej dowodów w kierunku stwierdzenia, że ​​mechanika kwantowa potrafi lepiej niż fizyka klasyczna (a tym samym dostarczają dowodów przeciwko rozszerzonej tezie Church-Turinga).

Z jednej strony istnieją reżimy, które oczywiście mieszczą się w „reżimie kwantowej supremacji”. To wtedy zdołasz rozwiązać problem z urządzeniem kwantowym, którego po prostu nie możesz rozwiązać za pomocą klasycznego urządzenia. Na przykład, jeśli uda ci się rozłożyć na czynniki ogromną liczbę, która wymagałaby wieku wszechświata do obliczenia za pomocą dowolnego klasycznego urządzenia (i zakładając, że komuś uda się udowodnić, że faktoring jest naprawdę trudny klasycznie, co jest dalekie od określonego), to wydaje się, że trudno obalić, że mechanika kwantowa rzeczywiście pozwala rozwiązać niektóre problemy bardziej efektywnie niż klasyczne urządzenia.

Ale powyższe nie jest dobrym sposobem myślenia o supremacji kwantowej, głównie dlatego, że jednym z głównych punktów supremacji kwantowej jest etap pośredni, zanim będzie w stanie rozwiązać praktyczne problemy z komputerami kwantowymi. Rzeczywiście, w dążeniu do supremacji kwantowej rozluźnia się wymóg próby rozwiązania użytecznych problemów i po prostu próbuje zaatakować zasadę, że przynajmniej w przypadku niektórych zadań mechanika kwantowa rzeczywiście zapewnia korzyści.

Kiedy to zrobisz i poprosisz o najprostsze możliwe urządzenie, które może wykazać supremację kwantową , sprawy stają się trudne. Chcesz znaleźć próg, powyżej którego urządzenia kwantowe są lepsze od klasycznych, ale sprowadza się to do porównania dwóch radykalnie różnych rodzajów urządzeń, działających radykalnie różnych rodzajów algorytmów . Nie ma łatwego (znanego?) Sposobu na zrobienie tego. Na przykład, czy bierzesz pod uwagę koszt budowy dwóch różnych urządzeń? A co z porównaniem klasycznego urządzenia ogólnego przeznaczenia z kwantowym urządzeniem specjalnego przeznaczenia? Czy to w porządku? Co z walidacjączy wyjście urządzenia kwantowego jest wymagane? A także, jak surowo wymagasz wyników swojej złożoności? Proponowana rozsądna lista kryteriów dla eksperymentu kwantowej supremacji, podana przez Harrowa i Montanaro ( nature23458 , paywalled), to1:

  1. Dobrze zdefiniowany problem obliczeniowy.
  2. Algorytm kwantowy rozwiązujący problem, który może działać na krótkoterminowym sprzęcie zdolnym do radzenia sobie z hałasem i niedoskonałościami.
  3. Szereg zasobów obliczeniowych (czas / przestrzeń) dozwolonych każdemu klasycznemu konkurentowi.
  4. Niewielka liczba dobrze uzasadnionych założeń teoretycznych dotyczących złożoności.
  5. metoda weryfikacji, która może skutecznie rozróżniać wydajność algorytmu kwantowego od dowolnego klasycznego konkurenta wykorzystującego dozwolone zasoby.

Aby lepiej zrozumieć ten problem, można rzucić okiem na dyskusje wokół twierdzeń D-Wave z 2005 r. O „108speedup "za pomocą swojego urządzenia (które działa tylko przy użyciu odpowiednich porównań). Zobacz na przykład dyskusje na blogu Scotta Aaronsona i odnośniki do niego (i oczywiście oryginalny artykuł Dencheva i in. ( 1512.02206 )).

Również w odniesieniu do dokładnych progów oddzielających „klasyczny” od reżimu „supremacji kwantowej”, można rzucić okiem na dyskusje wokół liczby fotonów wymaganych do twierdzenia o supremacji kwantowej w eksperymencie próbkowania bozonów. Podana liczba wynosiła początkowo około 20 i 30 ( między innymi Aaronson 2010 , Preskill 2012 , Bentivegna i in. 2015 ), następnie na krótko spadła do siedmiu ( Latmiral i in. 2016 ), a następnie ponownie wzrosła do około 50 ( Neville i in. 2017 , a możesz rzucić okiem na krótką dyskusję o tym wyniku tutaj ).

Istnieje wiele innych podobnych przykładów, o których tu nie wspomniałem. Na przykład jest cała dyskusja wokół przewagi kwantowej za pomocą obwodów IQP lub liczby kubitów, które są niezbędne, zanim klasyczne urządzenie nie będzie w stanie symulować ( Neill i in. 2017 , Pednault i in. 2017 , oraz kilka innych dyskusji na temat tych wyników) . Kolejną miłą recenzją, której nie uwzględniłem powyżej, jest Lund i in. Artykuł z 2017 r .

(1) Korzystam z przeredagowania kryteriów podanych w Calude i Calude ( 1712.01356 ).

glS
źródło