Algorytm kwantowy dla liniowych układów równań (HHL09): Krok 2 - Co to jest ?


9

Jest to kontynuacja algorytmu kwantowego dla liniowych układów równań (HHL09): Krok 1 - Zamieszanie dotyczące zastosowania algorytmu szacowania faz i algorytmu kwantowego dla liniowych układów równań (HHL09): Krok 1 - Liczba potrzebnych kubitów .


W artykule: Algorytm kwantowy dla liniowych układów równań (Harrow, Hassidim i Lloyd, 2009) , co napisano do części

Następnym krokiem jest dekompozycja |b w podstawie wektora własnego przy użyciu estymacji fazowej [5–7]. Oznacz przez | u_j \ rangle|uj wektorów własnych A (lub równoważnie, eiAt ), a przez λj odpowiednie wartości własne.

na stronie 2 ma dla mnie pewien sens (zamieszanie, które pojawiło się w poprzednich postach, do których odsyłam powyżej). Jednak kolejna część, tj. Rotacja R(λ1) wydaje się nieco tajemnicza.

Niech

|Ψ0:=2Tτ=0T1sinπ(τ+12)T|τ

dla jakiegoś dużego . Współczynniki są wybierane (zgodnie z [5-7]), aby zminimalizować pewną funkcję straty kwadratowej, która pojawia się w naszej analizie błędów (szczegóły [patrz 13]).T|Ψ0

Następnie stosujemy warunkową ewolucję hamiltonowską na , gdzie .τ=0T1|ττ|CeiAτt0/T|Ψ0C|bt0=O(κ/ϵ)

Pytania:

1. Czym dokładnie jest ? Co oznaczają i ? Nie mam pojęcia, skąd to gigantyczne wyrażenie nagle pochodzi i jakie jest jego zastosowanie.|Ψ0Tτ

2Tτ=0T1sinπ(τ+12)T|τ

2. Po etapie szacowania fazy stan naszego systemu jest najwyraźniej :

(j=1j=Nβj|uj|λ~j)|0ancilla

Z pewnością nie można tego zapisać jako tj

(j=1j=Nβj|uj)(j=1j=N|λ~j)|0ancilla

|b(j=1j=N|λ~j)|0ancilla

Jest więc jasne, że nie jest dostępny osobno w drugim rejestrze. Więc nie mam pojęcia, jak przygotowują stan taki jak w pierwszej kolejności! Co również oznacza to w indeksie górnym ?|b|Ψ0C|bC|Ψ0C

3. Skąd nagle pojawia się to wyrażenie ? Po co to symulować? Co to jest w ?τ=0T1|ττ|CeiAτt0/TκO(κ/ϵ)

Odpowiedzi:


5

1. Definicje

Nazwy i symbole użyte w tej odpowiedzi są zgodne z tymi zdefiniowanymi w algorytmach liniowych systemów kwantowych: primer (Dervovic, Herbster, Mountney, Severini, Usher i Wossnig, 2018) . Wycofanie odbywa się poniżej.

1.1 Zarejestruj nazwy

Nazwy rejestrów są zdefiniowane na rysunku 5. algorytmów liniowych systemów kwantowych: starter (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) (odtworzony poniżej):

  • S (1 kubit) to rejestr pomocniczy używany do sprawdzania, czy dane wyjściowe są prawidłowe, czy nie.
  • C ( kubitów) jest rejestrem zegarowym, tj. Rejestrem stosowanym do oszacowania wartości własnych hamiltonianu z estymacją fazy kwantowej (QPE).n
  • I ( kubitów) jest rejestrem przechowującym prawą stronę równania . Przechowuje , wynik równania, gdy jest mierzone jako na końcu algorytmu.mAx=bxS|1

Algorytm HHL

2. Informacje o :|Ψ0

  1. Czym dokładnie jest ?|Ψ0

    |Ψ0 jest jednym z możliwych stan początkowy rejestru zegara .C

  2. Co oznaczają i ?Tτ

    T oznacza dużą dodatnią liczbę całkowitą. Ten powinien być tak duży, jak to możliwe, ponieważ wyrażenie asymptotycznie minimalizuje podany błąd dla wzrostu do nieskończoności. W wyrazem , będzie , liczba możliwych stanów dla zegara kwantowa .T|Ψ0T|Ψ0T2nC

    τ to tylko indeks sumowania

  3. Dlaczego tak gigantyczne wyrażenie dla ?|Ψ0

    Zobacz post DaftWullie, aby uzyskać szczegółowe wyjaśnienie.

    Po cytowaniu w algorytmie kwantowym liniowych układów równań (Harrow, Hassidim i Lloyd, 2009 v3) otrzymujemy:

    1. Poprzednia wersja tego samego artykułu Algorytm kwantowy dla liniowych układów równań (Harrow, Hassidim i Lloyd, 2009 v2) . Autorzy poprawili artykuł 2 razy (istnieją 3 wersje oryginalnego artykułu HHL), a wersja nr 3 nie zawiera wszystkich informacji zawartych w poprzednich wersjach. W V2 (sekcja A.3. Od strony 17) autorzy przedstawiają szczegółową analizę błędu w tym specjalnym stanie początkowym.
    2. Optymalne zegary kwantowe (Buzek, Derka, Massar, 1998), gdzie wyrażenie jest podane jako w równaniu 10. Nie mam wiedzy, aby rozumiem w pełni tę część, ale wydaje się, że to wyrażenie jest w pewnym sensie „optymalne”.|Ψ0|Ψopt

3. Przygotowanie :|Ψ0

Jak powiedziano w poprzedniej części, jest stanem początkowym. Nie przygotowują po procedurze szacowania fazy. Kolejność zdań nie jest w rzeczywistości optymalna. Stosowana w artykule procedura szacowania faz różni się nieco od „klasycznego” algorytmu szacowania faz reprezentowanego w obwodzie kwantowym połączonym w części 1 i dlatego wyjaśniają go szczegółowo.|Ψ0|Ψ0

Ich algorytm szacowania faz to:

  1. Przygotowanie stan w rejestrze .|Ψ0C
  2. Zastosuj warunkową ewolucję hamiltonowską do rejestrów i (które są w stanie ).CI|Ψ0|b
  3. Zastosuj kwantową transformatę Fouriera do stanu wynikowego.

Wreszcie w oznacza, że ​​stan są przechowywane w rejestrze . Jest to krótki i wygodny zapis umożliwiający śledzenie używanych rejestrów.C|Ψ0C|Ψ0C

4. Symulacja Hamiltona:

Przede wszystkim jest liczbą warunek ( strona na Wikipedii „numer stan” ) macierzy .κA

τ=0T1|ττ|CeiAτt0/T to matematyczne przedstawienie bramki kwantowej.

Pierwsza część sumy jest częścią kontrolną. Oznacza to, że operacja będzie kontrolowana przez stan pierwszego rejestru kwantowego (rejestr jak mówi nam wykładnik).|ττ|CC

Druga część to bramka „symulacji Hamiltona”, tj. Bramka kwantowa, która zastosuje macierz jednostkową podaną przez do drugiego rejestru (rejestr który jest w stanie początkowym ).eiAτt0/TI|b

Cała suma jest matematyczną reprezentacją operacji kontrolowanego U w obwodzie kwantowym „1. Definicje”, przy .U=eiAτt0/T


3

W odpowiedzi na twoje pierwsze pytanie, jakiś czas temu napisałem sobie notatki na temat mojego zrozumienia, jak to działa. Notacja jest prawdopodobnie nieco inna (starałem się ją bardziej ujednolicić, ale łatwo przeoczyć bity), ale próbuje wyjaśnić ten wybór stanu . Wydaje się, że istnieją pewne czynniki unoszące się w różnych miejscach.|Ψ012

Kiedy po raz pierwszy badamy oszacowanie fazy, zwykle myślimy o tym w odniesieniu do zastosowania w określonym algorytmie, takim jak algorytm Shora. Ma to konkretny cel: uzyskanie najlepszego przybliżenia bitu do wartości własnej. Albo to robisz, albo nie, a opis szacowania faz jest specjalnie dostosowany, aby zapewnić jak największe prawdopodobieństwo sukcesu.t

W HHL staramy się stworzyć stan gdzie , wykorzystując estymację faz. Dokładność przybliżenia tego będzie znacznie bardziej zależała od dokładnego oszacowania wartości własnych, które są bliskie 0, a nie tych, które są dalekie od 0. Oczywistym krokiem jest zatem próba modyfikacji protokołu szacowania faz, aby raczej zamiast używać „przedziałów” o stałej szerokości do przybliżania faz ( i to liczba kubitów w rejestrze szacowania faz), możemy raczej określić zestaw dla

|ϕ=jβjλj|λj,
|b=jβj|λj2π/TeiAtT=2ttϕyy{0,1}t aby działał jako środek każdego pojemnika, dzięki czemu możemy znacznie zwiększyć dokładność blisko fazy 0. Mówiąc bardziej ogólnie, możesz określić funkcję kompromisu dla tego, jak tolerancyjnie możesz być na błędy jako funkcję fazy . Dokładny charakter tej funkcji można następnie dostosować do konkretnej aplikacji, a także konkretną wartość zasługi, której użyjesz do określenia sukcesu. W przypadku algorytmu Shora naszą zasługą był po prostu ten protokół binningu - odnieśliśmy sukces, jeśli odpowiedź była w poprawnym bin, a poza nią nie powiodło się. Nie będzie tak w przypadku HHL, którego sukces jest bardziej racjonalnie uchwycony przez ciągłe środki, takie jak wierność. Zatem w ogólnym przypadku wyznaczymy funkcję kosztuϕC(ϕ,ϕ)który określa karę za odpowiedzi jeśli prawdziwą fazą jest .ϕϕ

Przypomnij sobie, że standardowy protokół szacowania fazy działał, tworząc stan wejściowy, który był równomierną superpozycją wszystkich stanów bazowych dla . Ten stan został wykorzystany do kontrolowania sekwencyjnego zastosowania wielu bramek z kontrolowanym , po których następuje odwrotna transformata Fouriera. Wyobraźmy sobie, że możemy zastąpić stan wejściowy innym stanem a następnie reszta protokołu mogłaby działa jak poprzednio. Na razie zignorujemy pytanie, jak trudno jest stworzyć nowy stan , ponieważ staramy się tylko przekazać podstawową koncepcję. Począwszy od tego stanu, zastosowanie kontrolowanego|xx{0,1}tU

|Ψ0=x{0,1}tαx|x,
|Ψ0Ugates (celując w wektor własny wartości własnej ), tworzy stan Zastosowanie odwrotnej transformacji Fouriera daje Prawdopodobieństwo uzyskania odpowiedzi (tj. ) wynosi więc oczekiwana wartość funkcji kosztu, przy założeniu losowego rozkładu , wynosi Uϕ
x{0,1}tαxeiϕx|x.
1Tx,y{0,1}teix(ϕ2πyM)αx|y.
yϕ=2πy/T
1T|x{0,1}teix(ϕ2πyT)αx|2
ϕ
C¯=12πT02πdϕy{0,1}t|x{0,1}teix(ϕ2πyT)αx|2C(ϕ,2πy/T),
a naszym zadaniem jest wybranie amplitud które minimalizują to dla każdej konkretnej realizacji . Jeśli przyjmiemy upraszczające założenie, że jest tylko funkcją , wówczas możemy dokonać zmiany zmiennej w integracji, aby dać jak zauważyliśmy, najbardziej użytecznym miernikiem jest prawdopodobnie miara wierności. Rozważmy, że mamy stanαxC(ϕ,ϕ)C(ϕ,ϕ)ϕϕ
C¯=12π02πdϕ|x{0,1}teixϕαx|2C(ϕ),
|+i chcemy wdrożyć jednolity , ale zamiast tego wdrażamy . Wierność mierzy, jak dobrze osiąga to pożądane zadanie, więc bierzemy ponieważ w idealnym przypadku , więc błąd, który chcemy zminimalizować, można przyjąć jako . Z pewnością będzie to właściwa funkcja do oceny dowolnegoUϕ=|00|+eiϕ|11|Uϕ=|00|+eiϕ|11|
F=|+|UϕU|+|2=cos2(ϕϕ2),
C(ϕϕ)=sin2(ϕϕ2),
F=11FUt, ale w przypadku bardziej ogólnego zadania polegającego na modyfikacji amplitud, nie tylko faz, skutki niedokładności rozprzestrzeniają się w protokole w mniej trywialny sposób, dlatego trudno jest udowodnić optymalność, chociaż funkcja zapewni już pewną poprawę w stosunku do jednolitego superpozycji państw. Kontynuując ten formularz, mamy Teraz można wykonać całkę nad , dlatego chcemy zminimalizować funkcję Można to zwięźle wyrazić jako C(ϕϕ)
C¯=12π02πdϕ|x{0,1}teixϕαx|2sin2(12ϕ),
ϕ
12x,y=0T1αxαy(δx,y12δx,y112δx,y+1).
minΨ0|H|Ψ0
gdzie Optymalnym wyborem jest minimalny wektor własny macierzy , a to minimalna wartość własna Co najważniejsze, w przypadku dużych , łuski zamiast , który mamy z jednolitego sprzęgła wybór
H=12x,y=0T1(δx,y12δx,y112δx,y+1)|xy|.
|Ψ0H
αx=2T+1sin((x+1)πT+1),
C¯
C¯=1212cos(πT+1).
TC¯1/T21/Tαx=1/T. Daje to znaczącą korzyść z analizy błędów.

Jeśli chcesz uzyskać ten sam jak podano w artykule HHL, uważam, że musisz dodać warunki do Hamiltonian. Nie mam jednak takiego uzasadnienia, ale to chyba moja wina.|Ψ014(|0T1|+|T10|)

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.