Estymacja fazy kwantowej i algorytm HHL - wymagana znajomość wartości własnych?


10

Algorytm oszacowania fazy kwantowej (QPE) oblicza się aproksymację wartości własnej, związanej z danym wektor własny bramy kwantowej U .

Formalnie pozwól |ψ być wektorem własnym z U , QPE pozwala nam znaleźć |θ~ najlepsza m nieco zbliżanie 2mθ taki, że θ[0,1) i

U|ψ=e2πiθ|ψ.

Algorytm HHL ( pierwotny papier ) pobiera jako dane wejściowe macierzy A , które spełniają

eiAt is unitary 
i stanu kwantowa |b i oblicza |x który koduje roztwór liniowo Ax=b .

Uwaga : Każda macierz hermitowska statisfy stan na A .

Aby to zrobić, algorytm HHL wykorzystuje QPE na bramce kwantowej reprezentowanej przez U=eiAt . Dzięki liniowych wyników algebry, wiemy, że jeśli {λj}j są wartości własne A potem {eiλjt}j są wartościami własnymi U . Ten wynik znajduje się również w algorytmach układów liniowych kwantowych: starter (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) (strona 29, między równaniami 68 i 69).

Dzięki QPE, pierwszym krokiem algorytmu HLL spróbuje oszacować w taki sposób, e i 2 gatunku θ = e I λ j T . To prowadzi nas do równania 2 π θ = λ j t + 2 k π ,θ[0,1)ei2πθ=eiλjt tj. θ = λ j t

2πθ=λjt+2kπ,kZ, θ[0,1)
Analizując trochę implikacje warunków k Z i θ [ 0 , 1 ) , doszedłem do wniosku, że jeśli λ j t
θ=λjt2π+k,kZ, θ[0,1)
kZθ[0,1)(tj.K0), algorytm szacowania faz nie przewidział właściwej wartości własnej.λjt2π[0,1)k0

Ale ponieważ może być dowolną macierzą pustelnika, możemy swobodnie wybierać jej wartości własne, a szczególnie możemy wybrać dowolnie duże wartości własne dla A, tak że QPE zawiedzie ( λ j tAA).λjt2π[0,1)

W projekcie obwodu kwantowego do rozwiązywania liniowych układów równań (Cao, Daskin, Frankel i Kais, 2012) rozwiązują ten problem, symulując , wiedząc, że wartości własneAwynoszą{1,2,4,8}. Są oneznormalizowanematrycy (i jego wartości własne), aby uniknąć przypadku, gdyλjteiAt16A{1,2,4,8}.λjt2π[0,1)

Z drugiej strony wydaje się, że do przeprowadzenia tej normalizacji można użyć parametru .t

Aλjt2π[0,1)


t=1k=2t=10<(λ/2π)+2<14π<λ<2πλ=3πλ/2π0

λθ[0,1)λ<0λλ2kπk=λ2πλ2π

Odpowiedzi:


6

Atλt2πANQ

maxiaii+ji|aij|NQ,
miniaiiji|aij|NQ.
aijA

W granicach wartości , , jeśli martwisz się, że dla dużej macierzy (powiedzmy kubity), podczas gdy suma wierszy może być łatwa do obliczenia (ponieważ nie ma wielu wpisów), maksimum we wszystkich wierszach może zająć dużo czasu czasu (ponieważ są wierszy), będzie wiele sposobów na uzyskanie dobrych przybliżeń (np. próbkowanie lub wykorzystanie wiedzy o strukturze problemu). W najgorszym przypadku możesz prawdopodobnie użyć wyszukiwania Grovera, aby go nieco przyspieszyć.NQn2n


1
Grover nie jest ulepszeniem: nawet jeśli możemy użyć algorytmu, nadal będziemy potrzebować zapytań , które niszczą wykładniczą poprawę HHL w stosunku do klasycznych metod i zastępują go kwadratowym przyspieszeniem. Pozostaje więc tylko nadzieja na pobranie próbek (wprowadzenie innego źródła błędów) lub modlitwa i nadzieja, że ​​problem pozwoli nam oszacować górne / dolne granice. Wydaje mi się, że to poważna wada algorytmu. O(N)
Nelimee

2
Jasne, miałem na myśli tylko to, że Grover przyspiesza pierwiastek kwadratowy w porównaniu z naiwnym sposobem uzyskania maksimum. Oczywiście ma to zły wpływ na ogólny czas działania.
DaftWullie
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.