Полином Джонс

Существует много довольно стандартных квантовых алгоритмов, которые можно понять в очень похожих рамках: от алгоритма Дойча Саймона, поиска Гровера, алгоритма Шора и так далее.

Один алгоритм, который кажется совершенно другим, - это алгоритм оценки полинома Джонса . Более того, кажется, что это ключевой алгоритм для понимания в том смысле, что это проблема, полная BQP : он демонстрирует всю мощь квантового компьютера. Кроме того, для варианта задачи он завершен с DQC-1 , то есть обладает полной мощностью одного чистого кубита .

В статье, посвященной полиномиальному алгоритму Джонса, алгоритм представлен совершенно иначе, чем другие квантовые алгоритмы. Есть ли более похожий / знакомый способ, которым я могу понять алгоритм (в частности, унитарный в варианте DQC-1 или просто вся схема в BQP-полном варианте)?$U$

Этот ответ является более или менее кратким изложением статьи Ааронова-Джонса-Ландау, на которую вы ссылались, но со всем, что не имеет прямого отношения к определению алгоритма. Надеюсь, это полезно.

Алгоритм Ааронова-Джонса-Ландау аппроксимирует многочлен Джонса замыкания плат косы в k- м корне единицы, реализуя его как (некоторый перемасштабирование) матричного элемента некоторой унитарной матрицы U σ , изображения σ при некотором унитарном представлении группы кос B 2 n . Учитывая реализацию U σ в качестве квантового контура, аппроксимация его матричных элементов является простым, используя тест Адамара . Нетривиальная часть аппроксимирует U σ как квантовую цепь.$\sigma$$k$$U_\sigma$$\sigma$$B_{2n}$$U_\sigma$$U_\sigma$

Если - коса на 2 n нитях с m пересечениями, мы можем написать σ = σ ϵ 1 a 1 σ ϵ 2 a 2 ⋯ σ ϵ m a m , где a 1 , a 2 , … , a m ∈ { 1 , 2 , … , 2 n - 1 } , ϵ 1 , ϵ 2$\sigma$$2n$$m$$\sigma = \sigma_{a_1}^{\epsilon_1} \sigma_{a_2}^{\epsilon_2} \cdots \sigma_{a_m}^{\epsilon_m}$$a_1, a_2, \ldots, a_m \in \{1, 2, \ldots, 2n - 1\}$ , и σ я является генератором B 2 п , что соответствует пересекая I - й нити над ( я + 1 ) ст. Достаточно описать U σ i , так как U σ = U ϵ 1 σ a 1 ⋯ U ϵ m σ a m .$\epsilon_1, \epsilon_2, \ldots, \epsilon_m \in \{\pm 1\}$$\sigma_i$$B_{2n}$$i$$(i + 1)$$U_{\sigma_i}$$U_\sigma = U_{\sigma_{a_1}}^{\epsilon_1} \cdots U_{\sigma_{a_m}}^{\epsilon_m}$

Чтобы определить , сначала дадим некоторое подмножество стандартного базиса C 2 2 n, на котором U σ i действует нетривиально. Для ψ = | б 1 б 2 ⋯ б 2 н ⟩ , пусть ℓ я ' ( ψ ) = 1 + Σ я ' J = 1 ( - 1 ) 1 - б J . Давайте позвоним $U_{\sigma_i}$$\mathbb{C}^{2^{2n}}$$U_{\sigma_i}$$\psi = \lvert b_1 b_2 \cdots b_{2n} \rangle$$\ell_{i'}(\psi) = 1 + \sum_{j = 1}^{i'} (-1)^{1-b_j}$$\psi$ допустимо, если для всех i ′ ∈ { 1 , 2 , … , 2 n } . (Это соответствует ψ, описывающему путь длины 2 n на графе G k, определенном в статье AJL.) Пусть λ r = { sin ( π r / k ), если  1 ≤ r $1 \leq \ell_{i'}(\psi) \leq k - 1$$i' \in \{1, 2, \ldots, 2n\}$$\psi$$2n$$G_k$ПустьA=ie-πi/2k(это опечатка в статье AJL; также обратите внимание, что здесь и только здесьi=

$$\lambda_r = \begin{cases}\sin(\pi r / k) & \textrm{if $1 \leq r \leq k - 1$},\\ 0 & \textrm{otherwise.}\end{cases}$$ $A = ie^{-\pi i/2k}$ не является индексомя). Написатьψ=| ψябIб я + 1 ⋯⟩, гдеψяпервыйя-1битф, и пустьгя=ℓ я - 1 (ψя). Тогда U σ i ( | ψ i 00 ⋯ ⟩ $i = \sqrt{-1}$$i$$\psi = \lvert \psi_i b_i b_{i+1} \cdots\rangle$$\psi_i$$i - 1$$\psi$$z_i = \ell_{i-1}(\psi_i)$ ОпределимU σ я (ψ)=ψдля не-допустимые базисные элементыψ. $$\begin{align} U_{\sigma_i}(\lvert\psi_i 00 \cdots\rangle) & = A^{-1}\lvert\psi_i 00 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 01 \cdots \rangle) & = \left( A\frac{\lambda_{z_i-1}}{\lambda_{z_i}} + A^{-1}\right)\lvert\psi_i 01 \cdots\rangle + A\frac{\sqrt{\lambda_{z_i+1}\lambda_{z_i-1}}}{\lambda_{z_i}}\lvert\psi_i 10 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 10 \cdots \rangle) & = A\frac{\sqrt{\lambda_{z_i+1}\lambda_{z_i-1}}}{\lambda_{z_i}}\lvert\psi_i 01 \cdots\rangle + \left(A\frac{\lambda_{z_i+1}}{\lambda_{z_i}} + A^{-1}\right)\lvert\psi_i 10 \cdots\rangle\\ U_{\sigma_i}(\lvert\psi_i 11 \cdots\rangle) & = A^{-1}\lvert\psi_i 11 \cdots\rangle \end{align}$$ $U_{\sigma_i}(\psi) = \psi$$\psi$

$U_{\sigma_i}$$n$$k$$U_{\sigma_i}$$i - 1$$z_i$$z_i$$k$$U_{\sigma_i}$$U_{\sigma_i}$$1 \leq z_i \leq k - 1$

Итак, резюмируем:

1. $\sigma \in B_{2n}$$m$
2. $\sigma = \sigma_{a_1}^{\epsilon_1} \sigma_{a_2}^{\epsilon_2} \cdots \sigma_{a_m}^{\epsilon_m}$
3. $i \in \{1, 2, \ldots, m\}$$U_{\sigma_{a_i}}$$\epsilon_i = -1$
4. $U_{\sigma}$
5. $\lvert 1010 \cdots 10\rangle$
6. $\sigma$$e^{2\pi i/k}$

Вы упомянули пять статей в этом вопросе, но одна из них, которая не упоминается, - это экспериментальная реализация в 2009 году . Здесь вы найдете фактическую схему, которая использовалась для оценки полинома Джонса:

Это может быть ближе всего к «более знакомому» представлению алгоритма, так как интерес к полиному Джонса и к DQC-1 немного ослаб с 2009 года.

Более подробную информацию об этом эксперименте можно найти в диссертации Джины Пассанте .