¿Qué tan poderosa es la computación "cuántica" exacta si suspendes la unitaridad?

15

Pregunta corta

¿Cuál es el poder computacional de los circuitos "cuánticos", si permitimos puertas no unitarias (pero aún invertibles), y requerimos que la salida dé la respuesta correcta con certeza?

Esta pregunta es, en cierto sentido, sobre lo que le sucede a la clase cuando permite que los circuitos usen más que puertas unitarias. (Todavía nos vemos obligados a restringirnos a puertas invertibles sobre si queremos poder tener un modelo de cómputo bien definido).CEQPC

(Esta pregunta ha sufrido algunas revisiones a la luz de cierta confusión de mi parte sobre los resultados conocidos sobre tales circuitos en el caso unitario).

Sobre el cálculo cuántico "exacto"

Defino por el bien de esta cuestión a ser la clase de problemas que se pueden resolver con exactitud por una familia de circuitos uniforme cuántica, donde los coeficientes de cada unitaria es computable por máquinas de Turing delimitadas-tiempo polinomio (de la cadena de entrada ) para cada tamaño de entrada , y que el diseño del circuito como una red dirigida también se puede producir en tiempo polinómico. Por "exactamente" resuelto, quiero decir que medir el bit de salida produce con certeza para NO instancias, y con certeza para instancias YES.1 n n | 0 | 1 miQPAG1nortenorteEl |0 0El |1

Advertencias:

  • Incluso restringiéndose a puertas unitarias, esta noción de es diferente de la descrita por Bernstein y Vazirani usando máquinas cuánticas de Turing. La definición anterior permite que una familia de circuitos tenga, en principio, un conjunto de puertas infinito , por supuesto, cada circuito individual solo usa un subconjunto finito porque las puertas se calculan en efecto a partir de las entradas. (Una máquina cuántica de Turing puede simular cualquier conjunto de puertas finitas que desee, pero solo puede simular conjuntos de puertas finitas, ya que solo tiene un número finito de transiciones). { C n } C nmiQPAG{Cnorte}Cnorte

  • Este modelo de cálculo trivializa cualquier problema en , porque el unitario podría contener una única puerta que codifica la solución a cualquier problema en (después de todo, sus coeficientes están determinados por un cómputo poli-tiempo). Por lo tanto, la complejidad específica de tiempo o espacio de los problemas no es necesariamente interesante para tales circuitos.PPAGPAG

Podemos agregar a estas advertencias la observación de que las implementaciones prácticas de las computadoras cuánticas tendrán ruido de todos modos. Este modelo de computación es interesante principalmente por razones teóricas , ya que uno se preocupa por componer transformaciones unitarias en lugar de computación factible, y también como una versión exacta de . En particular, a pesar de las advertencias anteriores, tenemos .PE Q PB Q PsiQPAGPAGmiQPAGsiQPAG

La razón para definir en la forma en que lo hago es para que DISCRETE-LOG se pueda poner en . Por [  Mosca + Zalka 2003  ], existe un algoritmo de tiempo polinómico para construir un circuito unitario que resuelve exactamente instancias de DISCRETE-LOG produciendo versiones exactas de QFT dependiendo del módulo de entrada. Creo que luego podemos poner DISCRETE-LOG en , como se definió anteriormente, integrando los elementos de construcción de circuitos en la forma en que se calculan los coeficientes de la puerta. (Entonces, el resultado DISCRETE-LOG esencialmente se mantiene por fiat, pero se basa en la construcción de Mosca + Zalka).E Q P E Q PE Q PmiQPAGmiQPAGmiQPAGmiQPAG

Suspender la unitaridad

Deje que sea ​​la clase computacional que obtenemos si suspendemos la restricción de que las compuertas sean unitarias, y permita que se extiendan sobre transformaciones invertibles. ¿Podemos colocar esta clase (o incluso caracterizarla) en términos de otras clases no deterministas tradicionales ? CmiQPAGsolLC

Una de mis razones para preguntar: si es la clase de problemas que se puede resolver de manera eficiente con error acotado , por familias de circuitos uniformes "cuánticos no unitarios", donde las instancias SÍ dan una salida de con probabilidad al menos 2/3, y NO instancias con probabilidad como máximo 1/3 (después de normalizar el vector de estado) - luego [Aaronson 2005] muestra que . Es decir: suspender la unitaridad es en este caso equivalente a permitir un error ilimitado. | 1 B Q P G L = P PsiQPAGsolLEl |1siQPAGsolL=PAGPAG

¿Se obtiene un resultado similar o un resultado claro para ?miQPAGsolL

Niel de Beaudrap
fuente
2
Intuitivamente, supongo que es . C o C = PCCoC=PAG
Tayfun Pay
No es una mala suposición, ya que es la versión de error ilimitada (unilateral) de así como es la versión de error ilimitada de ; y contiene tanto como su complemento, debido a que está cerrado bajo intersección y complementos. E Q P P P B Q P P P C = P P PCoC=PAG=norteQPAGmiQPAGPAGPAGsiQPAGPAGPAGC=PAGPAGPAG
Niel de Beaudrap
¿Es obvio que NP está contenido en esta clase? (¿Y esta clase es la misma que EQP con postselección?)
Robin Kothari
2
@RobinKothari: No consideraría ninguno de estos obvios, debido a la condición de error cero. La segunda pregunta parece más probable que la primera. acuerdo con Tayfun en que (... y, por lo tanto, también ) es una conjetura razonable de que si se va a definir previamente clase en absoluto, ese es un sospechoso principal, pero obviamente si fuera cierto no sería una observación trivial. C = PmiQPAGsolL=CoC=PAGC=PAG
Niel de Beaudrap 01 de
¿Conoces algún problema en esta clase que no esté en P?
Robin Kothari

Respuestas:

6

Respuesta corta. Resulta que suspender el requisito de transformaciones unitarias, y requerir que cada operación sea invertible, da lugar a clases exactas definibles por huecos. Las clases específicas en cuestión son y una 'nueva' subclase L P W P P , ambos de los cuales se sienta entre S P P y C = P . Estas clases tienen definiciones bastante técnicas, que se describen brevemente a continuación; aunque estas definiciones ahora pueden sustituirse, en principio, por otras en términos de algoritmos no unitarios "de tipo cuántico".LWPAGPAGLPAGWPAGPAGSPAGPAGC=PAG

La clase de conteo contiene ISOMORFISMO GRÁFICO. También contiene toda la clase U P , por lo que no esperaríamos que los algoritmos cuánticos unitarios exactos sean tan poderosos como las clases no unitarias (como podríamos mostrar N P B Q P ).SPAGPAGUPAGNPBQPAG

Respuesta larga

  • En mi pregunta, propuse redefinir para permitir problemas que pueden resolverse mediante familias de circuitos uniformes que usan puertas que son computables de manera eficiente, pero no necesariamente extraídas de un conjunto de puertas finito. Ya no estoy tan seguro de que sea una buena idea redefinir E Q P de esta manera, aunque creo que vale la pena estudiar esas familias de circuitos. Podemos llamar a esta clase algo así como U n i t a r y P C en su lugar.EQPAG EQPAGUnorteyotunryPAGC

    Es posible demostrar que , que hasta hace poco era el más conocido con destino a E Q P . La clase L W P P corresponde más o menos a problemas para los cuales existe un algoritmo aleatorio, donde las instancias NO producen un resultado de 1 con probabilidad exactamente 0.5, y las instancias SÍ producen un resultado de 1 con alguna probabilidad que puede ser eficiente y exactamente calculado en forma racional, que es mayor que (pero posiblemente exponencialmente cercano a) 0.5. La definición técnica de L W PUnorteyotunryPAGCLWPAGPAGmiQPAGLWPAGPAG se presenta en términos de máquinas de Turing no deterministas, pero ya no es más esclarecedor.LWPAGPAG

    Si definimos como el equivalente de puerta invertible de U n i t a r y P C , de modo que es el conjunto de problemas que pueden resolverse exactamente por familias de circuitos invertibles con coeficientes de puerta computables de manera eficiente, entonces G L P C = L W P P .solLPAGCUnorteyotunryPAGCsolLPAGC=LWPAGPAG

  • Si nos limitamos a finitas gate-conjuntos, es posible demostrar que las familias unitarios de circuito pueden ser simulados en un subconjunto de , que podríamos llamar L P W P P . (Usando la descripción de L W P P anterior, esto corresponde a algoritmos aleatorios donde la probabilidad de obtener una salida de 1 para las instancias SÍ es exactamente m t ( x ) / 2 p ( | x | ) , para algunos polinomios p , algunos entero mLWPAGPAGLPAGWPAGPAGLWPAGPAGmetrot(X)/ /2pag(El |XEl |)pagmetroy algunos polinomios eficientemente computables .)t

    Si definimos para ser el invertible-gate equivalente de E Q P como se define normalmente, podemos mostrar que E Q P G LL P W P P .miQPAGsolLmiQPAGmiQPAGsolLLPAGWPAGPAG

Una corrección con respecto al REGISTRO DISCRETO.

Los resultados anteriores se basan en técnicas estándar para representar los coeficientes algebraicos, de forma independiente de la entrada (pero que puede depender del tamaño de la entrada). En la descripción de la pregunta original, afirmé que [ Mosca + Zalka 2003 ] muestran que DISCRETE LOG es exactamente solucionable mediante un conjunto de puertas con coeficientes computables de manera eficiente. La verdad parece ser más complicada. Si a uno le importa la solubilidad exacta, entonces considero que la representación exacta de los coeficientes es importante: pero Mosca y Zalka no proporcionan una forma de hacerlo de una manera dependiente de la entrada. Por lo tanto, no es obvio que DISCRETE LOG esté de hecho en o en la nueva clase U n i t a r y PmiQPAG .UnorteyotunryPAGC

Referencia.

  • de Beaudrap, Sobre conteo exacto y complejidad cuasi cuántica , [ arXiv: 1509.07789 ].
Niel de Beaudrap
fuente
¡¡¡Muy agradable!!! Una pregunta ingenua: ¿cuál es el poder de los circuitos que describió (invertible arbitrario; exacto o aproximado) cuando considera la complejidad de la muestra. (A saber, la clase de distribuciones de probabilidad que pueden dar.)
Gil Kalai
@GilKalai: Si no impone ninguna invariante en las distribuciones que estos circuitos calculan (es decir, haciendo que conserven la norma 1 o la norma 2), entonces uno tendría que definir con precisión cómo desea mapear los tensores que dichos circuitos describen a las distribuciones de probabilidad. Si uno se imagina que estas distribuciones son de alguna manera estados cuánticos en secreto en lugar de distribuciones de pseudo-probabilidad, uno podría volver a formalizar de la manera habitual que un físico podría elegir hacer, pero esta elección no se nos impone.
Niel de Beaudrap
Dicho esto: sea cual sea la restricción que uno impone, no sé de inmediato cómo respondería la pregunta. Pero por el trabajo de Aaronson en PostBQP , sabemos que la clase de muestreo aproximada es al menos PP- dura.
Niel de Beaudrap