Polinomio de Jones

12

Hay muchos algoritmos cuánticos bastante estándar que pueden entenderse dentro de un marco muy similar, desde el problema de Simon, el algoritmo de Deutsch, la búsqueda de Grover, el algoritmo de Shor, etc.

Un algoritmo que parece ser completamente diferente es el algoritmo para evaluar el polinomio de Jones . Además, parece que este es un algoritmo crucial para entender en el sentido de que es un problema completo de BQP : exhibe toda la potencia de una computadora cuántica. Además, para una variante del problema, es DQC-1 completo , es decir, exhibe toda la potencia de un qubit limpio .

El documento del algoritmo polinómico de Jones presenta el algoritmo de una manera muy diferente a los otros algoritmos cuánticos. ¿Hay una forma más similar / familiar de entender el algoritmo (específicamente, la unitaria en la variante DQC-1, o simplemente todo el circuito en la variante completa BQP)?U

DaftWullie
fuente

Respuestas:

5

Esta respuesta es más o menos un resumen del artículo de Aharonov-Jones-Landau al que se vinculó, pero con todo lo que no está directamente relacionado con la definición del algoritmo eliminado. Espero que esto sea útil.

El algoritmo de Aharonov-Jones-Landau se aproxima al polinomio de Jones del cierre de la plataforma de una trenza en una raíz de unidad al darse cuenta de que (un cambio de escala) de un elemento de matriz de una cierta matriz unitaria , la imagen de bajo una cierta representación unitaria del grupo de trenzas . Dada una implementación de como un circuito cuántico, aproximar sus elementos matriciales es sencillo utilizando la prueba de Hadamard . La parte no trivial se aproxima a como un circuito cuántico.σkUσσB2nUσUσ

Si es una trenza en hilos con cruces, podemos escribir , donde , y es el generador de que corresponde al cruce del ésimo filamento sobre el st. Es suficiente describir , ya que .σ2nmσ=σa1ϵ1σa2ϵ2σamϵma1,a2,,am{1,2,,2n1}ϵ1,ϵ2,,ϵm{±1}σiB2ni(i+1)UσiUσ=Uσa1ϵ1Uσamϵm

Para definir , primero damos un cierto subconjunto de la base estándar de en el que actúa de manera no trivial. Para , deje que . Llamemos admisible si para todo . (Esto corresponde a describe una ruta de longitud en el gráfico definido en el documento AJL).UσiC22nUσiψ=|b1b2b2ni(ψ)=1+j=1i(1)1bjψ 1i(ψ)k1i{1,2,,2n}ψ2nGk

λr={sin(πr/k)if 1rk1,0otherwise.
Let (esto está mal escrito en el documento AJL; también tenga en cuenta que aquí y solo aquí, no es el índice ). Escriba , donde es el primer bit de , y deje que . Entonces A=ieπi/2ki=1iψ=|ψibibi+1ψii1ψzi=i1(ψi)
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
Definimos para elementos básicos no admisibles .Uσi(ψ)=ψψ

Ahora nos gustaría describir como un circuito cuántico con polinomios muchas (en y ) puertas. Tenga en cuenta que mientras solo cambia dos qubits, también depende de los primeros qubits a través de la dependencia de (y de hecho, depende de todos los qubits para el requisito de admisibilidad). Sin embargo, podemos ejecutar un contador para calcular y almacenar (y también determinar la admisibilidad de la entrada) en logarítmicamente muchos (en ) qubits ancilla, y por lo tanto podemos aplicar el algoritmo Solovay-Kitaev para obtener una buena aproximación aUσinkUσii1zizikUσiusando solo polinomialmente muchas puertas. (El documento apela a Solovay-Kitaev dos veces: una para incrementar el contador en cada paso, y otra para aplicar ; no estoy seguro de si hay una forma más directa de describir cualquiera de estos como circuitos cuánticos con puertas estándar. El documento tampoco menciona la necesidad de verificar la admisibilidad aquí; No estoy seguro de si esto es importante, pero ciertamente al menos necesitamos )Uσi1zik1

Entonces para recapitular:

  1. Comience con una trenza con cruces.σB2nm
  2. Escriba .σ=σa1ϵ1σa2ϵ2σamϵm
  3. Para cada , aplique el algoritmo Solovay-Kitaev para obtener una aproximación de la matriz unitaria (o su inverso si )i{1,2,,m}Uσaiϵi=1
  4. Componga todas las aproximaciones del paso 3 para obtener un circuito cuántico con muchas puertas polinomiales que se aproximen a .Uσ
  5. Aplique las pruebas reales e imaginarias de Hadamard polinomialmente muchas veces con el circuito del paso 4 y el estado .|101010
  6. Promedie los resultados del paso 5 y multiplique por algún factor de escala para obtener una aproximación a las partes real e imaginaria del polinomio de Jones del cierre de la plataforma de evaluado en .σe2πi/k
Evan Jenkins
fuente
2

Usted ha mencionado cinco documentos en la pregunta, pero uno que permanece sin mencionar es la implementación experimental en 2009 . Aquí encontrará el circuito real que se utilizó para evaluar un polinomio de Jones:

ingrese la descripción de la imagen aquí

Esto podría ser lo más cercano a una presentación "más familiar" del algoritmo, ya que el interés en el polinomio de Jones y en DQC-1 ha decaído un poco desde 2009.

Se pueden encontrar más detalles sobre este experimento en la tesis de Gina Passante .

usuario1271772
fuente
1
No tenía conocimiento de ese documento, gracias, aunque estaba más específicamente interesado en la versión completa de BQP. Del mismo modo, en mi breve descripción, no veo mucha explicación sobre lo que es realmente la unitaria . Un
DaftWullie
De nada. Sí, se trata de una PRL de 4 páginas con detalles que no se explican tan a fondo como me gustaría, tal vez hay un "Material complementario" en la página web de la revista que explica mejor la U. El polinomio de Jones y DQC-1 fueron populares alrededor de 2008-2009, pero he dejado de escucharlo desde entonces.
user1271772