Algoritmo de Aharonov-Jones-Landau

En informática , el algoritmo Aharonov–Jones–Landau es un algoritmo cuántico eficiente para obtener una aproximación aditiva del polinomio de Jones de un enlace dado en una raíz arbitraria de la unidad . Encontrar una aproximación multiplicativa es un problema #P -difícil, ^[1] por lo que se considera improbable una mejor aproximación. Sin embargo, se sabe que calcular una aproximación aditiva del polinomio de Jones es un problema BQP -completo. ^[2]

El algoritmo fue publicado en 2009 en un artículo escrito por Dorit Aharonov , Vaughan Jones y Zeph Landau.

Historia

A principios de la década de 2000, una serie de artículos de Michael Freedman , Alexei Kitaev , Michael J. Larsen y Zhenghan Wang demostraron que las computadoras cuánticas topológicas basadas en la teoría cuántica de campos topológica tenían la misma potencia computacional que los circuitos cuánticos . En particular, demostraron que el trenzado de anyones de Fibonacci podía usarse para aproximar el polinomio de Jones evaluado en una quinta raíz primitiva de la unidad . Luego demostraron que este problema era BQP -completo.

Si juntamos estos resultados, se deduce que existe un circuito cuántico de longitud polinómica que se aproxima al polinomio de Jones en raíces quintas de la unidad. Sin embargo, este algoritmo era completamente inaccesible para los científicos informáticos cuánticos comunes, ya que los artículos de Freedman-Kitaev-Larsen-Wang utilizaban maquinaria pesada de topología de variedades . La contribución de Aharanov-Jones-Landau fue simplificar este complicado algoritmo implícito de tal manera que fuera aceptable para un público más amplio.

El rastro de Markov

La primera idea detrás del algoritmo es encontrar una descripción más manejable para la operación de evaluación del polinomio de Jones. Esto se hace por medio de la traza de Markov.

La "traza de Markov" es un operador de traza definido en el álgebra de Temperley-Lieb de la siguiente manera: dado un que es un solo diagrama de Kauffman, sea donde es el número de bucles obtenidos al identificar cada punto en la parte inferior del diagrama de Kauffman de con el punto correspondiente en la parte superior. Esto se extiende linealmente a todos los . ${\displaystyle TL_{n}(d)}$ ${\displaystyle T\in TL_{n}(d)}$ ${\displaystyle tr(T)=d^{a-n}}$ ${\displaystyle a}$ ${\displaystyle T}$ ${\displaystyle TL_{n}(d)}$

La traza de Markov es un operador de traza en el sentido de que y para cualquier . También tiene la propiedad adicional de que si es un diagrama de Kauffman cuya hebra más a la derecha va directamente hacia arriba entonces . ${\displaystyle \operatorname {tr} (1)=1}$ ${\displaystyle \operatorname {tr} (XY)=\operatorname {tr} (YX)}$ ${\displaystyle X,Y\in TL_{n}(d)}$ ${\displaystyle X}$ ${\displaystyle \operatorname {tr} (XE_{n-1})={\frac {1}{d}}\operatorname {tr} (X)}$

Un hecho útil explotado por el algoritmo AJL es que la traza de Markov es el único operador de traza con esa propiedad. ^[3] ${\displaystyle TL_{n}(d)}$

Representando B norte Estilo de visualización B_{n} en yo yo norte ( d ) Estilo de visualización TL_{n}(d)

Para un número complejo definimos la función mediante . Se deduce por cálculo directo que si satisface que entonces es una representación. ${\displaystyle A}$ ${\displaystyle \rho _{A}:B_{n}\to TL_{n}(d)}$ ${\displaystyle \sigma _{i}\mapsto AE_{i}+A^{-1}I}$ ${\displaystyle A}$ ${\displaystyle d=-A^{2}-A^{-2}}$ ${\displaystyle \rho _{A}}$

Dado un cerebro, sea el vínculo que se obtiene al identificar la parte inferior del diagrama con su parte superior como en la definición de una traza de Markov, y sea el polinomio de Jones del vínculo resultante. Se cumple la siguiente relación: ${\displaystyle B\in B_{n}}$ ${\displaystyle B^{tr}}$ ${\displaystyle V_{B^{tr}}}$

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

donde es la torsión . Como la torsión se puede calcular fácilmente de forma clásica, esto reduce el problema de aproximar el polinomio de Jones al de aproximar la traza de Markov. ${\displaystyle w}$

La representación del modelo de ruta de yo yo norte ( d ) Estilo de visualización TL_{n}(d)

Deseamos construir una representación compleja de tal manera que la representación de sea unitaria. También deseamos que nuestra representación tenga una codificación sencilla en qubits. ${\displaystyle \tau }$ ${\displaystyle TL_{n}(d)}$ ${\displaystyle \tau \circ \rho _{A}}$ ${\displaystyle B_{n}}$

Dejar

${\displaystyle 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\}}$

y sea el espacio vectorial que tiene como base ortonormal. ${\displaystyle V_{n,k}=\mathbb {C} [Q_{n,k}]}$ ${\displaystyle Q_{n,k}}$

Elegimos definir un mapa lineal definiéndolo sobre la base de generadores . Para ello, necesitamos definir el elemento de la matriz para cualquier . ${\displaystyle \tau :TL_{n}(d)\to V_{n,k}}$ ${\displaystyle \{1,E_{1},\ldots ,E_{n-1}\}}$ ${\displaystyle \tau (E_{i})_{q,q'}}$ ${\displaystyle q,q'\in Q_{n,k}}$

Decimos que y son 'compatibles' si para cualquier y . Geométricamente esto significa que si ponemos y debajo y encima del diagrama de Kauffman en los espacios entre las hebras, entonces ningún componente de conectividad tocará dos espacios que están etiquetados con números diferentes. ${\displaystyle q}$ ${\displaystyle q'}$ ${\displaystyle q(j)=q'(j)}$ ${\displaystyle j\neq i+1}$ ${\displaystyle q(i)=q(i+2)}$ ${\displaystyle q}$ ${\displaystyle q'}$

Si y son conjuntos incompatibles . En caso contrario, sea o (al menos uno de estos números debe estar definido, y si ambos están definidos deben ser iguales) y establezca ${\displaystyle q}$ ${\displaystyle q'}$ ${\displaystyle \tau (E_{i})_{q,q'}=0}$ ${\displaystyle l}$ ${\displaystyle q(i)}$ ${\displaystyle q(i+2)}$

${\displaystyle \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}}}$

donde . Finalmente establecido . ${\displaystyle \lambda _{l}=\sin(\pi l/k)}$ ${\displaystyle d=2\cos(\pi /k)}$

Esta representación, conocida como representación del modelo de ruta , induce una representación unitaria del grupo trenzado. ^{[4] [5]} Además, se cumple que para . ${\displaystyle d=-A^{2}-A^{-2}}$ ${\displaystyle A=ie^{-i\pi /2k}}$

Esto implica que si pudiéramos aproximar la traza de Markov en esta representación esto nos permitirá aproximar el polinomio de Jones en . ${\displaystyle A^{-4}=e^{2\pi i/k}}$

Una versión cuántica de la representación del modelo de trayectoria

Para poder actuar sobre elementos de la representación del modelo de trayectoria mediante circuitos cuánticos, necesitamos codificar los elementos de en qubits de una manera que nos permita describir fácilmente las imágenes de los generadores . ${\displaystyle Q_{n,k}}$ ${\displaystyle E_{i}}$

Representamos cada camino como una secuencia de movimientos, donde indica un movimiento hacia la derecha y indica un movimiento hacia la izquierda. Por ejemplo, el camino estará representado por el estado . ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1,2,3,2}$ ${\displaystyle \left|001\right\rangle }$

Esto se codifica como un subespacio del espacio de estados en qubits. ${\displaystyle \mathbb {C} [Q_{n,k}]}$ ${\displaystyle k-1}$

Definimos los operadores dentro de este subespacio que definimos ${\displaystyle \varphi _{i}}$

${\displaystyle \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}}}$

donde es la matriz de Pauli invirtiendo el bit n y es la posición de la ruta representada por los pasos posteriores . ${\displaystyle X_{i}}$ ${\displaystyle i}$ ${\displaystyle z_{i}}$ ${\displaystyle \left|w\right\rangle }$ ${\displaystyle i}$

Extendemos arbitrariamente la identidad al resto del espacio. ${\displaystyle \varphi _{i}}$

Observamos que el mapeo conserva todas las propiedades de la representación del modelo de ruta. Específicamente, induce una representación unitaria de . Es bastante sencillo demostrar que se puede implementar mediante puertas, por lo que se deduce que se puede implementar para cualquier usando donde es el número de cruces en . ${\displaystyle E_{i}\mapsto \varphi _{i}}$ ${\displaystyle \varphi }$ ${\displaystyle B_{n}}$ ${\displaystyle \varphi _{i}}$ ${\displaystyle {\text{poly}}\left(n,k\right)}$ ${\displaystyle \varphi (B)}$ ${\displaystyle B\in B_{n}}$ ${\displaystyle {\text{poly}}\left(m,n,k\right)}$ ${\displaystyle m}$ ${\displaystyle B}$

Una versión cuántica de la traza de Markov

El beneficio de esta construcción es que nos da una manera de representar la traza de Markov de una manera que puede aproximarse fácilmente.

Sea el subespacio de caminos que describimos en la cláusula anterior, y sea el subespacio abarcado por elementos base que representan recorridos que terminan en la -ésima posición. ${\displaystyle {\mathcal {H}}_{n,k}}$ ${\displaystyle {\mathcal {H}}_{n,k,l}}$ ${\displaystyle l}$

Tenga en cuenta que cada uno de los operadores se fija en conjunto, por lo que esto es válido para cualquier , por lo tanto, el operador está bien definido. ${\displaystyle \varphi _{i}}$ ${\displaystyle {\mathcal {H}}_{n,k,l}}$ ${\displaystyle W\in {\text{Im}}\Phi \left(TL_{n}\left(d\right)\right)}$ ${\displaystyle W|_{l}:=W|_{{\mathcal {H}}_{n,k,l}}}$

Definimos el siguiente operador:

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

donde es la traza de matriz habitual. ${\displaystyle \operatorname {Tr} }$

Resulta que este operador es un operador de traza con la propiedad de Markov, por lo que por el teorema enunciado anteriormente tiene que ser la traza de Markov. Esto finaliza las reducciones requeridas ya que establece que para aproximar el polinomio de Jones basta con aproximar . ${\displaystyle \operatorname {Tr} _{n}}$

El algoritmo

El algoritmo Approximate-Jones-Trace-Closure se  ingresa con cruces ${\displaystyle B\in B_{n}}$ ${\displaystyle m}$ Un entero genera un número tal que ${\displaystyle k}$  ${\displaystyle s}$ ${\displaystyle |s-V_{B^{tr}}(e^{2\pi /k})|<1/poly(n,k,m)}$  con una probabilidad casi exponencialmente pequeña repita para 1. Elija un número aleatorio tal que la probabilidad ${\displaystyle j=1}$ ${\displaystyle poly(n,m,k)}$ ${\displaystyle l\in \{1,\ldots ,k-1\}}$ Elegir un particular es proporcional a 2. Elegir aleatoriamente el que termina en la posición 3. Utilizando la prueba de Hadamard crear una variable aleatoria con Hacer lo mismo para crear con sea el promedio de retorno ${\displaystyle l}$ ${\displaystyle \lambda _{l}}$ ${\displaystyle q\in Q_{n,k}}$ ${\displaystyle l}$ ${\displaystyle x_{j}}$ ${\displaystyle \mathbb {E} \left[x_{j}\right]={\mathcal {Re}}\left\langle \alpha \mid Q\left(B\right)\mid \beta \right\rangle }$ ${\displaystyle y_{j}}$ ${\displaystyle \mathbb {E} \left[y_{j}\right]={\mathcal {Im}}\left\langle \alpha \mid Q\left(B\right)\mid \beta \right\rangle }$ ${\displaystyle r}$ ${\displaystyle x_{j}+iy_{j}}$   ${\displaystyle (-A)^{3w(B^{tr})}d^{n-1}r}$

Tenga en cuenta que el parámetro utilizado en el algoritmo depende de . ${\displaystyle d}$ ${\displaystyle k}$

La exactitud de este algoritmo se establece aplicando el límite de Hoeffding a y por separado. ${\displaystyle x_{j}}$ ${\displaystyle y_{j}}$

Notas

1. Kuperberg, Greg (2009). "¿Qué tan difícil es aproximar el polinomio de Jones?". arXiv : 0908.0512 .
2. Freedman, Michael; Larsen, Michael; Wang, Zhenghan (2000). "Un functor modular que es universal para la computación cuántica". arXiv : quant-ph/0001108 .
3. Jones, VFR (1983). "Índice de subfactores". Invent Math . 1 (72). Código Bibliográfico :1983InMat..72....1J. doi :10.1007/BF01389127.
4. Jones, VFR (1985). "Un invariante polinomial para nudos mediante álgebras de von Neumann". Bull. Amer. Math. Soc . 12 : 103–111. doi : 10.1090/s0273-0979-1985-15304-2 .
5. Jones, VFR (1986). "Grupos de trenzado, álgebras de Hecke y factores de tipo II". Métodos geométricos en álgebras de operadores . 123 : 242–273.

Referencias

1. D. Aharonov, V. Jones, Z. Landau - Un algoritmo cuántico polinomial para aproximar el polinomio de Jones