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 de unidad arbitraria . 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 completo de BQP . [2]
El algoritmo fue publicado en 2009 en un artículo escrito por Dorit Aharonov , Vaughan Jones y Zeph Landau .
El rastro de Markov
La primera idea detrás del algoritmo es encontrar una descripción más manejable para la operación de evaluar el polinomio de Jones. Esto se hace mediante 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 , dejemos dónde es el número de bucles logrados al identificar cada punto en la parte inferior de Diagrama de Kauffman con el punto correspondiente en la parte superior. Esto se extiende linealmente a todos los.
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 hacia arriba y luego .
Un hecho útil explotado por el algoritmo AJL es que la traza de Markov es el operador de traza único en con esa propiedad. [3]
Representando en
Para un número complejo definimos el mapa vía . De ello se deduce por cálculo directo que si satisface que luego es una representación.
Dado un cerebro dejar sea el vínculo obtenido al identificar la parte inferior del diagrama con su parte superior como en la definición de una traza de Markov, y sea ser el polinomio de Jones del enlace de resultado. Se cumple la siguiente relación:
dónde es el retorcerse . Como el retorcimiento 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.
La representación del modelo de ruta de
Deseamos construir una representación compleja de tal que la representacion de será unitario. También deseamos que nuestra representación tenga una codificación sencilla en qubits.
Dejar
y deja ser el espacio vectorial que tiene como base ortonormal.
Elegimos definir un mapa lineal definiéndolo sobre la base de generadores . Para hacerlo, necesitamos definir el elemento de la matriz para cualquier .
Nosotros decimos eso 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 los hilos, ningún componente de conectividad tocará dos espacios que están etiquetados con números diferentes.
Si y son incompatibles . De lo contrario, deja ser tanto o (al menos uno de estos números debe estar definido, y si ambos están definidos deben ser iguales) y establecer
dónde . Finalmente establecido.
Esta representación, conocida como representación del modelo de trayectoria , induce una representación unitaria del grupo de trenzas. [4] [5] Además, sostiene que por .
Esto implica que si pudiéramos aproximarnos a la traza de Markov en esta representación, esto nos permitirá aproximarnos al polinomio de Jones en .
Una versión cuántica de la representación del modelo de ruta.
Para poder actuar sobre elementos de la representación del modelo de ruta mediante circuitos cuánticos, necesitamos codificar los elementos de en qubits de una manera que nos permite describir fácilmente las imágenes de los generadores .
Representamos cada camino como una secuencia de movimientos, donde indica un movimiento a la derecha y indica un movimiento a la izquierda. Por ejemplo, el camino estará representado por el estado .
Esto codifica como un subespacio del espacio de estado en qubits.
Definimos los operadores dentro de este subespacio definimos
dónde es la matriz de Pauli volteando elth bit y es la posición de la ruta representada por después pasos.
Extendemos arbitrariamente para ser la identidad en el resto del espacio.
Notamos que el mapeo conserva todas las propiedades de la representación del modelo de ruta. En concreto, induce una representación unitaria de . Es bastante sencillo demostrar que puede ser implementado por puertas, por lo que se sigue que se puede implementar para cualquier utilizando dónde es el número de cruces en .
Una versión cuántica de la traza de Markov
El beneficio de esta construcción es que nos brinda una forma de representar la traza de Markov de una manera que se puede aproximar fácilmente.
Dejar ser el subespacio de caminos que describimos en la cláusula anterior, y dejar ser el subespacio atravesado por elementos base que representan paseos que terminan en el -ésima posición.
Tenga en cuenta que cada uno de los operadores reparar inteligente, por lo que esto es válido para cualquier , de ahí el operador está bien definido.
Definimos el siguiente operador:
dónde es el rastro de matriz habitual.
Resulta que este operador es un operador de traza con la propiedad de Markov, por lo que según el teorema mencionado anteriormente tiene que ser la traza de Markov. Con esto finalizan las reducciones requeridas ya que establece que para aproximar el polinomio de Jones basta con aproximar.
El algoritmo
se introduce el algoritmo Approximate-Jones-Trace-Closure con cruces Un entero generar un número tal que con casi una probabilidad exponencialmente pequeña repetir para a 1. Elige un al azar tal que la probabilidad para elegir un particular es proporcional a 2. Elija aleatoriamente que termina en posición 3. Con la prueba de Hadamard, cree una variable aleatoria con Haz lo mismo para crear con dejar ser el promedio de regreso
Tenga en cuenta que el parámetro utilizado en el algoritmo depende de .
La exactitud de este algoritmo se establece aplicando el límite de Hoeffding a y por separado.
Notas
- ^ Kuperberg, Greg (2009). "¿Qué tan difícil es aproximar el polinomio de Jones?". arXiv : 0908.0512 .
- ^ Freedman, Michael; Larsen, Michael; Wang, Zhenghan (2000). "Un funtor modular que es universal para la computación cuántica". arXiv : quant-ph / 0001108 .
- ^ Jones, VFR (1983). "Índice de subfactores". Inventar las matemáticas . 1 (72). Código Bibliográfico : 1983InMat..72 .... 1J . doi : 10.1007 / BF01389127 .
- ^ Jones, VFR (1985). "Un invariante polinomial de nudos a través de álgebras de von Neumann" . Toro. Amer. Matemáticas. Soc . 12 : 103-111. doi : 10.1090 / s0273-0979-1985-15304-2 .
- ^ Jones, VFR (1986). "Grupos de trenzas, álgebras de Hecke y factores de tipo II". Métodos geométricos en álgebras de operadores . 123 : 242-273.
Referencias
- D. Aharonov, V. Jones, Z. Landau: un algoritmo cuántico polinómico para aproximar el polinomio de Jones