Simulated Annealing

Dlaczego Optymalizacja Kombinatoryczna Jest Trudna

Problemy optymalizacji kombinatorycznej wymagają znalezienia najlepszego ułożenia spośród ogromnej liczby dyskretnych możliwości, takich jak najlepszy sposób podziału węzłów sieci na dwie grupy w celu odcięcia największej liczby połączeń (problem Max-Cut). Problem polega na tym, że liczba możliwych ułożeń rośnie wykładniczo wraz ze wzrostem rozmiaru problemu, więc sprawdzanie każdego z nich staje się niemożliwe nawet dla umiarkowanych danych wejściowych. Wiele z tych problemów jest klasyfikowanych jako NP-trudne, co oznacza, że nie znamy żadnego znanego algorytmu klasycznego, który mógłby szybko rozwiązać każdy przypadek, zmuszając do polegania na przybliżeniach i heurystykach. To dokładnie taki ogromny gaj, w którym potencjalnie mogą przynieść realną przewagę komputery kwantowe, które potrafią jednocześnie reprezentować wiele możliwości.

To właśnie złożoność problemów optymalizacji kombinatorycznej sprawia, że algorytmy oparte na przeszukiwaniu wszystkich możliwych rozwiązań są niepraktyczne. Zamiast tego, stosuje się metody heurystyczne i przybliżone, które dążą do znalezienia dobrego rozwiązania w rozsądnym czasie, nawet jeśli nie gwarantują optymalności.

Alternujące Warstwy Kosztu i Mieszadła

QAOA, wprowadzona przez Farhi’ego, Goldstone’a i Gutmanna w 2014 roku, koduje kandydatowe rozwiązanie do problemu optymalizacyjnego jako stan kubitów, a następnie wielokrotnie stosuje dwie alternujące się operacje kwantowe. Warstwa kosztowa (cost unitary) aplikuje fazy, które nagradzają konfiguracje kubitów odpowiadające dobrym rozwiązaniom, podczas gdy warstwa mieszadłowa (mixer unitary) rozdziela amplitudy między konfiguracjami, pozwalając algorytmowi na eksplorację sąsiednich rozwiązań. Powtarzanie tego wzoru koszt-mieszadło dla p warstw buduje interferencję, która konstruktywnie wzmacnia wysokiej jakości rozwiązania i destrukcyjnie wycofa słabe rozwiązania. Pomiar końcowego stanu daje bitstring, który z rozsądną dozą prawdopodobieństwa reprezentuje dobre – choć nie gwarantowane optymalne – rozwiązanie oryginalnego problemu.

Dostrajanie Kątów w Hybrydowej Pętli

Każda warstwa algorytmu QAOA posiada dwa parametry, które można dostosować – tradycyjnie nazywane beta i gamma. Parametry te kontrolują siłę działania operacji mieszadła i kosztu podczas danego cyklu. Ponieważ nie istnieje prosta formuła pozwalająca określić optymalne kąty, algorytm QAOA działa jako hybryda obliczeniowo-klasyczna: komputer kwantowy przygotowuje stan i mierzy średni koszt, a klasyczny optymalizator na komputerze stacjonarnym dostosowuje kąty w celu poprawy tego kosztu. Pętla ta powtarza się, z wykorzystaniem procesora kwantowego i optymalizatora klasycznego do wymiany informacji między sobą, stopniowo kierując kąty w stronę wartości, które zapewniają jak najlepsze wyniki pomiarowe. Podział pracy pozwala algorytmowi QAOA na wykorzystanie efektów kwantowych do eksploracji, jednocześnie opierając się na sprawdzonych metodach optymalizacji klasycznej do samego dostrajania.

Rzeczywiste Zastosowania i Obecne Ograniczenia

QAOA najczęściej badane jest na problemach grafowych, takich jak Max-Cut, a także w szerszym zakresie na zadaniach, które można sformułować jako minimalizację funkcji kosztowej nad zmiennymi dyskretnymi, w tym abstrakcyjne wersje planowania, routingu i selekcji kombinatorycznej w stylu portfelowego. Stanowi ona lidera wśród algorytmów dla współczesnego sprzętu NISQ (zaszumione pośrednie skale kwantowe) ze względu na to, że wykorzystuje stosunkowo płytkie obwody, które mogą tolerować pewien poziom szumu. Mimo to, QAOA nie wykazała jeszcze udanego przewagi nad najlepszymi algorytmami klasycznymi w praktycznie ważnym problemie, a jej wydajność zależy w dużym stopniu od głębokości obwodu, jakości optymalizacji kątów i poziomów szumu sprzętowego, co czyni ją nadal aktywnym i niejednoznacznym obszarem badań nad obliczeniami kwantowymi.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz QAOA: Quantum Approximate Optimization Algorithm i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.