Nowy algorytm kwantowy przyspiesza rozwiązywanie ogromnej klasy problemów

Oryginalna wersja tej historii ukazała się w magazynie Quanta .

Dla informatyków rozwiązywanie problemów jest trochę jak wspinaczka górska. Najpierw muszą wybrać problem do rozwiązania — podobnie jak zidentyfikować szczyt, na który należy się wspiąć — a następnie opracować strategię jego rozwiązania. Klasyczni i kwantowi badacze konkurują ze sobą, używając różnych strategii, a między nimi panuje zdrowa rywalizacja. Kwantowi badacze zgłaszają szybki sposób rozwiązania problemu — często poprzez wspinaczkę na szczyt, na który nikt nie uważał, że warto się wspiąć — a następnie klasyczne zespoły ścigają się, aby zobaczyć, czy mogą znaleźć lepszy sposób.

Ten konkurs prawie zawsze kończy się wirtualnym remisem: gdy naukowcy uważają, że opracowali algorytm kwantowy, który działa szybciej lub lepiej niż cokolwiek innego, klasyczni naukowcy zazwyczaj wymyślają taki, który mu dorównuje. Zaledwie w zeszłym tygodniu rzekome przyspieszenie kwantowe, opublikowane w czasopiśmie Science , spotkało się z natychmiastowym sceptycyzmem dwóch odrębnych grup, które pokazały, jak wykonywać podobne obliczenia na klasycznych maszynach.

Ale w artykule opublikowanym na stronie naukowych preprintów arxiv.org w zeszłym roku, badacze opisali coś, co wygląda na przyspieszenie kwantowe, które jest zarówno przekonujące, jak i użyteczne . Badacze opisali nowy algorytm kwantowy, który działa szybciej niż wszystkie znane klasyczne algorytmy, jeśli chodzi o znajdowanie dobrych rozwiązań dla szerokiej klasy problemów optymalizacyjnych (które szukają najlepszego możliwego rozwiązania spośród ogromnej liczby wyborów).

Jak dotąd żaden klasyczny algorytm nie zdetronizował nowego algorytmu, znanego jako zdekodowana interferometria kwantowa (DQI). To „przełom w algorytmach kwantowych”, powiedział Gil Kalai , matematyk z Reichman University i wybitny sceptyk komputerów kwantowych . Doniesienia o algorytmach kwantowych ekscytują badaczy, częściowo dlatego, że mogą one rzucić światło na nowe pomysły dotyczące trudnych problemów, a częściowo dlatego, że pomimo całego szumu wokół maszyn kwantowych nie jest jasne, które problemy faktycznie na nich skorzystają. Algorytm kwantowy, który przewyższa wszystkie znane algorytmy klasyczne w zadaniach optymalizacji, stanowiłby duży krok naprzód w wykorzystaniu potencjału komputerów kwantowych.

„Jestem tym entuzjastycznie nastawiony” — powiedział Ronald de Wolf , teoretyk informatyki w CWI, krajowym instytucie badawczym matematyki i informatyki w Holandii, który nie był zaangażowany w nowy algorytm. Jednocześnie jednak ostrzegł, że nadal jest całkiem możliwe, że badacze w końcu znajdą klasyczny algorytm, który będzie działał równie dobrze. A ze względu na brak sprzętu kwantowego minie jeszcze trochę czasu, zanim będą mogli przetestować nowy algorytm empirycznie.

Algorytm może zainspirować nowe prace po stronie klasycznej, według Ewin Tang , informatyka z University of California w Berkeley, która zyskała sławę jako nastolatka , tworząc klasyczne algorytmy, które dorównują algorytmom kwantowym . Nowe twierdzenia „są na tyle interesujące, że powiedziałabym ludziom zajmującym się algorytmami klasycznymi: 'Hej, powinniście przeczytać ten artykuł i zająć się tym problemem'” — powiedziała.

Kiedy klasyczne i kwantowe algorytmy konkurują, często dzieje się to na polu bitwy optymalizacji, polu skupionym na znalezieniu najlepszych opcji rozwiązania trudnego problemu. Naukowcy zazwyczaj skupiają się na problemach, w których liczba możliwych rozwiązań gwałtownie rośnie wraz ze wzrostem problemu. Jaki jest najlepszy sposób, aby ciężarówka dostawcza odwiedziła 10 miast w ciągu trzech dni? Jak należy pakować paczki na pace? Klasyczne metody rozwiązywania tych problemów, które często obejmują przeszukiwanie możliwych rozwiązań w sprytny sposób, szybko stają się nie do utrzymania.

Konkretny problem optymalizacji, którym zajmuje się DQI, wygląda mniej więcej tak: Masz zbiór punktów na kartce papieru. Musisz wymyślić funkcję matematyczną, która przechodzi przez te punkty. Konkretnie, Twoja funkcja musi być wielomianem — kombinacją zmiennych podniesionych do wykładników liczb całkowitych i pomnożonych przez współczynniki. Ale nie może być zbyt skomplikowana, co oznacza, że ​​potęgi nie mogą być zbyt wysokie. Daje Ci to zakrzywioną linię, która wije się w górę i w dół, gdy przesuwa się po stronie. Twoim zadaniem jest znalezienie krętej linii, która dotyka największej liczby punktów.

Odmiany tego problemu pojawiają się w różnych formach w informatyce, szczególnie w kodowaniu błędów i kryptografii — dziedzinach skupionych na bezpiecznym i dokładnym kodowaniu danych podczas ich przesyłania. Badacze DQI uznali, że wykreślenie lepszej linii jest w zasadzie podobne do przesunięcia zakodowanej wiadomości w kierunku jej dokładnego znaczenia.

Ale to wszystko przyszło później. Kiedy badacze stojący za DQI zaczęli pracować nad swoim algorytmem, nie mieli nawet tego problemu na myśli.

„Byłoby całkowicie prawdopodobne, aby badacz zorientowany na cel zaczął od sformułowania problemu, a następnie zbadał, czy algorytmy kwantowe mogą go rozwiązać szybciej niż algorytmy klasyczne” — powiedział Stephen Jordan , fizyk w Google Quantum AI i jeden z głównych architektów DQI. „Oczywiście, dla nas nie tak to się stało. Trafiliśmy na to okrężną i odwrotną drogą”.

Jordan wybrał tę drogę w 2023 roku, kiedy dołączył do Google i dowiedział się, że będzie pracował z Eddiem Farhim , fizykiem w Google, którego praca od dawna skupia się na algorytmach kwantowych, które przewyższają klasyczne. (Farhi był kiedyś doradcą doktorskim Jordana w Massachusetts Institute of Technology.) Jordan wiedział, że w 2014 roku Farhi przeprowadził atak kwantowy na problem optymalizacji, myśląc o energii, przy czym niższe energie odpowiadały lepszym rozwiązaniom. Dla Farhiego energia łączyła optymalizację z fizyką kwantową.

Ale Jordan chciał zrobić coś innego. Zwrócił się ku innej koncepcji wbudowanej w fizykę kwantową — uznając wszystko za fale. Używając narzędzia matematycznego zwanego kwantową transformacją Fouriera, Jordan znalazł sposób na przetłumaczenie wszystkich potencjalnych odpowiedzi na dobrze znaną klasę problemów optymalizacyjnych na fale kwantowe. Dzięki temu mógł manipulować układem kwantowym tak, aby większe fale (w formie wyższych amplitud kwantowych) odpowiadały lepszym rozwiązaniom.

Ale wciąż istniało ogromne wyzwanie, które należało pokonać. W systemie kwantowym pytanie „Jaka jest największa amplituda?” nie jest tak proste, jak rozpoznanie największej fali na plaży. Krajobraz kwantowy jest niewiarygodnie złożony i nie było jasne, jak zidentyfikować amplitudy kwantowe, które odpowiadałyby najlepszym rozwiązaniom.

Po wielu fałszywych startach Jordan dokonał przełomu: proces wybierania najlepszych rozwiązań okazał się podobny do procesu usuwania błędów w zakodowanych wiadomościach, znanego jako dekodowanie. Jest to dobrze zbadany obszar informatyki, pełen technik, które Jordan mógł zbadać. Przekładając problem optymalizacji na problem kwantowy, a następnie stosując do niego soczewkę dekodowania, natknął się na nowy sposób opracowywania algorytmów kwantowych.

Razem z Noahem Shuttym , również w Google, Jordan zaczął testować schematy dekodowania, sprawdzając, jak radzą sobie z klasycznymi algorytmami w różnych problemach optymalizacji. Potrzebowali zarówno właściwego podejścia, jak i problemu, w którym to zadziała. „Okazuje się, że klasyczne algorytmy są trudne do pokonania” — powiedział Jordan. „Po kilku miesiącach prób nadal nie odnotowaliśmy żadnych zwycięstw w kwantowym”.

Ale ostatecznie para wylądowała na algorytmie dekodującym wprowadzonym po raz pierwszy w latach 60. XX wieku, aby znaleźć i naprawić pojedyncze błędy w zakodowanej wiadomości. Znalezienie tego problemu było kluczem. „Kiedy to zbadaliśmy, wydawało się, że odnieśliśmy sukces niemal natychmiast” — powiedział Jordan. W końcu znaleźli problem i podejście, które razem wyglądały jak przyspieszenie kwantowe.

Oczywiście, nie oznaczało to, że jest to kuloodporne. „Być może istnieje jakaś klasyczna metoda, która może skutecznie odtworzyć całe twoje podejście” — powiedział Jordan. „Takie dekwantyzacje nie zawsze są oczywiste”.

Aby rozwiać te obawy, skonsultowali się z Mary Wootters , ekspertką w dziedzinie teorii kodowania (i byłą promotorką doktorską Shutty'ego na Uniwersytecie Stanforda). Starannie przeszukała ona każdy znany klasyczny algorytm, który mógłby dorównać ich kwantowemu przyspieszeniu. Przewaga się utrzymała. Kontrole zespołu również sugerują, że tak będzie nadal. „Dokonali należytej staranności” — powiedział Tang.

Wzmocnieni tą analizą, przyjrzeli się uważniej problemowi optymalizacji, który rozwiązywali. Jordan martwił się, że może być zbyt niszowy, bez szerszych zastosowań, ale Shutty uznał, że ten problem dekodowania był odmianą dobrze znanych i użytecznych problemów w szyfrowaniu i innych dziedzinach.

Jordan przyznaje, że bez wystarczająco dużej maszyny kwantowej DQI pozostanie teoretycznym przełomem. „DQI nie może działać na dzisiejszych komputerach kwantowych” — powiedział. Ale nadal idą naprzód. Od czasu opublikowania swojej pracy w sierpniu ubiegłego roku grupa rozszerzyła zastosowanie DQI poza pierwotny problem na szerszą klasę problemów optymalizacyjnych, która obejmuje więcej przypadków tych problemów „najlepszej ścieżki”.

Jordan spodziewa się, że na razie DQI pokona klasyczne algorytmy także w tych problemach.

Na razie społeczność kwantowa pozostaje w euforii. „Znalezienie algorytmów kwantowych, które wykazują przewagę nad algorytmami klasycznymi, to bardzo ekscytujące przedsięwzięcie ostatnich trzech dekad, a liczba określonych algorytmów, które wykazują taką przewagę, nie jest duża” — powiedział Kalai. „Dlatego każdy nowy algorytm jest powodem do świętowania”.

Oryginalny artykuł przedrukowano za zgodą Quanta Magazine , redakcyjnie niezależnej publikacji Fundacji Simonsa , której misją jest pogłębianie wiedzy naukowej wśród społeczeństwa poprzez relacjonowanie osiągnięć badawczych i trendów w matematyce, fizyce i naukach biologicznych.