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


11

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 jat | b λ J Σ j = N j = 1 β j | u jN×NAbxAx=bAbb|b=i=1Nbi|ieiAt|bidla 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 .tA|bAλju j | b = Σ j = N j = 1 β j | u jj=1j=Nβj|uj|λjujA|b=j=1j=Nβj|uj

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 Uφei2πφ|uU

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 φ tt|0tφ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|u|uUU

12t/2(|0+exp(2πi2t1φ)|1)(|0+exp(2πi2t2φ)|1)...(|0+exp(2πi20φ)|1)=12t/2k=02t1exp(2πiφk)|k

wprowadź opis zdjęcia tutaj

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.φΘ(t2)φ

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 . . . φ tφφ=0.φ1...φt

12t/2(|0+exp(2πi0.φt|1)(|0+exp(2πi0.φt1φt|1)...(|0+exp(2πi0.φ1...φt|1)

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!|φ1...φtφ

wprowadź opis zdjęcia tutaj

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φU|u

12t/2j=02t1exp(2πiφj)|j|u|φ~|u

Kontynuujmy stąd. Znalazłem ładny schemat dla algorytmu HHL09 tutaj [ ] :

wprowadź opis zdjęcia tutaj

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!). AAeiAtA

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=eiAt|ujUN×NNAλjeiAteiλjtUe2πiφeiλjt, 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φ=λjt2π|bUj=1j=Nβj|uj|ujU|u(|0)t|u|φ~|uj|λjt2π~λjto 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 .|ujAj=1j=Nβj|ujj=1j=Nβj|uj|λjt2π~

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 .j=1j=Nβj|uj|λ~jj=1j=Nβj|uj|λjt2π~

Czego tu brakuje? Gdzie zniknął czynnik w ich algorytmie?t2π

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)


1
@Nelimee That pochodzi ze wzoru . Oznacza liczbę kubitów w „pierwszym rejestrze” potrzebnych do reprezentacji każdego lub z dokładnością do bitów i dokładnością . Przy okazji, proszę zauważyć, że część pytania została teraz przeniesiona tutaj . 6t=3+log2(2+12(0.1))=3+3=6|λj|λjt2π390%
Sanchayan Dutta

Odpowiedzi:


5

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. .tt=t0=2π

  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ść ".λ~λt2πλ~λt2π

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 .t2π

  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).tt02π

  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π

  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.t0=2π


2

Czego tu brakuje? Gdzie zniknął czynnik w ich algorytmie?t2π

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 λUeiλtλt/(2π)Aλ

| przybliżony wektor własny dla którego wartość własna to oraz dla której wartość własna if ,e - i λ t λ UeiλtAλ

ale może zamiast pisać to za każdym razem, możemy po prostu napisać dla zwięzłości!|λ~

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.