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

12

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

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

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

DaftWullie
источник

Ответы:

5

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

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

Если - коса на 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 ,σ2nmσ=σa1ϵ1σa2ϵ2σamϵma1,a2,,am{1,2,,2n1} , и σ я является генератором B 2 п , что соответствует пересекая I - й нити над ( я + 1 ) ст. Достаточно описать U σ i , так как U σ = U ϵ 1 σ a 1U ϵ m σ a m .ϵ1,ϵ2,,ϵm{±1}σiB2ni(i+1)UσiUσ=Uσa1ϵ1Uσamϵm

Чтобы определить , сначала дадим некоторое подмножество стандартного базиса C 2 2 n, на котором U σ i действует нетривиально. Для ψ = | б 1 б 2б 2 н , пусть я ' ( ψ ) = 1 + Σ я ' J = 1 ( - 1 ) 1 - б J . Давайте позвоним ψUσiC22nUσiψ=|b1b2b2ni(ψ)=1+j=1i(1)1bjψ допустимо, если для всех i { 1 , 2 , , 2 n } . (Это соответствует ψ, описывающему путь длины 2 n на графе G k, определенном в статье AJL.) Пусть λ r = { sin ( π r / k ), если  1 r 1i(ψ)k1i{1,2,,2n}ψ2nGkПустьA=ie-πi/2k(это опечатка в статье AJL; также обратите внимание, что здесь и только здесьi=

λr={sin(πr/k)if 1rk1,0otherwise.
A=ieπi/2k не является индексомя). Написатьψ=| ψябIб я + 1, гдеψяпервыйя-1битф, и пустьгя= я - 1 (ψя). Тогда U σ i ( | ψ i 00 )i=1iψ=|ψibibi+1ψii1ψzi=i1(ψi) ОпределимU σ я (ψ)=ψдля не-допустимые базисные элементыψ.
Uσi(|ψi00)=A1|ψi00Uσi(|ψi01)=(Aλzi1λzi+A1)|ψi01+Aλzi+1λzi1λzi|ψi10Uσi(|ψi10)=Aλzi+1λzi1λzi|ψi01+(Aλzi+1λzi+A1)|ψi10Uσi(|ψi11)=A1|ψi11
Uσi(ψ)=ψψ

UσinkUσii1zizikUσiUσi1zik1

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

  1. σB2nm
  2. σ=σa1ϵ1σa2ϵ2σamϵm
  3. i{1,2,,m}Uσaiϵi=1
  4. Uσ
  5. |101010
  6. σe2πi/k
Эван Дженкинс
источник
2

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

введите описание изображения здесь

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

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

user1271772
источник
1
Un
Пожалуйста. Да, это был 4-страничный PRL с деталями, которые не были объяснены так тщательно, как мне хотелось бы - возможно, на веб-странице журнала есть «Дополнительный материал», который лучше объясняет U. Полином Джонс и DQC-1 были популярны примерно в 2008-2009 годах, но с тех пор я перестал слышать об этом.
user1271772