Czy istnieje formalny dowód, że obliczenia kwantowe są lub będą szybsze niż obliczenia klasyczne?

Zamiast dowodów empirycznych, jakie formalne zasady udowodniliśmy, że obliczenia kwantowe będą szybsze niż obliczenia tradycyjne / klasyczne?

To pytanie jest nieco trudne do rozpakowania, jeśli nie znasz złożoności obliczeniowej. Podobnie jak większość dziedziny złożoności obliczeniowej, powszechnie uważa się, że główne wyniki są przypuszczalne.

Klasami złożoności zwykle związanymi z wydajnym obliczeniem klasycznym są (dla algorytmów deterministycznych) i B P P (dla randomizowanych). Odpowiednikiem kwantowa z tych klas ma B P P . Wszystkie trzy klasy są podzbiorami P S P A C E (klasa bardzo potężna). Jednak nasze obecne metody dowodowe nie są wystarczająco silne, aby ostatecznie wykazać, że P nie jest to samo co P S P A C E . Zatem nie wiemy, jak formalnie oddzielić P od B Q $\mathsf{P}$$\mathsf{BPP}$$\mathsf{BQP}$$\mathsf{PSPACE}$$\mathsf{P}$$\mathsf{PSPACE}$$\mathsf{P}$$\mathsf{BQP}$albo - od , oddzielenie tych dwóch klas jest twardszy niż już groźnego zadania rozdzielania P, z P S P A C E . (Gdybyśmy mogli udowodnić, że P ≠ B Q P , natychmiast uzyskalibyśmy dowód, że P ≠ P S P A C E , a więc dowód P ≠ B Q $\mathsf{P \subseteq BQP \subseteq PSPACE}$$\mathsf{P}$$\mathsf{PSPACE}$$\mathsf{P \ne BQP}$$\mathsf{P \ne PSPACE}$$\mathsf{P \ne BQP}$musi być co najmniej tak samo trudny jak i tak już bardzo trudny problem udowodnienia ). Z tego powodu w obecnym stanie techniki trudno jest uzyskać ścisły matematyczny dowód pokazujący, że obliczenia kwantowe będą szybsze niż obliczenia klasyczne.$\mathsf{P \ne PSPACE}$

Dlatego zwykle polegamy na poszlakach na rozdzielenie klas złożoności. Nasze najsilniejsze i najbardziej znanym dowodem jest algorytm Shor za to, że pozwala nam czynnik . W przeciwieństwie do tego, nie znamy żadnego algorytmu, który mógłby uwzględniać B P P - i większość ludzi uważa, że ​​nie istnieje; jest to na przykład jeden z powodów, dla których używamy RSA do szyfrowania. Z grubsza mówiąc, oznacza to, że komputer kwantowy może być efektywnie rozkładać na czynniki, ale sugeruje, że klasyczny komputer może nie być w stanie efektywnie rozkładać na czynniki. Z tych powodów wynik Shora zasugerował wielu, że B Q P jest ściśle silniejszy niż B P $\mathsf{BQP}$$\mathsf{BPP}$$\mathsf{BQP}$$\mathsf{BPP}$(a zatem także silniejszy niż ).$\mathsf{P}$

Nie znam żadnych poważnych argumentów, że , z wyjątkiem tych, którzy wierzą w znacznie większą złożoność załamują się (stanowią mniejszość społeczności). Najpoważniejsze argumenty, jakie słyszałem przeciwko obliczeniom kwantowym, pochodzą z postaw bliższych fizyce i dowodzą, że B Q P nie oddaje poprawnie natury obliczeń kwantowych. Argumenty te zazwyczaj mówią, że makroskopijne spójne stany są niemożliwe do utrzymania i kontrolowania (np. Ponieważ istnieje jeszcze nieznana podstawowa fizyczna blokada drogi), a zatem operatorzy, na których polega B Q P, nie mogą zostać zrealizowani (nawet zasadniczo) w naszym świecie .$\mathsf{BQP = P}$$\mathsf{BQP}$$\mathsf{BQP}$

Jeśli zaczniemy przechodzić na inne modele obliczeń, szczególnie łatwym modelem do pracy jest kwantowa złożoność zapytań (klasyczna wersja, która odpowiada, to złożoność drzewa decyzyjnego). W tym modelu dla funkcji całkowitych możemy udowodnić, że (w przypadku niektórych problemów) algorytmy kwantowe mogą osiągnąć przyspieszenie kwadratowe, chociaż możemy również wykazać, że dla funkcji całkowitych nie możemy zrobić lepiej niż przyspieszenie potęgi-6 i wierzymy, że kwadrat jest przyspieszeniem Najlepsza możliwość. W przypadku funkcji częściowych jest to zupełnie inna historia i możemy udowodnić, że możliwe są wykładnicze przyspieszenia. Ponownie, argumenty te opierają się na przekonaniu, że dobrze rozumiemy mechanikę kwantową i nie ma żadnej magicznej nieznanej teoretycznej bariery w powstrzymywaniu kontroli makroskopowych stanów kwantowych.

Ze względu na złożoność obliczeniową nie ma dowodów na to, że komputery kwantowe są lepsze niż komputery klasyczne ze względu na to, jak trudno jest osiągnąć dolne granice twardości problemów. Istnieją jednak ustawienia, w których komputer kwantowy okazuje się lepszy niż klasyczny. Najbardziej znanym z tych przykładów jest model blackbox, w którym masz dostęp przez blackbox do funkcji i chcesz znaleźć unikalny x, dla którego f jest równy 1. Miarą złożoności w tym przypadku jest liczba połączeń z $f:\{0,1\}^n\mapsto \{0,1\}$$x$$f$$f$. Klasycznie nie można zrobić nic lepszego niż zgadywanie losowe które zajmuje średnio Ω ( 2 n ) zapytaniom do f . Jednak za pomocą algorytmu Grovera możesz osiągnąć to samo zadanie w O ( $x$$\Omega(2^n)$$f$.$O(\sqrt{2^n})$

Aby uzyskać dalsze możliwe do udowodnienia separacje, możesz spojrzeć na złożoność komunikacji, w której wiemy, jak udowodnić dolne granice. Istnieją zadania, które dwa komputery kwantowe komunikujące się kanałem kwantowym mogą wykonać przy mniejszej komunikacji niż dwa komputery klasyczne. Na przykład obliczenie iloczynu wewnętrznego dwóch łańcuchów, jednego z najtrudniejszych problemów w złożoności komunikacji, przyspiesza przy użyciu komputerów kwantowych.

Artem Kaznatcheev zapewnia znakomite podsumowanie niektórych kluczowych powodów, dla których spodziewamy się, że komputery kwantowe będą zasadniczo szybsze od klasycznych komputerów do niektórych zadań.

Jeśli chcesz trochę dodatkowej lektury, możesz przeczytać notatki z wykładu Scotta Aaronsona na temat obliczeń kwantowych , które omawiają algorytm Shora i inne algorytmy, które dopuszczają wydajne algorytmy kwantowe, ale nie wydają się dopuszczać żadnego wydajnego klasycznego algorytmu.

Jest to nie jest BQP dokładny model rzeczywistości, czy jest coś, co może uniemożliwić nam zbudowanie komputera kwantowego, zarówno ze względów technicznych lub z powodu podstawowych barier fizycznych: dyskusja o tym, czy komputery kwantowe mogą być budowane w praktyce? Możesz przeczytać notatki z wykładu Scotta Aaronsona podsumowujące argumenty podniesione przez innych, a także przeczytać jego post na blogu z jego poglądem na tę debatę , ale prawdopodobnie nie będziemy mieć ostatecznej odpowiedzi, dopóki ktoś nie zbuduje komputera kwantowego, który może wykonywać niebanalne zadania (takie jak duże liczby).

Podstawowym gmachem obliczeń kwantowych jest transformacja Unitary, jest to podstawowe narzędzie do przyspieszenia wielu algorytmów w literaturze. Algorytmy wykorzystujące jednostki Unitaries wykorzystują teoretyczne właściwości liczbowe / graficzne problemów w zasięgu ręki - znajdowanie okresu, przyspieszenie w spacerach kwantowych itp. Przyspieszenia w naturalnych problemach są wciąż nieuchwytne - jak wskazano. To, czy faktoring dużych liczb jest celem samym w obliczeniach kwantowych, jest wciąż pytaniem otwartym. Inne otwarte pytania, takie jak QNC, jego oddzielenie od NC nadal mogą dostarczyć nieuchwytnych wskazówek na temat tego, co mogą zrobić komputery kwantowe. Ale jeśli celem komputera kwantowego jest uwzględnienie dużych liczb - może to być jeszcze wykonalne, samo w sobie w przyszłości, z przerażającymi konsekwencjami (oczywiście dla prywatności)!

Chciałem odpowiedzieć na komentarze Niel de Beaudrap dotyczące źródła przyspieszeń kwantowych, ale nie mogę tego skomentować. Nie wiem, czy mogę opublikować odpowiedź.

Moim zdaniem wszystkie przyspieszenia kwantowe są spowodowane splątaniem. Jedynym algorytmem, w którym możemy zrobić coś szybciej niż klasyczne komputery bez użycia stanów splątanych, jest Deutsch-Jozsa do obliczania parzystości dwóch bitów. Jeśli dyskutujemy o asymptotycznych przyśpieszeniach, uwikłanie jest konieczne, a właściwie dużo. Jeśli algorytm kwantowy wymaga niewielkiej ilości splątania, można go skutecznie symulować klasycznie. Mogę wskazać artykuł http://arxiv.org/abs/quant-ph/0201143 , który szczegółowo omawia algorytm faktoringu i ilość wymaganego splątania.

jest to prawie to samo kluczowe pytanie, które napędza setki milionów, a może miliardy dolarów inicjatyw badawczych w dziedzinie QM, zarówno publicznych, jak i prywatnych na całym świecie. pytanie jest atakowane jednocześnie eksperymentalnie i teoretycznie, a postępy z każdej strony przenoszą się na drugą stronę.

pytanie próbuje starannie oddzielić teoretyczne i pragmatyczne / eksperymentalne aspekty tego pytania, ale eksperymentator lub inżynier twierdziłby, że są ściśle ze sobą powiązane, nierozłączne, a dotychczasowy postęp historyczny w kwestii wyzwania jest tego dowodem / dowodem.

poniższy punkt z pewnością nie wygra żadnych konkursów popularności (być może z powodu dobrze znanej / obserwowanej stronniczości, że negatywne wyniki są rzadko zgłaszane naukowo), ale warto zauważyć, że istnieje opinia mniejszości / przeciwników promowana przez różne wiarygodne , nawet elitarni badacze, że obliczenia QM mogą lub nigdy nie zmaterializują się fizycznie z powodu niemożliwych do pokonania wyzwań związanych z wdrożeniem, i istnieje nawet teoretyczne uzasadnienie / analiza (ale może bardziej z fizyki teoretycznej niż TCS). (i zauważ, że niektórzy mogą mieć wątpliwości, ale nie chcą zapisywać kwestionowania „dominującego paradygmatu”). główne argumenty opierają się na nieodłącznym hałasie QM, zasadzie niepewności Heisenberga i fundamentalnym eksperymentalnym chaosie konfiguracji QM itp.

obecnie istnieją dość solidne dwie dekady badań teoretycznych i eksperymentalnych, a frakcja mniejszościowa argumentowałaby, że dotychczasowe wyniki nie są zachęcające, słabe, a nawet zbliżają się do ostatecznej negatywnej odpowiedzi.

jednym z najbardziej otwartych zwolenników negatywnego poglądu (graniczącego z ekstremalnym / zjadliwym!) jest Dyakonov, ale mimo to z pasją argumentuje tę sprawę na podstawie wszystkich punktów widzenia:

• Stan techniki i perspektywy obliczeń kwantowych / Dyakonov

• Perspektywy obliczeń kwantowych: bardzo wątpliwe / Dyakonov

można oskarżyć Dyakonowa o niemal polemikę, ale służy on jako niemal symetryczny kontrapunkt dla niektórych zwolenników obliczeń QM, którzy mają gorącą wiarę w przeciwną pozycję (że prawie absolutnie nie ma wątpliwości co do jej przyszłej / ostatecznej / nieuniknionej żywotności). innym ważnym teoretykiem argumentującym za nieodłącznymi ograniczeniami w obliczeniach QM (opartych na hałasie) jest Kalai. tutaj jest długa debata między nim a Harrowem na ten temat.

• Perpetual Motion of the 21st Century?

naturalne jest również wyciągnięcie jakiejś luźnej analogii do innego ogromnego / złożonego projektu fizyki, który do tej pory nie osiągnął swojego ostatecznego celu po dziesięcioleciach prób i optymistycznych wczesnych prognoz, eksperymentów z wytwarzaniem energii .