Algorytm kwantowy dla liniowych układów równań (HHL09): Krok 1 - Zamieszanie dotyczące zastosowania algorytmu szacowania faz

Od pewnego czasu próbuję obejść słynny (?) Papierowy algorytm kwantowy dla liniowych układów równań (Harrow, Hassidim i Lloyd, 2009) (bardziej znany jako papier algorytmiczny HHL09 ).

Na pierwszej stronie mówią :

Naszkicujemy tutaj podstawową ideę naszego algorytmu, a następnie omówimy go bardziej szczegółowo w następnej sekcji. Biorąc pod uwagę macierz Hermitian macierzy i wektor jednostkowy , załóżmy, że chcielibyśmy znaleźć spełniającą . (Omawiamy później kwestie wydajności, a także sposób, w jaki przyjęliśmy założenia dotyczące i ). Po pierwsze, algorytm reprezentuje jako stan kwantowy . Następnie używamy technik symulacji Hamiltona [3, 4], aby zastosować doA → b → x A → x = → b A → b → b | b ⟩ = Σ N i = 1, b : i | i A e i A t | b ja ⟩ t | b ⟩ λ J Σ j = N j = 1 β j | u $N\times N$$A$$\vec{b}$$\vec{x}$$A\vec{x} = \vec{b}$$A$$\vec{b}$$\vec{b}$$|b\rangle = \sum_{i=1}^{N}b_i|i\rangle$$e^{iAt}$$|b_i\rangle$dla superpozycji różnych czasów . Ta zdolność do potęgowania przekłada się, za pomocą dobrze znanej techniki estymacji fazowej [5–7], na zdolność do rozkładania w bazie własnej i znajdowania odpowiednich wartości własnych Nieoficjalnie, stan system po tym etapie jest blisko , gdzie jest bazą wektorów własnych i .$t$$A$$|b\rangle$$A$$\lambda_j$u j | b ⟩ = Σ j = N j = 1 β j | u j$\sum_{j=1}^{j=N} \beta_j |u_j\rangle|\lambda_j\rangle$$u_j$$A$$|b\rangle = \sum_{j=1}^{j=N} \beta_j|u_j\rangle$

Na razie w porządku. Jak opisano w Nielsen i Chuang w rozdziale „ Kwantowa transformata Fouriera i jej zastosowania ”, algorytm estymacji fazowej służy do oszacowania w która jest wartością własną odpowiadającą wektorowi własnemu jednostkowego operatora .e i 2 π φ | U ⟩ $\varphi$$e^{i2\pi \varphi}$$|u\rangle$$U$

Oto odpowiednia część z Nielsen & Chuang:

Algorytm szacowania fazy wykorzystuje dwa rejestry. Pierwszy rejestr zawiera kubitów początkowo w stanie . To, jak wybieramy zależy od dwóch rzeczy: liczby cyfr dokładności, które chcemy mieć w naszym oszacowaniu dla , i z jakim prawdopodobieństwem chcemy, aby procedura szacowania fazy zakończyła się powodzeniem. Zależność od tych wielkości wynika naturalnie z następującej analizy.| 0 ⟩ t φ $t$$|0\rangle$$t$$\varphi$$t$

Drugi rejestr zaczyna się w stanie i zawiera tyle kubitów, ile potrzeba do przechowywania . Oszacowanie fazowe odbywa się w dwóch etapach. Najpierw zastosujemy obwód pokazany na rysunku 5.2. Obwód zaczyna się od zastosowania transformacji Hadamarda do pierwszego rejestru, a następnie zastosowania operacji o kontrolowanym na drugim rejestrze, przy czym wzrasta do kolejnych potęg dwóch. Ostateczny stan pierwszego rejestru jest łatwo widoczny:| U ⟩ U $|u\rangle$$|u\rangle$$U$$U$

$$\frac{1}{2^{t/2}}\left(|0\rangle+\text{exp}(2\pi i 2^{t-1}\varphi)|1\rangle)(|0\rangle+\text{exp}(2\pi i 2^{t-2}\varphi)|1\rangle)...(|0\rangle+\text{exp}(2\pi i 2^{0}\varphi)|1\rangle\right)= \frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}\text{exp}(2\pi i \varphi k)|k\rangle$$

Drugim etapem estymacji fazowej jest zastosowanie odwrotnej kwantowej transformaty Fouriera do pierwszego rejestru. Uzyskuje się to poprzez odwrócenie obwodu kwantowej transformaty Fouriera w poprzednim rozdziale (Ćwiczenie 5.5) i można to zrobić w krokach . Trzecim i ostatnim etapem szacowania faz jest odczyt stanu pierwszego rejestru poprzez wykonanie pomiaru w oparciu o obliczenia. Pokażemy, że daje to całkiem niezłą ocenę . Ogólny schemat algorytmu pokazano na rysunku 5.3.$\Theta (t^2)$$\varphi$

Aby wyostrzyć naszą intuicję, dlaczego działa szacowanie faz, załóżmy, że może być wyrażone dokładnie w bitach, ponieważ . Następnie stan (5.20) wynikający z pierwszego etapu szacowania fazy może zostać przepisanyφ = 0. φ 1 . . . φ $\varphi$$\varphi = 0.\varphi_1 ... \varphi_t$

$$\frac{1}{2^{t/2}}(|0\rangle + \exp(2\pi i 0.\varphi_t|1\rangle)(|0\rangle + \exp(2\pi i 0.\varphi_{t-1}\varphi_t|1\rangle)...(|0\rangle + \exp(2\pi i 0.\varphi_1...\varphi_t|1\rangle)$$

Drugim etapem estymacji fazowej jest zastosowanie odwrotnej kwantowej transformaty Fouriera. Ale porównując poprzednie równanie z formą iloczynu dla transformaty Fouriera, równanie (5.4), widzimy, że stanem wyjściowym z drugiego etapu jest stan produktu . Dlatego pomiar w podstawie obliczeniowej daje nam dokładnie!$|\varphi_1 ...\varphi_t\rangle$$\varphi$

Podsumowując, algorytm szacowania faz pozwala oszacować fazę wartości własnej operatora jednostkowego , biorąc pod uwagę odpowiedni wektor własny . Istotną cechą leżącą u podstaw tej procedury jest zdolność odwrotnej transformacji Fouriera do przeprowadzenia transformacji$\varphi$$U$$|u\rangle$

$$\frac{1}{2^{t/2}}\sum_{j = 0}^{2^t-1}\exp(2\pi i \varphi j)|j\rangle |u\rangle \to |\tilde \varphi \rangle |u\rangle$$

Kontynuujmy stąd. Znalazłem ładny schemat dla algorytmu HHL09 tutaj ^{[ ]$\dagger$} :

Krok 1 (Szacowanie fazy):

W pierwszym etapie algorytmu HHL09 zastosowano tę samą koncepcję (standardowego algorytmu szacowania fazy kwantowej, jak opisano w Nielsen i Chuang). Musimy jednak pamiętać, że samo nie jest operatorem jednolitym. Jeśli jednak założymy, że jest pustelnikiem, wykładnicza jest jednolita (nie martw się, istnieje obejście na wypadek, gdyby nie był pustelnikiem!). $A$$A$$e^{iAt}$$A$

Tutaj możemy napisać . W grę wchodzi jeszcze jeden subtelny punkt. My nie wiemy wektorów własnych z uprzednich (ale wiem , że dla każdej jednostkowej macierzy rozmiaru istnieją wektorów własnych ortonormalne). Co więcej, musimy sobie przypomnieć, że jeśli wartości własne są wówczas wartości własne będą . Jeśli porównamy to z formą wartości własnych podanych w Nielsen i Chuang dla tj. Jeśli $U=e^{iAt}$$|u_j\rangle$$U$$N\times N$$N$$A$$\lambda_j$$e^{iAt}$$e^{i \lambda_j t}$$U$$e^{2\pi i \varphi} \equiv e^{ i \lambda_j t}$, znajdziemy . W takim przypadku zaczynamy od stanu (który można zapisać jako superpozycję wektorów własnych tj. ) szczególności wektor własny od , o ile drugi rejestr qubitach jest zaniepokojony. Gdybyśmy zaczęli w stanie , skończylibyśmy na tj. (biorąc pod uwagę, że$\varphi = \frac{\lambda_j t}{2\pi}$$|b\rangle$$U$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle$$|u_j\rangle$$U$$|u\rangle \otimes (|0\rangle)^{\otimes t}$$|u\rangle \otimes |\tilde\varphi\rangle$$|u_j\rangle \otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$$\lambda_j$to wartość własna związana z wektorem własnym z ). Zamiast tego, jeśli zaczniemy od superpozycji wektorów własnych , powinniśmy skończyć z .$|u_j\rangle$$A$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$

Pytanie:

Część 1 : W pracy HHL09 pisali o stanie systemu po tym etapie Etap Oszacowania to . Jednak z tego, co napisałem powyżej, wydaje mi się, że stanem systemu powinien być raczej .$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde\lambda_j\rangle$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$

Czego tu brakuje? Gdzie zniknął czynnik w ich algorytmie?$\frac{t}{2\pi}$

Edycja: Poproszono tutaj, aby część 2 była bardziej ukierunkowana na poszczególne pytania.

^{Mam również kilka nieporozumień dotyczących kroku 2 i kroku 3 algorytmu HHL09, ale postanowiłem opublikować je jako osobne wątki pytań, ponieważ ten staje się zbyt długi. Dodam linki do wątków pytań w tym poście, gdy zostaną utworzone.}

[ ]: eksperymenty z szyfrowaniem homomorficznym na chmurze IBM Quantum Computing Platform Huang i in. (2016)$\dagger$

To zależy od dokumentów, ale widziałem 2 podejścia:

1. W większości artykułów, które czytałem o algorytmie HHL i jego implementacji, czas ewolucji hamiltonianów przyjmuje się w taki sposób, że czynnik ten zanika, tj. .$t$$t = t_0 = 2\pi$

2. Przybliżona wartość własna jest często zapisywana . W niektórych artykułach notacja ta naprawdę oznacza „przybliżenie prawdziwej wartości własnej ”, aw innych artykułach wydaje się zawierać w tej definicji, tj. „ jest przybliżeniem wartość ".$\tilde \lambda$$\lambda$$\frac{t}{2\pi}$$\tilde \lambda$$\frac{\lambda t}{2\pi}$

Oto kilka linków:

1. Algorytmy kwantowych systemów liniowych: elementarz (Dervovic, Herbster, Mountney, Severini, Usher i Wossnig, 2018) : kompletny i bardzo dobry artykuł na temat algorytmu HHL i odkrytych ulepszeń. Artykuł pochodzi z 22 lutego 2018 r. Wartość którą jesteś zainteresowany, została po raz pierwszy omówiona na stronie 30, w legendzie na ryc. 5, i jest ustalona na .$t$$2\pi$

2. Układ obwodu kwantowego do rozwiązywania liniowych układów równań (Cao, Daskin, Frankel i Kais, 2013) (weź v2, a nie v3): szczegółowa implementacja algorytmu HHL dla stałej macierzy 4x4. Jeśli planujesz skorzystać z tego artykułu, pozwól, że cię ostrzeżę, że jest w nim trochę błędów. Mogę dostarczyć ci te, które znalazłem, jeśli jesteś zainteresowany. Wartość (która w tym dokumencie jest oznaczona jako ) jest ustalona na na drugiej stronie (na początku prawej kolumny).$t$$t_0$$2\pi$

3. Eksperymentalne obliczenia kwantowe do rozwiązywania układów równań liniowych (Cai, Weedbrook, Su, Chen, Gu, Zhu, Li, Liu, Lu & Pan, 2013) : implementacja algorytmu HHL dla macierzy 2x2 na układzie eksperymentalnym. Naprawiają w legendzie z ryc. 1.$t = 2\pi$

4. Eksperymentalna realizacja algorytmu kwantowego do rozwiązywania układów liniowych równań (Pan, Cao, Yao, Li, Ju, Peng, Kais i Du, 2013) : implementacja HHL dla macierzy 2x2. Implementacja jest podobna do tej podanej w drugim punkcie powyżej, z matrycą 4x4. Ustalony na stronie 3, podpunkcie n ° 2.$t_0 = 2\pi$

Czego tu brakuje? Gdzie zniknął czynnik w ich algorytmie?$\frac{t}{2\pi}$

Pamiętaj, że w notacji Diraca cokolwiek piszesz w kecie, jest dowolną etykietą odnoszącą się do czegoś bardziej abstrakcyjnego. Tak więc prawdą jest, że znajdujesz (przybliżony) wektor własny dla , który ma wartość własną a zatem wyodrębniasz to , ale to jest taki sam jak wektor własny z wartością własną , i to o tym mowa w notacji. Ale jeśli chcesz być naprawdę jasny, możesz to napisać jakoe - i λ t λ t / ( 2 π ) A $U$$e^{-i\lambda t}$$\lambda t/(2\pi)$$A$$\lambda$

| przybliżony wektor własny dla którego wartość własna to oraz dla której wartość własna if ,e - i λ t λ $U$$e^{-i\lambda t}$$A$$\lambda\rangle$

ale może zamiast pisać to za każdym razem, możemy po prostu napisać dla zwięzłości!$|\tilde\lambda\rangle$