Optymalizacja ruchu pojazdów za pomocą kwantowego wyżarzania

W informatyce wielokrotnie spotykamy się z sytuacjami, gdy tworzone algorytmy są w pewnym stopniu inspirowane przyrodą. Mamy na przykład algorytmy genetyczne, mrówkowe, rojowe czy symulowane wyżarzanie. Okazuje się, że obliczenia mogą być nie tylko inspirowane przez przyrodę, ale również przez przyrodę wykonywane!

Dużo mówi się ostatnio o komputerach kwantowych, w których obliczenia przeprowadzane są zgodnie z prawami mechaniki kwantowej i dzięki tym prawom. Najmniejszą i niepodzielną jednostką informacji kwantowej jest kubit, jest on odpowiednikiem bitu, będącego podstawową jednostką informacji w przypadku komputerów klasycznych. Stany kubitu mogą być formalnie reprezentowane jako wektory jednostkowe w dwuwymiarowej przestrzeni Hilberta nad ciałem liczb zespolonych. Brzmi skomplikowanie? Cóż, wystarczy wyobrazić sobie, że mamy 2-wymiarową przestrzeń punktów oraz 2 wektory, które oznaczymy jako $| 0⟩$ i $1⟩$ (będą one odpowiadały wartościom 0 i 1, tak jak przy standardowych bitach w przypadku komputerów klasycznych). Wektory te stanowić będą ortonormalną bazę naszej przestrzeni (czyli ich norma to 1 oraz ich iloczyn skalarny to 0). Dowolny punkt naszej przestrzeni można wtedy zapisać jako $| ϕ = a 0⟩ + b 1⟩ ,$ gdzie $a$ i $b$ są liczbami zespolonymi. Stany kubitów są wektorami o normie 1 w tej przestrzeni, czyli zawsze będzie $| a 2 + b 2 = 1$ oraz - o ile oba współczynniki są niezerowe - mówimy, że stan kubitu jest w superpozycji stanów $| 0⟩$ i $1⟩.$ Obliczenia kwantowe mogą sprawić, że zmieniają się stany kubitów, czyli zmieniają się wartości $a$ i $b$ (zachowując założenie, że $a 2 + b 2 = 1$ ), a na koniec obliczeń, aby otrzymać wyniki, należy jeszcze wykonać pomiar, który zaburza superpozycję - z prawdopodobieństwem $| a 2$ odczytamy wartość 0, a z prawdopodobieństwem $2 b$ wartość 1 (wynik obliczeń może być więc niedeterministyczny). Oczywiście w komputerze kwantowym możemy mieć wiele kubitów (podobnie jak w komputerze klasycznym mamy wiele bitów), mając $n$ kubitów, możemy przygotować stan będący superpozycją stanów, które reprezentują wszystkie $n 2$ liczby $n$ -bitowe. Dzięki temu możemy w pewnym sensie wykonywać obliczenia na wszystkich tych liczbach jednocześnie.

Czym dokładnie są jednak te kwantowe obliczenia? Obecnie istnieją 2 główne podejścia do obliczeń kwantowych: bazujące na bramkach kwantowych (analogicznie do bramek logicznych w przypadku komputerów klasycznych) oraz bazujące na algorytmie kwantowego wyżarzania w przypadku tzw. komputerów adiabatycznych. O modelach obliczeń kwantowych Czytelnicy Delty mogli przeczytać w artykule O modelach obliczeń komputerowych, a o kwantowym wyżarzaniu w artykule Kwantowe wyżarzanie "klasycznej" optymalizacji. Co ciekawe, te 2 modele obliczeń są równoważne, można za ich pomocą wykonywać takie same obliczenia (ale nie tak samo i niekoniecznie w takim samym czasie). W tym artykule przedstawiam interesujące zastosowanie kwantowego wyżarzania, przypomnę więc najpierw jego główne założenia.

Jak wspomniałem, kwantowe wyżarzanie może być realizowane na komputerach adiabatycznych (słowo "adiabatyczny" oznacza, że w trakcie obliczeń nie ma transferu ciepła do ani z otoczenia). Ważnym pojęciem związanym z obliczeniami adiabatycznymi jest Hamiltonian, który w tym przypadku można interpretować jako przyporządkowanie danemu stanowi układu fizycznego (np. układu kubitów) jego energii. Pomysł obliczeń na komputerach adiabatycznych bazuje na tym, że możemy stosunkowo łatwo przygotować układ początkowy kubitów, którego energia opisywana jest Hamiltonianem, dla którego minimum osiągane jest wtedy, gdy wszystkie kubity są w stanie superpozycji. Następnie poprzez modyfikację natężenia pola magnetycznego działającego na ten układ kubitów możemy doprowadzić go do stanu, w którym energia układu opisywana jest za pomocą innego Hamiltonianu, związanego z problemem obliczeniowym, który nas interesuje i którego minimum odpowiadałoby rozwiązaniu naszego problemu. Przy założeniu, że zmiana natężenia pola magnetycznego odbywa się dostatecznie wolno i ewolucja układu kubitów odbywa się adiabatycznie, układ kubitów pozostanie cały czas w stanie podstawowym, czyli w takim, w którym Hamiltonian (zmieniający się tym razem w czasie) cały czas będzie osiągał minimum. Dzięki temu na końcu kubity powinny również być w stanie odpowiadającym minimum ostatecznego Hamiltonianu, czyli powinny wskazać nam rozwiązanie naszego problemu. Proces ten można opisać wzorem:

(s)=(1−s)H0+sH1, H

gdzie $0 H$ jest Hamiltonianem początkowego układu kubitów, $1 H$ jest Hamiltonianem docelowego układu, a $s$ jest liczbą z przedziału $|[0,1]$ odpowiadającą natężeniu pola magnetycznego, zmieniającą się w sposób ciągły w czasie od 0 do 1. Zmieniając natężenie pola magnetycznego (a co za tym idzie - rozważany Hamiltonian) zachowujemy jednak cały czas warunek, że kubity są w stanie, który minimalizuje aktualny Hamiltonian układu. Ważną rolę w tym procesie odgrywa zjawisko kwantowego tunelowania, dzięki któremu kubity mogą zmieniać swój stan, aby układ "przeskakiwał" z minimum lokalnego do globalnego.

Taki model obliczeń jest obecnie nieco idealistyczny, ponieważ w praktyce trudno jest zapewnić adiabatyczność procesu obliczeń, a odpowiednio wolne tempo zmiany natężenia pola magnetycznego powodowałoby zbyt długi czas obliczeń. Oznacza to, że w praktyce układ może nie być w stanie pozostać cały czas w optimum globalnym. Proces, który realizuje odpowiednik obliczeń adiabatycznych w świecie rzeczywistym, nazywany jest kwantowym wyżarzaniem, a jego fizyczna realizacja jest obecnie dostępna w maszynach tworzonych przez kanadyjską firmę D-Wave. O szczegółach tego rozwiązania można przeczytać m.in. na stronach tej firmy, my zaś zajmiemy się w dalszej części artykułu obliczeniami, które można wykonywać za pomocą kwantowego wyżarzania.

Okazuje się, że projektowanie algorytmów rozwiązujących określone problemy w przypadku kwantowego wyżarzania wygląda zupełnie inaczej niż w przypadku tradycyjnych algorytmów projektowanych na maszyny Turinga (czy nawet na komputery bazujące na kwantowych bramkach). W tym przypadku istotą jest odpowiednie sformułowanie problemu obliczeniowego, a dokładnie: sformułowaniu go jako tzw. problem QUBO (Quadratic Unconstrained Binary Optimization), czyli problem minimalizacji wielomianu kwadratowego wielu zmiennych binarnych:

n i i jxix j, QUBO(x1, x2,x3,...,xn) = Q Q Q i 1 j 1

gdzie $i j∈R xi∈ {0,1},Q$ dla $i, j∈ {1,...,n}.$ Przy takim sformułowaniu, problem QUBO można następnie "przetłumaczyć" na model Isinga, który jest modelem ferromagnetyka, dla którego Hamiltonian odpowiada właśnie sformułowaniu QUBO. Dzięki temu dany problem ma już określoną interpretację fizyczną, można ją "zakodować" w komputerze kwantowym D-Wave. Dalej, zmieniając natężenie pola magnetycznego, sprawiamy, że obliczenia wykonuje przyroda, zgodnie z ideą kwantowego wyżarzania, ewoluując system zgodnie z równaniem Schrödingera.

Przyjrzyjmy się zatem, jak można za pomocą QUBO i kwantowego wyżarzania rozwiązywać problemy optymalizacyjne. Zaprezentuję dość prosty i pouczający przykład pochodzący z pracy Traffic Flow Optimization Using a Quantum Annealer autorstwa naukowców z D-Wave i Volkswagena. Dotyczy on zagadnienia optymalizacji kursowania taksówek w Pekinie. Naukowcy zbudowali najpierw graf reprezentujący rzeczywistą sieć drogową w Pekinie (oznaczmy jego zbiór krawędzi jako $S$ ) oraz pozyskali dane o 418 przejazdach taksówek z centrum Pekinu na lotnisko. Każda trasa przebiegała przez pewne krawędzie w grafie, trasy pochodziły z tygodnia kursowania taksówek (zbiór T-Drive), ale na potrzeby eksperymentu założono, że przejazdy odbywają się mniej więcej w tym samym czasie. Dla każdego przejazdu dodano 2 alternatywne trasy (z tego samego miejsca do tego samego celu). Poczyniono również założenie, że czas przejazdu przez dany odcinek drogi (krawędź grafu) jest proporcjonalny do kwadratu liczby pojazdów, które przejeżdżają przez daną krawędź (jest to pewne uproszczenie, ale rozsądne z punktu widzenia tych badań). Celem badań było znalezienie optymalnego (a przynajmniej lepszego niż początkowy) układu tras dla tych samych pojazdów, a więc dla każdego przejazdu trzeba było "wybrać" taką trasę (spośród 3 możliwych: początkowej oraz 2 dodanych), aby minimalizować łączny czas przejazdu wszystkich pojazdów. Jak można to zrobić za pomocą kwantowego wyżarzania?

Przyjmijmy, że mamy $n = 418$ pojazdów, każdy z nich ma do wyboru 3 różne trasy, a $|q i j$ będą zmiennymi binarnymi określającymi, czy pojazd $|i$ wybrał trasę $| j$ (dla $i ∈{1,2,...,n}, j∈ {1,2,3}$ ), czyli $qi j = 1,$ jeśli pojazd $|i$ wybrał trasę $| j,$ w przeciwnym razie $|qi j = 0.$ Dla każdego pojazdu $i$ musi być spełniony warunek:

2 ⎛ 3 ⎞ ⎝ Q qi j− 1⎠ = 0, j 1

(1)

a ponieważ $q2 = qi j i j$ (dla możliwych wartości 0 i 1), więc daje to warunek: $|− q −q − q + 2q q + 2q q +q q + 1 = 0. i1 i2 i3 i1 i2 i1 i3 i2 i3$

Przyjmijmy również, że $cost(s)$ jest łącznym kosztem (czasem) przejazdu wszystkich pojazdów przez krawędź $s,$ a $B s$ jest zbiorem tych par $|(i, j),$ które odpowiadają trasom zawierającym krawędź $s.$ Zgodnie z założeniem, że czas przejazdu przez krawędź jest proporcjonalny do kwadratu liczby pojazdów, które przejeżdżają przez daną krawędź, możemy przyjąć, że $|cost(s) = ( q )2. iP, j >Bs i j$

W takim razie możemy zdefiniować optymalizowaną funkcję celu jako:

2 n ⎛ 3 ⎞ Obj = Q cost(s)+ λQ ⎝ Q qi j− 1⎠ . s> S i 1 j 1

Pierwszy składnik odpowiada sumie kosztów przejazdu przez wszystkie krawędzie. Dodajemy drugi składnik z odpowiednio dużą wartością parametru $|λ,$ aby zapewnić, że w optymalnym rozwiązaniu ten składnik będzie równy 0, czyli zapewnione będzie spełnienie warunku (1) dla wszystkich pojazdów. Można już zauważyć, że optymalizowana funkcja kosztu $Obj$ jest sformułowaniem $QUBO$ dla $3n = 1254$ zmiennych $|q . i j$ Autorzy pracy "zakodowali" to sformułowanie QUBO i przeprowadzili eksperymenty (kwantowe wyżarzanie) na maszynie D-Wave 2X QPU. Obliczenia trwały 22 sekundy, po tym czasie udało im się znaleźć rozkład tras istotnie lepszy niż początkowy, co obrazuje poniższa grafika z tej pracy.

Kwantowe wyżarzanie nie jest doskonałą realizacją obliczeń adiabatycznych, nie możemy być więc pewni, że za każdym razem znajdziemy najlepsze rozwiązanie. Poza tym, o ile wiele praktycznych problemów da się zdefiniować jako problemy optymalizacji kombinatorycznej, to jednak nie zawsze łatwo jest znaleźć odpowiednią reprezentację QUBO. Jest to jednak ciekawa alternatywa dla obliczeń klasycznych i przypuszcza się, że to właśnie kwantowe wyżarzanie może przyczynić się do pierwszych praktycznych zastosowań obliczeń kwantowych.