Utility-scale QAOA

Obejrzyj film o utility-scale QAOA autorstwa Olivii Lanes lub otwórz wideo w osobnym oknie na YouTube.

Przegląd lekcji:

Do tej pory w tym kursie mamy nadzieję, że daliśmy ci solidne podstawy frameworku i narzędzi potrzebnych do rozwiązywania problemów w skali użytkowej na komputerze kwantowym. Teraz nareszcie zobaczymy te narzędzia w działaniu.

W tej lekcji zabrudzimy sobie ręce przykładem problemu Max-Cut w skali użytkowej — słynnego zagadnienia z teorii grafów dotyczącego najlepszego podziału grafu na dwie części. Zaczniemy od prostego, pięciowęzłowego grafu, by zbudować intuicję dotyczącą tego, jak komputer kwantowy może pomóc nam rozwiązać ten problem, a następnie zastosujemy to podejście do wersji problemu w skali użytkowej.

Ta lekcja będzie stanowić ogólny przegląd podejścia, jakie stosujemy do rozwiązywania tego problemu. Nie jest to omówienie kodu. Do lekcji dołączony jest jednak samouczek z prawdziwym kodem, który możesz uruchomić, aby rozwiązać problem Max-Cut na komputerze kwantowym.

Problem

Dla przypomnienia: nie wszystkie problemy obliczeniowe nadają się do przetwarzania kwantowego. „Łatwe problemy" nie zyskają żadnych korzyści dzięki tej technologii, ponieważ klasyczne komputery świetnie sobie z nimi radzą.

Trzy przypadki użycia, co do których jesteśmy najbardziej optymistyczni w kwestii eksploracji, to:

1. symulacja natury
2. przetwarzanie danych o złożonej strukturze
3. optymalizacja

Dzisiaj skupimy się na trzecim przypadku użycia — optymalizacji. W problemie optymalizacyjnym szukamy na ogół największej lub najmniejszej możliwej wartości danej funkcji. Trudność znalezienia tych ekstremów metodami klasycznymi może rosnąć wykładniczo wraz ze wzrostem rozmiaru problemu.

Interesującym dziś problemem optymalizacyjnym jest Max-Cut, który rozwiążemy przy użyciu algorytmu zwanego Quantum Approximate Optimization Algorithm (QAOA).

Czym jest Max-Cut?

Zaczynamy od grafu, który składa się ze zbioru wierzchołków (lub węzłów), z których niektóre są połączone krawędziami. W tym problemie musimy podzielić węzły grafu na dwa podzbiory, „przecinając" krawędzie je łączące. Chcemy znaleźć podział, który maksymalizuje liczbę tak przeciętych krawędzi — stąd nazwa „Max-Cut".

Na przykład rysunek powyżej przedstawia pięciowęzłowy graf z rozwiązaniem Max-Cut po prawej stronie. Przecina pięć krawędzi, co jest najlepszym wynikiem możliwym dla tego grafu.

Ponieważ pięciowęzłowy graf jest bardzo mały, ustalenie Max-Cut w głowie lub przez wypróbowanie kilku cięć na kartce papieru nie jest szczególnie trudne. Jednak, jak możesz się domyślić, problem staje się coraz trudniejszy wraz z rosnącą liczbą wierzchołków — między innymi dlatego, że liczba możliwych cięć do rozważenia rośnie wykładniczo wraz z liczbą węzłów. W pewnym momencie staje się to trudne nawet dla superkomputerów przy użyciu jakichkolwiek znanych algorytmów klasycznych.

Chcielibyśmy mieć sposób na rozwiązanie problemu Max-Cut dla tych większych, bardziej skomplikowanych grafów, ponieważ problem ten ma wiele praktycznych zastosowań, w tym wykrywanie oszustw w finansach, grupowanie grafów, projektowanie sieci i analizę mediów społecznościowych. Max-Cut często pojawia się jako podproblem w ramach określonego podejścia do większego zagadnienia. Jest więc znacznie bardziej powszechny, niż moglibyśmy naiwnie sądzić.

Rozwiązanie

Teraz omówimy podejście, które stosujemy do rozwiązania problemu Max-Cut na komputerze kwantowym. Zrobimy to na prostym, pięciowęzłowym grafie. Możesz śledzić postępy, korzystając z samouczka w notebooku Pythona. Po tym prostym przykładzie samouczek przeprowadzi cię przez przykład problemu w skali użytkowej.

Pierwszym krokiem jest utworzenie grafu przez zdefiniowanie liczby węzłów i krawędzi łączących dwa węzły. Możesz to zrobić, importując pakiet o nazwie rustworkx, co zostało zademonstrowane w samouczku. Wynikiem będzie graf wyglądający następująco:

Użyjemy frameworku wzorców Qiskit, aby znaleźć rozwiązania Max-Cut dla tego grafu na naszym komputerze kwantowym.

Odwzorowanie

Musimy odwzorować problem na nasz komputer kwantowy. Aby to zrobić, zauważmy najpierw, że maksymalizację liczby cięć w grafie można matematycznie zapisać jako:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

Gdzie $i$ i $j$ to węzły grafu, a $x_i$ i $x_j$ wynoszą 0 lub 1, w zależności od tego, po której stronie podziału znajduje się każdy węzeł (jedna grupa jest oznaczona „0", a druga „1"). Gdy $x_i$ i $x_j$ są po tej samej stronie podziału, wyrażenie w sumie jest równe zero. Gdy są po przeciwnych stronach, a więc jest między nimi cięcie, wyrażenie jest równe jeden. Zatem maksymalizacja liczby cięć zmaksymalizuje sumę.

Możemy też odwrócić to podejście i szukać minimum, mnożąc każdą z wartości przez minus jeden.

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

Teraz jesteśmy gotowi do odwzorowania. Myślenie o tym, jak przejść od grafu, który właśnie narysowaliśmy, do kwantowego Circuit, może być nieco onieśmielające. Ale zrobimy to krok po kroku.

Pamiętaj, że będziemy próbować rozwiązać Max-Cut przy użyciu QAOA. W metodologii QAOA ostatecznie chcemy mieć operator (czyli Hamiltonian), który będzie reprezentował funkcję kosztu naszego algorytmu hybrydowego, a także sparametryzowany Circuit (ansatz), którego używamy do reprezentowania możliwych rozwiązań problemu.

QUBO

Możemy próbkować z tych rozwiązań kandydujących, a następnie oceniać je za pomocą funkcji kosztu. W tym celu korzystamy z szeregu matematycznych przeformułowań, w tym notacji Quadratic Unconstrained Binary Optimization — w skrócie QUBO — która jest użytecznym sposobem kodowania kombinatorycznych problemów optymalizacyjnych. W QUBO chcemy znaleźć:

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

gdzie $Q$ jest macierzą $n\times n$ liczb rzeczywistych, a $n$ odpowiada liczbie węzłów w naszym grafie — tutaj pięć.

Aby zastosować QAOA, musimy sformułować nasz problem jako Hamiltonian — funkcję lub macierz reprezentującą całkowitą energię układu. Konkretnie chcemy stworzyć Hamiltonian funkcji kosztu o tej właściwości, że stan podstawowy odpowiada minimalnej wartości funkcji. Aby rozwiązać nasz problem optymalizacyjny, spróbujemy więc przygotować stan podstawowy $H$ na komputerze kwantowym. Następnie próbkowanie z tego stanu da z dużym prawdopodobieństwem rozwiązanie $\min 𝑓(𝑥)$.

Odwzorowanie na Hamiltonian funkcji kosztu

Jak się okazuje, mamy szczęście, ponieważ problem QUBO jest bardzo ściśle związany — i faktycznie obliczeniowo równoważny — z jednym z najsławniejszych i najszerzej stosowanych Hamiltonianów w fizyce: Hamiltonianem Ising.

Aby zapisać problem QUBO jako Hamiltonian Ising, musimy jedynie wykonać prostą zmianę zmiennych:

$$x_i = \frac{1-z_i}{2}.$$

Nie będziemy tu przechodzić przez wszystkie kroki — są one wyjaśnione w dołączonym notebooku. Ostatecznie minimalizacja wyrażenia QUBO jest tożsama z minimalizacją tego wyrażenia:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

Zapisując jeszcze raz nieco inaczej, otrzymujemy nasz Hamiltonian funkcji kosztu, gdzie minimum wyrażenia reprezentuje stan podstawowy, Z to operator Pauli Z, a $b$ jest rzeczywistym skalarnym współczynnikiem:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

Teraz, gdy mamy nasz Hamiltonian, musimy go przepisać w kategoriach dwulokowych operatorów Pauli ZZ, które można łatwo przekształcić w dwukubitowe Gate'y w naszym kwantowym Circuit. Otrzymamy sześć obiektów — czyli łańcuchów Pauli — z których każdy odpowiada jednej z sześciu krawędzi grafu. Każdy z pięciu elementów w łańcuchu reprezentuje operację na węźle — identyczność, jeśli węzeł nie jest połączony z daną krawędzią, oraz operator Pauli Z, jeśli jest. W Qiskit bitstringi reprezentujące qubity są indeksowane wstecz. Na przykład krawędź między węzłami 0 i 1 jest zakodowana jako IIIZZ, a krawędź między 2 i 4 jako ZIZII.

Konstruowanie kwantowego Circuit

Mając nasz Hamiltonian zapisany w kategoriach operatorów Pauli, jesteśmy gotowi do skonstruowania kwantowego Circuit, który pozwala nam próbkować dobre rozwiązania za pomocą komputera kwantowego:

Algorytm QAOA czerpie inspirację z twierdzenia adiabatycznego, które głosi, że jeśli zaczynamy w stanie podstawowym zależnego od czasu Hamiltonianu, a Hamiltonian ewoluuje wystarczająco wolno i ma wystarczająco dużo czasu, stan końcowy będzie stanem podstawowym końcowego Hamiltonianu. QAOA można traktować jako dyskretną, trotteryzowaną wersję tego kwantowego algorytmu adiabatycznego, gdzie każdy krok Trottera reprezentuje warstwę algorytmu QAOA. Zamiast ewoluować z jednego stanu do drugiego, w każdej warstwie będziemy przełączać się tam i z powrotem między naszym Hamiltonianem funkcji kosztu a tzw. Hamiltonianem „miksera", który omówimy w dalszej części lekcji.

Zaletą QAOA jest to, że jest szybszy niż kwantowy algorytm adiabatyczny, ale zwraca przybliżone rozwiązania zamiast optymalnych. W granicy, gdy liczba warstw dąży do nieskończoności, QAOA zbiega się do przypadku QAA, ale oczywiście jest to bardzo kosztowne obliczeniowo.

Aby stworzyć nasz kwantowy Circuit, zastosujemy naprzemienne operatory sparametryzowane przez $\gamma$ i $\beta$, które będą reprezentować dyskretyzację ewolucji czasowej.

Trzy główne części Circuit QAOA to:

1. początkowy stan próbny, zaznaczony na szaro, będący stanem podstawowym miksera, tworzony przez zastosowanie bramki Hadamarda do każdego kubitu
2. ewolucja funkcji kosztu, którą omówiliśmy wcześniej, zaznaczona ciemnofioletowym kolorem
3. ewolucja pod Hamiltonianem miksera, którego jeszcze nie omówiliśmy, zaznaczona jasnofioletowym kolorem.

Nasz startowy Hamiltonian nazywany jest Mikserem, ponieważ jego stan podstawowy jest superpozycją wszystkich możliwych bitstringów zainteresowania — a więc wymusza mieszaninę wszystkich możliwych rozwiązań na początku.

Hamiltonian miksera to prosta suma operacji Pauli-X na każdym węźle grafu. Qiskit pozwala na użycie innego, niestandardowego operatora miksera, jeśli chcesz, ale my użyjemy tutaj standardowego. Możesz więc ponownie zauważyć, że dzięki Qiskit duża część pracy jest za nas wykonana, co sprawia, że opracowanie Hamiltonianu miksera i stanu początkowego jest trywialne. Jedyną pracą, jaką musieliśmy wykonać, było znalezienie funkcji kosztu.

Każda iteracja tych operatorów jest nazywana warstwą. Warstwy te można traktować jako dyskretyzację ewolucji czasowej układu, jak opisano wcześniej. Naprzemienny wzorzec pochodzi z rozkładu Trottera i aproksymuje funkcje wykładnicze niekomutujących macierzy. Ogólnie rzecz biorąc, im więcej warstw lub kroków uwzględnimy, tym bliżsi będziemy ciągłej ewolucji czasowej, jak w QAA, więc w teorii wynik będzie dokładniejszy. Ale w tym przykładzie zaczniemy od próbkowania z jedną warstwą. Pamiętaj, że zarówno Hamiltonian funkcji kosztu, jak i mikser są sparametryzowane — musimy jeszcze wyznaczyć optymalne wartości $\gamma$ i $\beta.$

Optymalizacja

Choć obwód, który właśnie stworzyliśmy, wygląda dość prosto i jest przydatny do zbudowania intuicyjnego zrozumienia, pamiętaj — procesor kwantowy nie rozumie, czym jest Gate QAOA. Musimy zamienić go w serię jednoQubitowych i dwuQubitowych Gate'ów „natywnych", które można wykonać bezpośrednio na sprzęcie. Gate'y natywne to takie, które można wykonać bezpośrednio na kubitach. Mówi się, że takie Circuit są zapisane w Instruction Set Architecture (ISA) backendu.

Biblioteka Qiskit oferuje szereg pasów transpilacji (transpilation passes), które obsługują szeroką gamę transformacji Circuit. Chcemy się upewnić, że Circuit jest zoptymalizowany pod nasze potrzeby.

Przypomnij sobie z poprzedniej lekcji, że proces transpilacji obejmuje kilka kroków:

• Wstępne mapowanie kubitów w Circuit (czyli zmiennych decyzyjnych) na fizyczne kubity na urządzeniu.
• Rozwijanie instrukcji w Circuit kwantowym do natywnych instrukcji sprzętowych rozumianych przez backend.
• Routing kubitów w Circuit, które na siebie oddziałują, do sąsiadujących ze sobą fizycznych kubitów.

I jak zawsze, więcej szczegółów na ten temat znajdziesz w dokumentacji.

Zanim jednak przeprowadzimy transpilację, musimy wybrać backend, na którym uruchomimy nasz Circuit, ponieważ transpilator optymalizuje w różny sposób dla różnych procesorów. To kolejny powód, dla którego ważne jest używanie automatycznego transpilatora — nie chciałbyś przechodzić przez czasochłonny proces ręcznego optymalizowania swojego Circuit, żeby potem zdać sobie sprawę, że chcesz go uruchomić na zupełnie innym procesorze o innych właściwościach.

Przekaż wybrany backend do funkcji transpilatora i określ poziom optymalizacji. W samouczku wybierzesz poziom 3, który jest najwyższym i najbardziej dokładnym poziomem.

I gotowe — mamy Circuit po transpilacji, gotowy do wykonania na sprzęcie!

Wykonanie

Do tej pory przeprowadziliśmy transpilację Circuit, pozostawiając parametry gamma i beta bez zmian — ale nie możemy faktycznie uruchomić Circuit bez podania tych parametrów. W przepływie pracy QAOA optymalne parametry QAOA są znajdowane w iteracyjnej pętli optymalizacji, gdzie uruchamiamy serię ewaluacji Circuit, a następnie używamy klasycznego optymalizatora do znalezienia optymalnych parametrów 𝛽 i 𝛾. Musimy jednak od czegoś zacząć, więc przyjmujemy wstępne przybliżenie $\gamma=\pi/2$ i $\beta=\pi.$

Tryby wykonania

Jesteśmy już prawie gotowi do uruchomienia Circuit — obiecuję! Ale najpierw warto wiedzieć, że możesz wysłać swoje zadanie na kilka różnych sposobów, zwanych trybami wykonania.

• Tryb zadania (Job mode): Pojedyncze żądanie primitywu Estimator lub Sampler jest wysyłane bez menedżera kontekstu. Circuit i dane wejściowe są pakowane jako primitive unified blocs (PUBs) i przesyłane jako zadanie do wykonania na komputerze kwantowym.

• Tryb wsadowy (Batch mode): Menedżer wielu zadań służący do efektywnego uruchamiania eksperymentu składającego się z paczki niezależnych zadań. Tryb wsadowy pozwala jednocześnie przesyłać wiele zadań primitywów.

• Tryb sesji (Session mode): Dedykowane okno do uruchamiania obciążenia złożonego z wielu zadań. Pozwala użytkownikom eksperymentować z algorytmami wariacjonymi w bardziej przewidywalny sposób, a nawet uruchamiać wiele eksperymentów jednocześnie, wykorzystując równoległość w stosie. Używaj sesji do obciążeń iteracyjnych lub eksperymentów wymagających dedykowanego dostępu. Przykłady znajdziesz w sekcji Run jobs in a session.

Dla eksperymentu QAOA sesja byłaby dobrym wyborem — jeśli masz do niej dostęp — ponieważ musimy wielokrotnie próbkować nasz Circuit z różnymi wartościami parametrów, aby znaleźć optimum.

Wróćmy do problemu optymalizacji. Musimy znaleźć lepsze wartości gamma i beta niż nasze wstępne przybliżenia. Zrobimy to, podając naszą funkcję kosztu i te wstępne przybliżenia do optymalizatora scipy COBYLA.

Tutaj możesz zobaczyć wartość funkcji kosztu w kolejnych iteracjach. Na początku jest trochę niestabilna i waha się w górę i w dół, ale potem stabilizuje się na niskiej wartości. Użyjemy wartości znalezionych przez scipy, które odpowiadają najniższej ewaluacji funkcji kosztu.

Teraz, gdy udało nam się zmniejszyć naszą funkcję kosztu, znajdując lepsze wartości parametrów, uruchomimy nasz Circuit z nowymi wartościami gamma i beta. Podałem tutaj konkretne wartości, których używam, ale pamiętaj — gdy sam spróbujesz lub nawet po prostu ponownie uruchomisz ten sam notatnik samouczka, wartości te mogą się nieznacznie zmienić. Teraz uruchomimy nasz zoptymalizowany Circuit z tymi wartościami i znajdziemy kandydujące rozwiązanie naszego problemu Max-Cut.

Na etapie post-processingu przeanalizujemy dane i wyświetlimy wyniki, aby sprawdzić, czy nasz algorytm kwantowy znalazł prawidłowe rozwiązania.

Post-processing

Narysujmy teraz histogram danych, żeby przyjrzeć się końcowemu rozwiązaniu:

Ciągi bitów reprezentują sposób, w jaki poszczególne węzły zostały podzielone na dwie grupy (oznaczone „0" i „1") przez cięcie. Powinny istnieć cztery rozwiązania, które wszystkie dają maksymalną liczbę przeciętych krawędzi. Te cztery są pokazane na fioletowo. Od razu widać, że 4 rozwiązania są znacznie bardziej prawdopodobne niż wszystkie pozostałe. Najwyższy, a więc najbardziej prawdopodobny ciąg bitów to 0,1,0,1,1. (Pamiętaj — kolejność kubitów jest odwrócona w ciągach bitów na wykresie!)

Na podstawie tego wykresu możemy wziąć najbardziej prawdopodobny ciąg bitów i przedstawić go jako podzielony graf z cięciem przechodzącym przez pięć krawędzi:

Jest to więc rzeczywiście rozwiązanie Max-Cut. Ale nie jedyne! Ze względu na symetrię tego grafu istnieje wiele prawidłowych rozwiązań. Zamiast węzłów 0 i 3 wewnątrz cięcia moglibyśmy uwzględnić węzły 2 i 4. Widać, że wystarczyło obrócić cięcie, aby objęło te nowe punkty. Liczba przeciętych krawędzi nadal wynosi pięć. Okazuje się, że istnieją cztery rozwiązania Max-Cut, ponieważ każde z dwóch zauważonych rozwiązań ma również swój „przeciwny" odpowiednik, w którym fioletowe węzły są szare, a szare — fioletowe — cięcie pozostaje takie samo, ale każdy węzeł efektywnie przechodzi na przeciwną stronę podziału.

Przyjrzyjmy się jeszcze raz histogramowi i czterem najbardziej prawdopodobnym rozwiązaniom. Idealnie powinny one odpowiadać każdemu z czterech prawdziwych rozwiązań Max-Cut. Problem polega na tym, że algorytm nie zidentyfikował czwartego i ostatniego rozwiązania jako jednego z 4 najbardziej prawdopodobnych odpowiedzi. Było ono piątym pod względem prawdopodobieństwa. Czwarte rozwiązanie wskazane przez algorytm jest nieprawidłowe — gdybyś je narysował, zobaczyłbyś, że ma tylko cztery cięcia.

Ale pamiętaj: to jest algorytm przybliżony. Nie jest nieomylny i nie jest poprawny w 100% przypadków. Musisz stosować własną wiedzę i rozumienie, aby zdrowo-rozsądkowo weryfikować rozwiązania.

Ten błąd może wynikać z kilku przyczyn:

1. Może to być przybliżona natura samego algorytmu i mała liczba warstw, których użyłem.
2. Może to być błąd skończonego próbkowania — można go zmniejszyć, zwiększając liczbę shots w eksperymencie.
3. Może to być również błąd odczytu, ponieważ czwarte prawdziwe rozwiązanie różni się tylko jednym bitem.

Tego rodzaju analiza błędów jest niezbędna, aby stać się praktykiem informatyki kwantowej. Musisz rozumieć wydajność sprzętu i to, jak może ona przyczyniać się do określonych typów błędów oraz jak je korygować.

Nie zapominajmy jednak, że było 32 możliwych ciągów bitów, a cztery prawdziwe rozwiązania znalazły się w pięciu najlepszych kandydatach. I użyliśmy do tego tylko dwóch warstw. Ogólnie rzecz biorąc, gdybyśmy chcieli zwiększyć szanse na znalezienie najlepszego Max-Cut za każdym razem, moglibyśmy zwiększyć głębokość warstw. Wiążą się z tym pewne subtelności, ale to temat na późniejszą lekcję.

Na utility-scale