W 1994 roku matematyk wymyślił, jak sprawić, by komputer kwantowy zrobił coś, czego nie byłby w stanie zrobić żaden zwykły klasyczny komputer. Prace wykazały, że w zasadzie maszyna oparta na zasadach mechaniki kwantowej mogłaby skutecznie rozbić dużą liczbę na czynniki pierwsze, co jest zadaniem tak trudnym dla klasycznego komputera, że stanowi podstawę większości współczesnych zabezpieczeń Internetu.
Nastąpił przypływ optymizmu. Być może, myśleli naukowcy, będziemy w stanie wynaleźć algorytmy kwantowe, które rozwiążą wiele różnych problemów.
Ale postęp utknął w martwym punkcie. „To była trochę marna trajektoria”, powiedział Ryan O'Donnell Uniwersytetu Carnegie Mellon. „Ludzie mówili: 'To niesamowite, jestem pewien, że dostaniemy wiele innych niesamowitych algorytmów'. Nie." Naukowcy odkryli dramatyczne przyspieszenia tylko dla jednej, wąskiej klasy problemów ze standardowego zestawu zwany NP, co oznacza, że mają rozwiązania, które można skutecznie weryfikować, takie jak faktoring.
Tak było przez prawie trzy dekady. Następnie w kwietniu badacze wynalazł całkowicie nowy rodzaj problemu, który komputer kwantowy powinien być w stanie rozwiązać wykładniczo szybciej niż komputer klasyczny. Polega ona na obliczaniu danych wejściowych do skomplikowanego procesu matematycznego, opartego wyłącznie na jego pomieszanych danych wyjściowych. To, czy problem występuje sam, czy też jest pierwszym na nowej granicy wielu innych, nie zostało jeszcze ustalone.
„Wyczuwa się podekscytowanie”, powiedział Vinod Vaikuntanathan, informatyk z Massachusetts Institute of Technology. „Wiele osób myśli o tym, co jeszcze tam jest”.
Informatycy próbują zrozumieć, co komputery kwantowe robią lepiej, badając modele matematyczne, które je reprezentują. Często wyobrażają sobie model komputera kwantowego lub klasycznego w połączeniu z wyidealizowaną maszyną liczącą zwaną wyrocznią. Wyrocznie są jak proste funkcje matematyczne lub programy komputerowe, pobierające dane wejściowe i wyrzucające z góry określone dane wyjściowe. Mogą mieć losowe zachowanie, wyprowadzając „tak”, jeśli dane wejściowe mieszczą się w pewnym losowym zakresie (powiedzmy, od 12 do 67) i „nie”, jeśli nie. Lub mogą być okresowe, tak że dane wejściowe od 1 do 10 zwracają „tak”, 11 do 20 dają „nie”, 21 do 30 dają ponownie „tak” i tak dalej.
Powiedzmy, że masz jedną z tych okresowych wyroczni i nie znasz okresu. Wszystko, co możesz zrobić, to podać mu numery i zobaczyć, co generuje. Biorąc pod uwagę te ograniczenia, jak szybko komputer może znaleźć okres? W 1993 roku Daniel Simon, pracujący wówczas na Uniwersytecie w Montrealu, odkrył, że algorytm kwantowy może obliczyć odpowiedź na ściśle powiązany problem wykładniczo szybciej niż jakikolwiek algorytm klasyczny.
Wyniki umożliwiły Simonowi określenie jednej z pierwszych wskazówek, gdzie można się spodziewać dramatycznej wyższości komputerów kwantowych. Ale kiedy przedstawił swoją pracę na wiodącej konferencji, została ona odrzucona. Artykuł zainteresował jednak młodszego członka komitetu programowego konferencji — Piotr Szor, który w tym czasie przebywał w Bell Laboratories w New Jersey. Shor przekonał się, że potrafi przystosować algorytm Simona do obliczania okresu wyroczni, jeśli taki ma. Potem zdał sobie sprawę, że może ponownie zaadaptować algorytm, aby rozwiązać równanie, które zachowuje się podobnie do wyroczni okresowej: równanie opisujące faktoring, który jest okresowy.
Wynik Shora był historyczny. Odkryty przez niego algorytm kwantowy może szybko zredukować gigantyczne liczby do ich składowych czynników pierwszych, czego nie potrafi żaden znany algorytm klasyczny. W następnych latach naukowcy odkryli inne wydajne algorytmy kwantowe. Niektóre z nich, jak algorytm Shora, zapewniały nawet wykładniczą przewagę, ale nikt nie był w stanie udowodnić ogromnej przewagi kwantowej w przypadku jakiegokolwiek problemu NP, który nie był okresowy.
Ten brak postępu doprowadził dwóch informatyków, Scott aaronson Uniwersytetu Teksańskiego w Austin oraz Andrisa Ambainisa Uniwersytetu Łotewskiego w celu dokonania obserwacji. Dowody przewagi kwantowej zawsze wydawały się zależne od wyroczni, które miały jakąś nielosową strukturę, taką jak okresowość. W 2009 roku domysł że nie może być dramatycznych przyspieszeń w przypadku problemów z NP, które byłyby przypadkowe lub nieustrukturyzowane. Nikt nie mógł znaleźć wyjątku.
Ich przypuszczenie powiązało moc komputerów kwantowych. Ale powiedział tylko, że nie było dramatycznych przyspieszeń dla określonego typu nieustrukturyzowanego problemu NP — tych z odpowiedziami „tak” lub „nie”. Jeśli problem polegał na znalezieniu bardziej szczegółowych, ilościowych odpowiedzi, co jest znane jako problem wyszukiwania, przypuszczenie nie miało zastosowania.
Mając to na uwadze, naukowcy Takashiego Yamakawy Laboratoriów Informatyki Społecznej NTT oraz Marek Zhandry NTT Research i Princeton University postanowiły poeksperymentować z konkretnym problemem wyszukiwania, wprowadzonym w 2005 roku przez Oded Regev.
Wyobraź sobie zestaw wiatrowskazów, które są skierowane w tym samym kierunku. Daj każdemu z nich miarowy pchnięcie, a następnie pozwól, aby porywisty wiatr wpłynął na ich kierunek. Regev chciał ustalić, na podstawie ich ostatecznych kierunków, gdzie wszyscy początkowo wskazywali. Takie problemy zaczęto nazywać „uczeniem się z błędami”, ponieważ pchnięcie i wiatr działają jak źródło przypadkowych błędów w pierwotnym kierunku. Istnieją dowody na to, że jest to trudne do rozwiązania zarówno dla algorytmów klasycznych, jak i kwantowych.
Yamakawa i Zhandry poprawili konfigurację. Zmodyfikowali siłę tych początkowych pchnięć, czyniąc je bardziej przewidywalnymi. Spowodowali również, że wiatr był określany przez losową wyrocznię, tak że w niektórych przypadkach był jeszcze bardziej losowy, ale w innych całkowicie uśpiony.
Dzięki tym modyfikacjom naukowcy odkryli, że algorytm kwantowy może skutecznie znaleźć początkowy kierunek. Udowodnili również, że każdy klasyczny algorytm musi być wolniejszy o współczynnik wykładniczy. Podobnie jak Shor, zaadaptowali swój algorytm, aby rozwiązać prawdziwą wersję problemu, w której wyrocznię zastąpiono rzeczywistym równaniem matematycznym.
Informatycy wciąż pracują nad zrozumieniem i rozwinięciem problemu. Vaikuntanathan porównuje to do innego, który pojawia się podczas kompresji danych: Kiedy informacja jest ściśnięta, dwa bity mogą przypadkowo zostać ściśnięte w tym samym miejscu, nadpisując je. Problem z przewidywaniem tych kolizji z wyprzedzeniem, aby można było ich uniknąć, jest trochę podobny. „To jest klasa problemów, które zasadniczo wyglądają tak” – powiedział. „Może te problemy da się rozwiązać ilościowo”.
Istniały nadzieje, że nieustrukturyzowany problem, taki jak nowy, może być rozwiązany nawet na dzisiejszych raczkujących wersjach komputerów kwantowych, zapewniając w ten sposób możliwość ich przetestowania. Pomyślano, że nieustrukturyzowane problemy mogą wymagać mniej zasobów do zaprogramowania lub być mniej wrażliwe na zakłócenia, ponieważ są już losowe. Ale jak dotąd nowy problem wciąż wydaje się zbyt zaawansowany, aby można było rozwiązać istniejące komputery kwantowe. „To dziwny problem. Nie myślałem, żeby to zdefiniować – powiedział Aaronson. „Ale z perspektywy czasu ma kilka bardzo fajnych funkcji”.
Wynik stanowi pierwszy przykład ogromnej przewagi kwantowej w nieustrukturyzowanym problemie nanocząsteczkowym. Czy może istnieć wiele innych problemów, które świat kwantowy zmienia się z praktycznie nierozwiązywalnego na rozwiązywalny? Teraz jest więcej powodów, by tak sądzić.
„To nieco obaliło nasze przekonania o tym, w jakich rodzajach problemów komputery kwantowe mogą być dobre” — powiedział O'Donnell.
