¿Existe un conjunto de compuerta unitario finito que pueda realizar exactamente todas las QFT de orden

11

Estoy considerando ideas sobre algoritmos cuánticos exactos. En particular, estoy considerando las posibles limitaciones de EQP , que consiste en lenguajes exactamente decidibles por las familias de circuitos cuánticos uniformes de polimetro sobre un conjunto arbitrario de puerta finita.

La transformada cuántica de Fourier (QFT), dada por

FN=1N[111111ωω2ω3ωN11ω2ω4ω6ωN21ω3ω6ω9ωN31ωN1ωN2ωN3ω(N1)2]for ω=e2πi/N,
es una parte famosa de la teoría computacional cuántica. En el caso deN=2n , existe una descomposición bien conocida deFN en Hadamards, puertas SWAP y puertas diagonales
CZ2T=diag(1,1,1,e2πi/2T)
T1EQPPF2nF2nCZ2n

Obviamente, según el teorema de Solovay-Kitaev, podemos aproximar las puertas o arbitrariamente bien con cualquier conjunto de puertas aproximadamente universal que esté cerrado bajo inversas. Lo que me gustaría saber es si existe un conjunto de puertas finito que pueda dar cuenta exactamente de estas familias de operadores, o, lo que sospecho es más probable, si existe una prueba de que no existe tal conjunto de puertas finito.F2nCZ2n

Pregunta. ¿Existe una descomposición de como una familia de circuitos uniformes de polytime en un conjunto de puertas finitas, o una prueba de que esto es imposible?{F2n}n1

Niel de Beaudrap
fuente

Respuestas:

7

No, no hay descomposición de toda la familia en un único conjunto de puertas finito. Este es el por qué.{F2n}n1

Las QFT involucran solo coeficientes sobre , el cierre algebraico complejo de los números racionales. En analogía con [ Adleman + Demarrais + Huang – 1997 ], si involucramos puertas que incluyan números trascendentales, podríamos elegir un conjunto mínimo de trascendentales y describir los coeficientes de la puerta esencialmente como funciones racionales . Para obtener el QFT como producto de tales compuertas, debemos hacer arreglos para que todos los componentes trascendentales se cancelen (debe ocurrir algo similar para garantizar que cada una de las compuertas sea unitaria); pero también podríamos reemplazar todos los trascendentales conQ¯{τ1,τ2,}Q¯(τ1,τ2,)0, de modo que todos los coeficientes sean algebraicos. Por lo tanto, nos restringimos a conjuntos de puertas algebraicas sin pérdida de generalidad.

Los coeficientes de una puerta finita establecida sobre pueden estar contenidos en una extensión de grado finito de , que se puede construir extendiendo por esos mismos coeficientes. Sin embargo, las puertas obviamente tienen coeficientes que pertenecen a extensiones de campo sobre de grado , es decir, de grado ilimitado. Así, la familia de QFTs de orden no se descompone en ningún conjunto de puertas finito.Q¯QQCZ2nQ2n12n

Como corolario, no podemos esperar tener ningún algoritmo en que se base en QFT sobre anillos cíclicos de tamaño ilimitado; tenga en cuenta que se produce el mismo problema para cualquier familia de circuitos que puedan usar QFT de orden arbitrario.EQP

Niel de Beaudrap
fuente