Wariacyjny kwantowo-oszczędny heurystyczny algorytm MaxCut

Dlaczego małe układy kwantowe mają znaczenie przy dużych zagadkach

Wiele zadań z rzeczywistego świata — od rozmieszczania układów scalonych po modelowanie materiałów — sprowadza się do podzielenia sieci na dwie grupy przy jednoczesnym przecięciu jak największej liczby połączeń między nimi. To wyzwanie, znane jako MaxCut, jest wyjątkowo trudne dla klasycznych komputerów. Artykuł przedstawia nową metodę inspirowaną kwantowo, która potrafi obsłużyć zaskakująco duże sieci używając zaledwie kilku kubitów, oferując nowe podejście do testowania i ulepszania narzędzi optymalizacyjnych zarówno kwantowych, jak i klasycznych.

Rozciąć sieć na dwie użyteczne połowy

MaxCut zadaje prosto brzmiące pytanie: mając zbiór punktów (węzłów) połączonych liniami (krawędziami), jak pokolorować każdy węzeł, na przykład na niebiesko lub biało, aby jak najwięcej linii łączyło węzły o różnych kolorach? Najlepszy możliwy podział jest cenny w obszarach takich jak projektowanie układów czy fizyka statystyczna, ale jego dokładne znalezienie dla dużych sieci jest bardzo trudne. Szeroko stosowane podejście klasyczne, algorytm Goemansa–Williamsona (GW), robi sprytne złagodzenie problemu i gwarantuje znalezienie przecięcia przynajmniej w około 88% wartości optymalnej. Obliczenia kwantowe obiecują nowe sposoby podejścia do takich zadań, jednak obecne urządzenia są zaszumione i ograniczone rozmiarem, co utrudnia uruchamianie dużych, głębokich obwodów.

Rozwiązywanie dużych grafów przy użyciu zaledwie kilku kubitów

Standardowe kwantowe podejścia, takie jak Quantum Approximate Optimization Algorithm (QAOA), wymagają jednego kubitu na węzeł sieci, więc graf o 1000 węzłach potrzebowałby 1000 kubitów — znacznie poza zasięgiem dzisiejszych maszyn. Nowa metoda, nazwana Qubit-Efficient MaxCut (QEMC), odwraca tę skalę: wykorzystuje jedynie około logarytmu liczby węzłów, co oznacza, że 11 kubitów może zakodować informacje o ponad 2000 węzłach. Zamiast przypisywać każdy kubit do pojedynczego węzła, QEMC wykorzystuje cały stan kwantowy jako kompaktową przestrzeń adresową, gdzie różne węzły odpowiadają różnym stanom bazowym tego małego rejestru. Ta oszczędność kubitów pozwala utrzymać obwody płytkie i łatwiejsze do uruchomienia na zaszumionym sprzęcie, jednocześnie reprezentując bardzo duże grafy.

Kolorowanie węzłów przez prawdopodobieństwo zamiast stałych stanów

Kluczową innowacją jest sposób, w jaki QEMC koduje „kolor” każdego węzła. Zamiast wymuszać, by każdy węzeł był dokładnie niebieski lub biały w pojedynczym stanie kwantowym, metoda pozwala, by kolor węzła był wywnioskowany z prawdopodobieństwa jego zaobserwowania w pomiarze. Węzeł, którego stan bazowy pojawia się z małym prawdopodobieństwem, traktowany jest jako jeden kolor; węzeł o wyższym prawdopodobieństwie — jako drugi. Wartość progowa rozdziela te dwa rejony. Oznacza to, że wiele różnych stanów kwantowych odpowiada w praktyce temu samemu podziałowi grafu. Funkcja kosztu, którą QEMC minimalizuje, jest skonstruowana tak, by węzły połączone krawędzią były zachęcane do tego, by znaleźć się po przeciwnych stronach tego progowego prawdopodobieństwa, co zwykle zwiększa liczbę krawędzi przecinających grupy kolorów i tym samym poprawia przecięcie.

Testowanie wydajności na rzeczywistych i symulowanych maszynach

Autorzy testują QEMC na dwóch polach: na rzeczywistych procesorach kwantowych oraz na klasycznych symulacjach obwodów kwantowych. Na małych regularnych grafach do 32 węzłów (używając tylko 2 do 5 kubitów) QEMC uruchomiony na sprzęcie nadprzewodzącym IBM znajduje przecięcia odpowiadające lub niemal odpowiadające najlepszym możliwym rozwiązaniom znalezionym przez przeszukiwanie pełne, wyraźnie przewyższając losowe zgadywanie i wcześniejsze badania kwantowe oparte na QAOA. W symulacjach bez szumów QEMC konsekwentnie osiąga ponad 97% optymalnego przecięcia dla tych małych grafów. Siła kodowania staje się jeszcze bardziej widoczna dla większych grafów: dla grafów 9-regularnych do 2048 węzłów klasyczne symulacje QEMC wciąż przewyższają GW zarówno pod względem przeciętnych, jak i najlepszych przecięć o kilka procent, a podobne przewagi widoczne są także dla losowych grafów o 128 węzłach przy różnych gęstościach.

Szybkość, ograniczenia i obietnica inspiracji kwantowej

Pomimo sukcesu QEMC nie dostarcza jeszcze formalnego przyspieszenia kwantowego. Ponieważ wykorzystuje tylko około log N kubitów, klasyczna symulacja jego obwodów także skaluje się mniej więcej liniowo z liczbą węzłów, a czas potrzebny na ewaluację funkcji kosztu rośnie wraz z liczbą krawędzi. Badania empiryczne sugerują, że łączny czas potrzebny do osiągnięcia wydajności na poziomie GW rośnie mniej więcej kwadratowo wraz z rozmiarem grafu, co wciąż jest w praktycznym zasięgu dla wielu problemów. Oznacza to, że QEMC w swojej obecnej formie działa raczej jako potężny heurystyczny algorytm inspirowany kwantowo niż jako dowód przewagi kwantowej.

Co ta praca oznacza na przyszłość

Dla osób niebędących specjalistami główne przesłanie jest takie, że małe, zaszumione urządzenia kwantowe nadal mogą być naukowo użyteczne, jeśli zaprojektujemy algorytmy dopasowane do ich mocnych stron. Poprzez kodowanie kolorów węzłów w elastycznych zakresach prawdopodobieństw zamiast w sztywnych wartościach bitowych, QEMC używa bardzo niewielu kubitów do rozwiązywania bardzo dużych problemów sieciowych i naturalnie toleruje szumy sprzętowe. Metoda ustanawia nowy punkt odniesienia dla testowania algorytmów optymalizacji kwantowej i daje także praktyczny algorytm klasyczny oparty na tych samych ideach. Szerzej rzecz biorąc, pokazuje, że przemyślenie sposobu kodowania informacji — zamiast jedynie budowania większych maszyn — może otworzyć obiecujące drogi do rozwiązywania trudnych problemów obliczeniowych.

Cytowanie: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

Słowa kluczowe: MaxCut, optymalizacja kwantowa, algorytmy wariacyjne, dzielenie grafu, obliczenia inspirowane kwantowo