Wariacyjne algorytmy kwantowe są odpowiedzią na problem klasycznych algorytmów wykorzystywanych w obliczeniach kwantowych - mianowicie algorytmy te (np wzmacnianie amplitudy) wymagają duzej liczby kubitów.
Zamiast realizować zadania za pomocą ustalonej sekwencji ustaolnych bramek algorytmy VQA definiowane są za pomocą ansatz\(W(\theta)\), który mozemy uznać za template (wzór) opisujący jakie bramki działają na który kubit. Dodatkowo kazdy ansatz moze byc wykonywany wiele razy (w jednym algorytmie) tworzą w ten sposób osobne warstwy (layers). Nazwa variational bierze się z tego, iz część bramek mozna realizować jako bramki obrotów zaleznych od parametrów.
VQE
Algorytmy wariacyjne zostały zaproponowane w celu znalezienia stanu podstawowego, stanu o najnizszej energii (najmniejsza wartość własna z odpowiadaijącym wekrtorem własnym).
Stan podstawowy \(\ket{\psi}\) to stan dla którego wartość oczekiwana operatora jest minimalna. \[ \bra{\psi} H \ket{\psi} \]
Algorytm VQE propnuje aby stan podstawowy zrealizować jako ansatz.
$ = W () $ Zamiast szukać stanu podstawowego $ $ znajdujemy prametr \(\theta\) dla którego wartość oczekiwana jest minimalna.
\[ C(\theta) = \bra{\psi \left(\theta\right)} H \ket{\psi \left(\theta\right)} \]
Obliczenie wartości oczekiwanej dowolnego hamiltonianu nie musi być trudne ale wymaga duzej ilości powtórzeń dla niewielkiej liczby kubitów aby uzyskać odpowiednią statystykę.
W wielu praktycznych przypadkach mozemy wyrazić nasz operator jako sumę jedno lub dwu kubitowych obserwabli. \[ H = \sum_{j=1}^{J} h_j H_j \]
W ogólności macierze Pauliego tworzą bazę dla macierzy 2x2 i dzieki temu zawsze mozemy zapisać ten wzór jako:
Poproszono Cię o zorganizowanie 5 róznych eventów na Sobotę i Niedzielę. Kazde przyjęcie zaplanowane jest na cały dzień -> Jeśli dwa eventy odbywają się w tym samym dniu to jedna osoba nie moze pojawić się na dwóch przyjęciach.
Posiadamy listę czterech osób i ich preferencje.
E1, E4
E2, E3
E4, E5
E3, E4
Problem ten mozna zareprezentować jako problem typu QUBO (ang. quadratic unconstrained binary optimization)
Zdefiniujmy graf, którego wierzchołki (nodes) to wydarzenia (eventy), natomiast krawędzie (edges) to osoby, które łączą dwa wydazenia jeśli dana osoba jest zainteresowana (dwoma) wydarzeniami. Rozwiązanie zadania mozna uzyskać poprzez pokolorowanie grafu na dwa kolory (biały - sobota , czarny - niedziela) - Znalezienie optymalnego podziału kolorów tak aby edge nie łączył tych samych kolorów (nie da się iść na dwa eventy w tym samym czasie).
Rozwiązanie:
wprowadźmy pięć zmiennych \(x_i = x_1, x_2, x_3, x_4, x_5\).
Wszystkim \(x_i\) trzeba przypisać dwie wartości 0 event w sobotę lub 1 event w niedzielę.
Do optymalizacji potrzebujemy funkcję \(f(x_1,...,x_5) = 1 + x_1 + x_4 - 2 x_1 x_4 + ...\)
Combinatorial optimization problems are problems involving a large number of yes/no decisions with each set of decisions yielding a corresponding objective function value, like a cost or profit value.
Because of the combinatorial explosion of the solution space with the number of variables, finding good solutions is extremely difficult.
The QUBO model unifies a rich variety of NP-hard combinatorial optimization problems:
Quadratic Assignment Problems
Capital Budgeting Problems
Task allocation Problems
Maximum–Cut Problems
QUBO objective function:
\[
F(q) = \sum_a v_a x_a + \sum_{a < b} \omega_{a b} x_a x_b
\] gdzie \(q_a \in \{0,1\}\), \(v_a\) oraz \(\omega_a\) to rzeczywiste współczynniki dla liniowej i kwadratowej części.
Bramki kwantowe realizowane są w modelu bramkowym przez operatory unitarne reprezentowane przez macierze.
\[
U U^{\dagger} = U^{\dagger} U = I
\]
Kazda macierz unitarna moze być przedstawiona jako:
\[
U(H,t) = e^{-i H t}
\] gdzie \(H\) to macierz Hermitowska (\(H=H^{\dagger}\))
W ogólności, implementacja obwodu kwantowego, który dokładnie realizuje macierz unitarną dla zadanego Hamiltonianiu jest bardzo trudnym zadaniem. Hamiltonian taki zazwyczaj składa się z sumy wielu niekomutujących części.
\[
H = H_1 + H_2 + \dots + H_n
\]
Rozwazmy pierwszy prosty przypadek gdzie nasza macierz \(H\) realizowana jest przez operator Pauliego \(Z\).
Chcielibyśmy znaleźć tzn poziom podstawowy operatora \(H\), czyli jego wektor własny dla którego ma on najmniejszą wartość własną. Takie podejście powinno kojarzyć się nam z wymogiem minimalizacji funkcji straty. \[ H\ket{E_0} = E_0\ket{E_0} \]
W przypadku gdy \(H = Z\) mamy dwa stany \(\ket{0}\) i \(\ket{1}\)
\[ Z\ket{0} = 1 \ket{0} \]
\[ Z\ket{1} = -1 \ket{1} \]
Czyli stanem o najmniejszej wartości własnej jest stan \(\ket{1}\).
Załózmy, ze nie znamy tej informacji!!!
Algorytm QAOA
Przygotuj obwód i zastosuj bramkę Hadamarda - stan superpozycji (\(\ket{+} = H\ket{0}\))