Квантовая фазовая оценка и алгоритм HHL - требуется знание собственных значений?

Алгоритм оценки квантовой фазы (КОО) вычисляет приближение собственного значения , связанного с данным собственного вектора квантового ворот . $U$

Формально пусть собственный вектор , QPE позволяет найти , лучший бит приближение такое , что & и $\left|\psi\right>$ $U$ $\vert\tilde\theta\rangle$ $m$ $\lfloor2^m\theta\rfloor$ $\theta \in [0,1)$

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

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

Алгоритм HHL ( оригинальная бумага ) принимает в качестве входных данных матрицы , которые удовлетворяют условие и квантовое состояние и вычисляет , который кодирует решение линейной системы . $A$

e^{i A t} is unitary

$e^{iAt} \text{ is unitary }$

| b ⟩

$\vert b \rangle$

| x ⟩

$\vert x \rangle$

A x = b

$Ax = b$

Примечание : Каждая эрмитова матрица Утоли условие на . $A$

Для этого алгоритм HHL использует QPE на квантовых воротах, представленных . Благодаря линейной алгебры результатов, мы знаем , что если являются собственные значения , то собственные значения . Этот результат также изложен в алгоритмах квантовых линейных систем: учебник для начинающих (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) (стр. 29, между уравнениями 68 и 69). $U = e^{iAt}$ $\left\{\lambda_j\right\}_j$ $A$ $\left\{e^{i\lambda_j t}\right\}_j$ $U$

$\theta \in [0,1)$ $e^{i2\pi \theta} = e^{i\lambda_j t}$

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)$

θ = \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)$

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

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

k \neq 0

$k \neq 0$

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

$e^{\frac{iAt}{16}}$ $A$ $\left\{ 1, 2, 4, 8 \right\}$ $\frac{\lambda_j t}{2\pi} \notin [0,1)$

$t$

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

algorithm hhl-algorithm phase-estimation Nelimee
источник

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$

В пределах значений , , если вы беспокоитесь, что для большой матрицы (скажем, кубитов), в то время как сумма строк может быть легко вычислена (потому что записей не много), максимальное значение для всех строк может занять много времени. время (потому что есть строк), будет множество способов получить хорошие приближения к нему (например, выборка или использование знаний о структуре задачи). В худшем случае, вы можете использовать поиск Гровера, чтобы немного ускорить его. $N$ $Q$ $n$ $2^n$

DaftWullie
источник

Гровер не является улучшением: даже если мы сможем использовать алгоритм, нам все равно потребуются запросы , которые уничтожают экспоненциальное улучшение HHL по сравнению с классическими методами и заменяют его квадратичным ускорением. Поэтому остается только надеяться на выборку (ввести другой источник ошибок) или молиться и надеяться, что проблема позволяет нам оценить верхнюю / нижнюю границы. Похоже, главный недостаток алгоритма для меня.

O (\sqrt{N})

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

Нелиме

Конечно, я имел в виду только то, что Гровер дает вам ускорение по квадратному корню по сравнению с наивным способом получения максимума. Конечно, это плохо влияет на общее время работы.

DaftWullie