Choć badacze opublikowali setki algorytmów kwantowych, do kanonu weszło zaledwie kilka — te, które dają udowodnione przyspieszenie lub realną nadzieję na praktyczne zastosowanie. Oto najważniejsze z nich.
Algorytm Shora (1994) — łamacz szyfrów
Co robi: rozkłada wielkie liczby na czynniki pierwsze i rozwiązuje pokrewne problemy (logarytm dyskretny). Przyspieszenie: wykładnicze — zadanie nie do wykonania klasycznie staje się wykonalne. Znaczenie: zagraża szyfrom RSA i ECC, na których stoi bezpieczeństwo internetu; to on uruchomił globalną migrację do kryptografii postkwantowej. Wymaga dużego komputera z korekcją błędów — dotąd faktoryzowano nim jedynie symboliczne liczby, jak 15 czy 21.
Algorytm Grovera (1996) — szukanie igły w stogu siana
Co robi: znajduje element spełniający warunek w nieuporządkowanym zbiorze. Przyspieszenie: kwadratowe — milion możliwości sprawdzamy w czasie odpowiadającym tysiącowi prób. Znaczenie: uniwersalny „dopalacz” do przeszukiwania i problemów typu „znajdź kombinację”; w kryptografii zmusza do wydłużenia kluczy symetrycznych (np. AES-128 → AES-256). Kwadratowe przyspieszenie jest jednak na dzisiejszym sprzęcie zbyt małe, by opłacało się w praktyce.
VQE (2014) — chemik kwantowy
Co robi: wariacyjnie znajduje stan o najniższej energii cząsteczki lub materiału — klucz do przewidywania reakcji chemicznych. Typ: hybrydowy (komputer kwantowy + klasyczny optymalizator), zaprojektowany specjalnie pod dzisiejszy „szumny” sprzęt. Znaczenie: najczęściej uruchamiany algorytm w chemii kwantowej i materiałoznawstwie; przyspieszenie nie jest gwarantowane matematycznie, ale podejście skaluje się wraz z postępem sprzętu.
QAOA (2014) — optymalizator
Co robi: szuka przybliżonych rozwiązań problemów kombinatorycznych — trasy pojazdów, harmonogramy, portfele inwestycyjne. Typ: hybrydowy, jak VQE. Znaczenie: najpopularniejszy algorytm optymalizacyjny na komputery bramkowe i bramkowy „konkurent” wyżarzania D-Wave; czy da realną przewagę nad metodami klasycznymi — to wciąż otwarte pytanie badawcze.
Kwantowe Monte Carlo / szacowanie amplitudy
Co robi: przyspiesza symulacje losowe używane w finansach i inżynierii. Przyspieszenie: kwadratowe. Znaczenie: największa nadzieja sektora finansowego — szczegóły w artykule o metodzie Monte Carlo. Wymaga sprzętu z korekcją błędów.
HHL (2009) — równania liniowe
Co robi: rozwiązuje wielkie układy równań liniowych — fundament inżynierii i uczenia maszynowego. Przyspieszenie: wykładnicze, ale z ważnymi gwiazdkami: dane trzeba umieć szybko załadować, a wynikiem jest stan kwantowy, nie gotowa lista liczb. Znaczenie: zapalnik całej dziedziny kwantowego uczenia maszynowego (QML).
Ściąga
| Algorytm | Do czego | Przyspieszenie | Kiedy użyteczny |
|---|---|---|---|
| Shor | łamanie RSA/ECC | wykładnicze | po zbudowaniu dużych maszyn z korekcją błędów |
| Grover | przeszukiwanie | kwadratowe | odległa przyszłość |
| VQE | chemia, materiały | heurystyczne | testowany już dziś |
| QAOA | optymalizacja | heurystyczne | testowany już dziś |
| Kwantowe Monte Carlo | finanse, ryzyko | kwadratowe | ok. 2030 (szacunki) |
| HHL | równania liniowe, ML | wykładnicze* | odległa przyszłość |