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

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 $\left|\psi\right>$ być wektorem własnym z $U$ , QPE pozwala nam znaleźć $\vert\tilde\theta\rangle$ najlepsza $m$ nieco zbliżanie $\lfloor2^m\theta\rfloor$ taki, że $\theta \in [0,1)$ i

U | ψ ⟩ = e^{2 π i θ} | ψ ⟩ .

$U\vert\psi\rangle = e^{2\pi i \theta} \vert\psi\rangle.$

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

e^{i A t} is unitary

$e^{iAt} \text{ is unitary }$ i stanu kwantowa

| b ⟩

$\vert b \rangle$ i oblicza

| x ⟩

$\vert x \rangle$ który koduje roztwór liniowo

A x = b

$Ax = b$ .

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

Aby to zrobić, algorytm HHL wykorzystuje QPE na bramce kwantowej reprezentowanej przez $U = e^{iAt}$ . Dzięki liniowych wyników algebry, wiemy, że jeśli $\left\{\lambda_j\right\}_j$ są wartości własne $A$ potem $\left\{e^{i\lambda_j t}\right\}_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, . To prowadzi nas do równania $\theta \in [0,1)$ $e^{i2\pi \theta} = e^{i\lambda_j t}$ tj.

2 π θ = λ_{j} t + 2 k π, k \in Z, θ \in [0, 1)

$2\pi \theta = \lambda_j t + 2k\pi, \qquad k\in \mathbb{Z}, \ \theta \in [0,1)$

Analizując trochę implikacje warunków

, doszedłem do wniosku, że jeśli

θ = \frac{λ_{j} t}{2 π} + k, k \in Z, θ \in [0, 1)

$\theta = \frac{\lambda_j t}{2\pi} + k, \qquad k\in \mathbb{Z}, \ \theta \in [0,1)$

k \in Z

$k\in \mathbb{Z}$

θ \in [0, 1)

$\theta \in [0,1)$

(tj.

), algorytm szacowania faz nie przewidział właściwej wartości własnej.

\frac{λ_{j} t}{2 π} \notin [0, 1)

$\frac{\lambda_j t}{2\pi} \notin [0,1)$

k \neq 0

$k \neq 0$

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 tak że QPE zawiedzie ( $A$ $A$ ). $\frac{\lambda_j t}{2\pi} \notin [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łasnewynoszą. Są oneznormalizowanematrycy (i jego wartości własne), aby uniknąć przypadku, gdy $e^{\frac{iAt}{16}}$ $A$ $\left\{ 1, 2, 4, 8 \right\}$ . $\frac{\lambda_j t}{2\pi} \notin [0,1)$

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

$A$ $\frac{\lambda_j t}{2\pi} \in [0,1)$

algorithm hhl-algorithm phase-estimation

— Nelimee
źródło

t = 1

$t=1$

k = 2

$k=2$

t = 1

$t=1$

0 < (λ / 2 π) + 2 < 1

$0 < (\lambda / 2\pi) + 2 < 1$

- 4 π < λ < - 2 π

$-4\pi < \lambda < -2\pi$

λ = - 3 π

$\lambda = -3\pi$

λ / 2 π

$\lambda/2\pi$

0

$0$

λ

$\lambda$

θ \in [0, 1)

$\theta \in [0, 1)$

λ < 0

$\lambda < 0$

λ

$\lambda$

λ - 2 k π

$\lambda - 2k\pi$

k = ⌊ \frac{λ}{2 π} ⌋

$k = \lfloor \frac{\lambda}{2\pi} \rfloor$

λ

$\lambda$

2 π

$2\pi$

$A$ $t$ $\lambda t$ $2\pi$ $A$ $N$ $Q$

max_{i} a_{i i} + \sum_{j \neq i} | a_{i j} | \leq N Q,

$\max_i a_{ii}+\sum_{j\neq i}|a_{ij}|\leq NQ,$

min_{i} a_{i i} - \sum_{j \neq i} | a_{i j} | \geq - N Q .

$\min_ia_{ii}-\sum_{j\neq i}|a_{ij}|\geq -NQ.$

a_{i j}

$a_{ij}$

A

$A$

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ć. $N$ $Q$ $n$ $2^n$

— DaftWullie
źródło

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 (\sqrt{N})

$\mathcal{O}(\sqrt{N})$

— Nelimee

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