Алгоритм Ааронова – Джонса – Ландау

В информатике алгоритм Ааронова-Джонса-Ландау представляет собой эффективный квантовый алгоритм для получения аддитивной аппроксимации полинома Джонса заданной ссылки при произвольном корне из единицы . Нахождение мультипликативной аппроксимации — #P -сложная задача, поэтому лучшее приближение считается маловероятным. Однако известно, что вычисление аддитивной аппроксимации полинома Джонса является BQP -полной задачей.

Алгоритм был опубликован в 2009 году в статье, написанной Дорит Аароновой , Воаном Джонсом и Зефом Ландау .

История

В начале 2000-х годов серия статей Майкла Фридмана , Алексея Китаева , Майкла Дж. Ларсена и Чжэнхана Ванга продемонстрировала, что топологические квантовые компьютеры, основанные на топологической квантовой теории поля, обладают той же вычислительной мощностью, что и квантовые схемы . В частности, они показали, что сплетение анионов Фибоначчи можно использовать для аппроксимации полинома Джонса, оцененного по примитивному корню пятой степени из единицы . Затем они показали, что эта проблема является BQP -полной.

Если объединить эти результаты, это означает, что существует квантовая схема полиномиальной длины, которая аппроксимирует полином Джонса при корнях 5-й степени из единицы. Однако этот алгоритм был совершенно недоступен обычным ученым, занимающимся квантовыми компьютерами, поскольку в работах Фридмана-Китаева-Ларсена-Ванга использовалась тяжелая техника из топологии многообразий . Вклад Ахаранова-Джонса-Ландау заключался в упрощении этого сложного неявного алгоритма таким образом, чтобы он был понятен более широкой аудитории.

Марковский след

Первая идея алгоритма состоит в том, чтобы найти более понятное описание операции вычисления полинома Джонса. Это делается с помощью следа Маркова.

«Марковский след» — это оператор следа, определенный в алгебре Темперли – Либа. $TL_{n}(d)$ следующим образом: учитывая $T\in TL_{n}(d)$ которая представляет собой одну диаграмму Кауфмана , пусть $tr(T)=d^{a-n}$ где $a$ - это количество петель, полученное путем определения каждой точки внизу $T$Диаграмма Кауфмана с соответствующей точкой вверху. Это распространяется линейно на все $TL_{n}(d)$.

След Маркова является оператором следа в том смысле, что $\operatorname {tr} (1)=1$ и $\operatorname {tr} (XY)=\operatorname {tr} (YX)$ для любого $X,Y\in TL_{n}(d)$. Он также имеет дополнительное свойство: если $X$ это диаграмма Кауфмана, правая цепь которой тогда идет прямо вверх $\operatorname {tr} (XE_{n-1})={\frac {1}{d}}\operatorname {tr} (X)$.

Полезный факт, используемый алгоритмом AJL, заключается в том, что марковский след является уникальным оператором следа на $TL_{n}(d)$ с этим свойством.

Представляя $B_{n}$ в $TL_{n}(d)$

Для комплексного числа $A$ мы определяем карту $\rho _{A}:B_{n}\to TL_{n}(d)$ с помощью $\sigma _{i}\mapsto AE_{i}+A^{-1}I$. Непосредственным вычислением следует, что если $A$ удовлетворяет этому $d=-A^{2}-A^{-2}$ затем $\rho _{A}$ является представлением.

Учитывая мозг $B\in B_{n}$ позволять $B^{tr}$ — связь, полученная путем отождествления нижней части диаграммы с ее вершиной, как в определении марковского следа, и пусть $V_{B^{tr}}$ быть полиномом Джонса результирующей ссылки. Имеет место следующее соотношение:

$V_{B^{tr}}(A^{-4})=(-A)^{3w(B^{tr})}d^{n-1}\operatorname {tr} (\rho _{A}(B))$

где $w$ это корчи . Поскольку корчу можно легко вычислить классически, это сводит проблему аппроксимации полинома Джонса к проблеме аппроксимации следа Маркова.

Представление модели пути $TL_{n}(d)$

Мы хотим построить сложное представление $\tau$ из $TL_{n}(d)$ такое, что представление $\tau \circ \rho _{A}$ из $B_{n}$ будет унитарным. Мы также хотим, чтобы наше представление имело прямую кодировку в кубиты.

Позволять

$Q_{n,k}=\left\{q\in \left\{1,\ldots ,k-1\right\}^{n+1}\mid q(1)=1,\left|q(i)-q(i+1)\right|=1\right\}$

и пусть $V_{n,k}=\mathbb {C} [Q_{n,k}]$ быть векторным пространством, которое имеет $Q_{n,k}$ как ортонормированный базис.

Мы выбираем определение линейной карты $\tau :TL_{n}(d)\to V_{n,k}$ определив его на основе генераторов $\{1,E_{1},\ldots ,E_{n-1}\}$. Для этого нам нужно определить матричный элемент $\tau (E_{i})_{q,q'}$ для любого $q,q'\in Q_{n,k}$.

Мы говорим, что $q$ и $q'$ являются «совместимыми», если $q(j)=q'(j)$ для любого $j\neq i+1$ и $q(i)=q(i+2)$. Геометрически это означает, что если положить $q$ и $q'$ ниже и выше диаграммы Кауфмана в промежутках между нитями, тогда ни один компонент связности не будет касаться двух промежутков, которые помечены разными номерами.

Если $q$ и $q'$ несовместимый набор $\tau (E_{i})_{q,q'}=0$. Иначе, легко $l$ быть либо $q(i)$ или $q(i+2)$ (должно быть определено хотя бы одно из этих чисел, а если определены оба, они должны быть равны) и установите

$\tau \left(E_{i}\right)_{q,q'}={\begin{cases}{\frac {\lambda _{l+1}}{\lambda _{l}}}&q\left(i+1\right)=q'(i+1)>l\\{\frac {\sqrt {\lambda _{l-1}\lambda _{l+1}}}{\lambda _{l}}}&q\left(i+1\right)\neq q'(i+1)\\{\frac {\lambda _{l-1}}{\lambda _{l}}}&q\left(i+1\right)=q'(i+1)<l\end{cases}}$

где $\lambda _{l}=\sin(\pi l/k)$. Наконец установил $d=2\cos(\pi /k)$.

Это представление, известное как представление модели пути , порождает унитарное представление группы кос. Более того, он утверждает, что $d=-A^{2}-A^{-2}$ для $A=ie^{-i\pi /2k}$.

Это означает, что если мы сможем аппроксимировать марковский след в этом представлении, это позволит нам аппроксимировать полином Джонса в $A^{-4}=e^{2\pi i/k}$.

Квантовая версия представления модели пути

Чтобы иметь возможность воздействовать на элементы представления модели пути посредством квантовых схем, нам необходимо закодировать элементы $Q_{n,k}$ на кубиты таким образом, чтобы можно было легко описать образы генераторов $E_{i}$.

Представим каждый путь как последовательность ходов, где $0$ указывает на движение вправо и $1$ указывает на движение влево. Например, путь $1,2,3,2$ будет представлено государством $\left|001\right\rangle$.

Это кодирует $\mathbb {C} [Q_{n,k}]$ как подпространство пространства состояний на $k-1$ кубиты.

Определим операторы $\varphi _{i}$ внутри этого подпространства мы определяем

$\Phi _{i}\left|w\right\rangle ={\begin{cases}0&w_{i}=w_{i+1}\\{\frac {\lambda _{z_{i}-\left(-1\right)^{w_{i}}}}{\lambda _{z_{i}}}}\left|w\right\rangle +{\frac {\sqrt {\lambda _{z_{i}-1}\lambda _{z_{i}+1}}}{\lambda _{z_{i}}}}X_{i}X_{i+1}\left|w\right\rangle &w_{i}\neq w_{i+1}\end{cases}}$

где $X_{i}$ это матрица Паули, переворачивающая $i$этот бит и $z_{i}$ это положение пути, представленного $\left|w\right\rangle$ после $i$ шаги.

Мы произвольно расширяем $\varphi _{i}$ быть личностью на остальном пространстве.

Заметим, что отображение $E_{i}\mapsto \varphi _{i}$ сохраняет все свойства представления модели пути. В частности, это индуцирует унитарное представление $\varphi$ из $B_{n}$. Довольно просто показать, что $\varphi _{i}$ может быть реализован путем ${\text{poly}}\left(n,k\right)$ ворота, поэтому следует, что $\varphi (B)$ может быть реализован для любого $B\in B_{n}$ с использованием ${\text{poly}}\left(m,n,k\right)$ где $m$ количество пересечений в $B$.

Квантовая версия марковского следа

Преимущество этой конструкции в том, что она дает нам возможность представить марковский след таким образом, чтобы его можно было легко аппроксимировать.

Позволять ${\mathcal {H}}_{n,k}$ — подпространство путей, которые мы описали в предыдущем пункте, и пусть ${\mathcal {H}}_{n,k,l}$ быть подпространством, охватываемым базовыми элементами, которые представляют обходы, заканчивающиеся на $l$-я позиция.

Обратите внимание, что каждый из операторов $\varphi _{i}$ исправить ${\mathcal {H}}_{n,k,l}$ по порядку, и это справедливо для любого $W\in {\text{Im}}\Phi \left(TL_{n}\left(d\right)\right)$, следовательно, оператор $W|_{l}:=W|_{{\mathcal {H}}_{n,k,l}}$ хорошо определен.

Мы определяем следующий оператор:

$\operatorname {Tr} _{n}\left(W\right)={\frac {1}{N}}\sum _{l=1}^{k-1}\lambda _{l}\operatorname {Tr} \left(W|_{l}\right)$

где $\operatorname {Tr}$ — обычный матричный след.

Оказывается, этот оператор является оператором следа с марковским свойством, поэтому по сформулированной выше теореме он должен быть марковским следом. На этом необходимые сокращения завершаются, поскольку устанавливается, что для аппроксимации полинома Джонса достаточно аппроксимировать $\operatorname {Tr} _{n}$.

Алгоритм

algorithm Approximate-Jones-Trace-Closure is
    input $B\in B_{n}$ with $m$ crossings
                An integer $k$
    output a number $s$ such that $|s-V_{B^{tr}}(e^{2\pi /k})|<1/poly(n,k,m)$ 
                 with all but exponentially small probability
    repeat for $j=1$ to $poly(n,m,k)$
        1. Pick a random $l\in \{1,\ldots ,k-1\}$ such that the probability
           to choose a particular $l$ is proportional to $\lambda _{l}$
        2. Randomly pick $q\in Q_{n,k}$ which ends in position $l$
        3. Using the Hadamard test create a random variable $x_{j}$ with
           $\mathbb {E} \left[x_{j}\right]={\mathcal {Re}}\left\langle \alpha \mid Q\left(B\right)\mid \beta \right\rangle$
    Do the same to create $y_{j}$ with $\mathbb {E} \left[y_{j}\right]={\mathcal {Im}}\left\langle \alpha \mid Q\left(B\right)\mid \beta \right\rangle$
    let $r$ be the average of $x_{j}+iy_{j}$
    return $(-A)^{3w(B^{tr})}d^{n-1}r$

Обратите внимание, что параметр $d$ используемый в алгоритме, зависит от $k$.

Корректность этого алгоритма устанавливается путем применения границы Хеффдинга к $x_{j}$ и $y_{j}$ отдельно.

Ссылки

1. Д. Ааронов, В. Джонс, З. Ландау - Полиномиальный квантовый алгоритм аппроксимации полинома Джонса