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\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^{iAt} \text{ is unitary }$$ i stanu kwantowa $\vert b \rangle$ i oblicza $\vert x \rangle$ 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 = 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, e i 2 gatunku θ = e I λ j T . To prowadzi nas do równania 2 π θ = λ j t + 2 k π $\theta \in [0,1)$$e^{i2\pi \theta} = e^{i\lambda_j t}$ tj. θ = λ j

$$2\pi \theta = \lambda_j t + 2k\pi, \qquad k\in \mathbb{Z}, \ \theta \in [0,1)$$ Analizując trochę implikacje warunków k ∈ Z i θ ∈ [ 0 , 1 ) , doszedłem do wniosku, że jeśli λ j $$\theta = \frac{\lambda_j t}{2\pi} + k, \qquad k\in \mathbb{Z}, \ \theta \in [0,1)$$ $k\in \mathbb{Z}$$\theta \in [0,1)$(tj.K≠0), algorytm szacowania faz nie przewidział właściwej wartości własnej.$\frac{\lambda_j t}{2\pi} \notin [0,1)$$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 A, tak że QPE zawiedzie ( λ j$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łasneAwynoszą{1,2,4,8}. Są oneznormalizowanematrycy (i jego wartości własne), aby uniknąć przypadku, gdyλj$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)$

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

$$\max_i a_{ii}+\sum_{j\neq i}|a_{ij}|\leq NQ,$$ $$\min_ia_{ii}-\sum_{j\neq i}|a_{ij}|\geq -NQ.$$ $a_{ij}$$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$