Квантовый алгоритм для линейных систем уравнений (HHL09): Шаг 1 - Путаница относительно использования алгоритма оценки фазы

Я уже некоторое время пытаюсь разобраться со знаменитым (?) Документом « Квантовый алгоритм для линейных систем уравнений» (Harrow, Hassidim & Lloyd, 2009) (более широко известный как статья с алгоритмом HHL09 ).

На самой первой странице они говорят :

Мы набросаем здесь основную идею нашего алгоритма, а затем обсудим ее более подробно в следующем разделе. Учитывая эрмитову матрицу A и единичный вектор → b , предположим, что мы хотели бы найти → x, удовлетворяющий A → x = → b . (Мы обсудим более поздние вопросы эффективности, а также о том, как можно ослабить сделанные нами предположения относительно A и → b .) Во-первых, алгоритм представляет → b как квантовое состояние | б ⟩ = Σ N $N\times N$$A$$\vec{b}$$\vec{x}$$A\vec{x} = \vec{b}$$A$$\vec{b}$$\vec{b}$. Далее мы используем методы гамильтонова моделирования [3, 4], чтобы применить eiAtк| бя⟩для наложения разного временит. Эта способность возводить в степеньАпереводит через хорошо известную технику оценки фазы [5–7] в способность разлагать| б⟩ в базисе матрицыAи найти соответствующие собственные значения ЛJнеформально, состояние системы после этой стадии близко кΣ J $|b\rangle = \sum_{i=1}^{N}b_i|i\rangle$$e^{iAt}$$|b_i\rangle$$t$$A$$|b\rangle$$A$$\lambda_j$, гдеуJесть собственный базис Аи| б⟩=Σ J = N J = 1 βJ| уJ⟩.$\sum_{j=1}^{j=N} \beta_j |u_j\rangle|\lambda_j\rangle$$u_j$$A$$|b\rangle = \sum_{j=1}^{j=N} \beta_j|u_j\rangle$

Все идет нормально. Как описано в Nielsen & Chuang в главе « Квантовое преобразование Фурье и его приложения », алгоритм оценки фазы используется для оценки в e i 2 π φ, который является собственным значением, соответствующим собственному вектору | у ⟩ унитарного оператора U .$\varphi$$e^{i2\pi \varphi}$$|u\rangle$$U$

Вот соответствующая часть от Nielsen & Chuang:

Алгоритм оценки фазы использует два регистра. Первый регистр содержит кубитов, изначально находящихся в состоянии | 0 ⟩ . То, как мы выбираем t, зависит от двух вещей: количества цифр точности, которые мы хотим иметь в нашей оценке для φ , и с какой вероятностью мы хотим, чтобы процедура оценки фазы была успешной. Зависимость t от этих величин естественно вытекает из следующего анализа.$t$$|0\rangle$$t$$\varphi$$t$

Второй регистр начинается в состоянии и содержит столько же кубитов , как это необходимо для хранения | у ⟩ . Оценка фазы выполняется в два этапа. Сначала мы применяем схему, показанную на рисунке 5.2. Схема начинается с применения преобразования Адамара к первому регистру с последующим применением операций с управляемым U во втором регистре, причем U увеличивается до последовательных степеней, равных двум. Конечное состояние первого регистра легко увидеть:$|u\rangle$$|u\rangle$$U$$U$

$$\frac{1}{2^{t/2}}\left(|0\rangle+\text{exp}(2\pi i 2^{t-1}\varphi)|1\rangle)(|0\rangle+\text{exp}(2\pi i 2^{t-2}\varphi)|1\rangle)...(|0\rangle+\text{exp}(2\pi i 2^{0}\varphi)|1\rangle\right)= \frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}\text{exp}(2\pi i \varphi k)|k\rangle$$

Второй этап оценки фазы заключается в применении обратного квантового преобразования Фурье к первому регистру. Это получается путем обращения схемы для квантового преобразования Фурье в предыдущем разделе (упражнение 5.5) и может быть выполнено за шагов. Третий и последний этап оценки фазы заключается в считывании состояния первого регистра путем выполнения измерений на вычислительной основе. Покажем, что это дает довольно хорошую оценку φ . Общая схема алгоритма показана на рисунке 5.3.$\Theta (t^2)$$\varphi$

Чтобы прояснить нашу интуицию относительно того, почему оценка фазы работает, предположим, что может быть выражено точно в битах, как φ = 0. φ 1 . , , φ т . Тогда состояние (5.20), полученное в результате первого этапа оценки фазы, может быть переписано$\varphi$$\varphi = 0.\varphi_1 ... \varphi_t$

$$\frac{1}{2^{t/2}}(|0\rangle + \exp(2\pi i 0.\varphi_t|1\rangle)(|0\rangle + \exp(2\pi i 0.\varphi_{t-1}\varphi_t|1\rangle)...(|0\rangle + \exp(2\pi i 0.\varphi_1...\varphi_t|1\rangle)$$

$|\varphi_1 ...\varphi_t\rangle$$\varphi$

$\varphi$$U$$|u\rangle$

$$\frac{1}{2^{t/2}}\sum_{j = 0}^{2^t-1}\exp(2\pi i \varphi j)|j\rangle |u\rangle \to |\tilde \varphi \rangle |u\rangle$$

^$\dagger$

Шаг 1 (оценка фазы):

$A$$A$$e^{iAt}$$A$

$U=e^{iAt}$$|u_j\rangle$$U$$N\times N$$N$$A$$\lambda_j$$e^{iAt}$$e^{i \lambda_j t}$$U$$e^{2\pi i \varphi} \equiv e^{ i \lambda_j t}$$\varphi = \frac{\lambda_j t}{2\pi}$$|b\rangle$$U$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle$$|u_j\rangle$$U$$|u\rangle \otimes (|0\rangle)^{\otimes t}$$|u\rangle \otimes |\tilde\varphi\rangle$$|u_j\rangle \otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$$\lambda_j$$|u_j\rangle$$A$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$

Вопрос:

$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde\lambda_j\rangle$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$

$\frac{t}{2\pi}$

Изменить: Часть 2 была задана здесь, чтобы сделать отдельные вопросы более сфокусированными.

^{У меня также есть несколько путаниц в отношении шага 2 и шага 3 алгоритма HHL09, но я решил опубликовать их как отдельные цепочки вопросов, так как этот становится слишком длинным. Я добавлю ссылки на эти темы вопросов в этом посте, как только они будут созданы.}

$\dagger$

Это зависит от бумаг, но я видел 2 подхода:

1. $t$$t = t_0 = 2\pi$

2. $\tilde \lambda$$\lambda$$\frac{t}{2\pi}$$\tilde \lambda$$\frac{\lambda t}{2\pi}$

Вот несколько ссылок:

1. $t$$2\pi$

2. $t$$t_0$$2\pi$

3. $t = 2\pi$

4. $t_0 = 2\pi$

$\frac{t}{2\pi}$

$U$$e^{-i\lambda t}$$\lambda t/(2\pi)$$A$$\lambda$

$U$$e^{-i\lambda t}$$A$$\lambda\rangle$

$|\tilde\lambda\rangle$