Como es bien sabido, PARITY no se puede hacer en circuitos de profundidad constante de tamaño polivinílico, y de hecho, los circuitos const-dept requieren un número EXP de compuertas.
¿Qué pasa con los circuitos QUANTUM?
a) ¿Se puede hacer PARITY con un circuito cuántico que tiene una profundidad constante y un número polivinílico de puertas?
b) ¿Tiene sentido mi pregunta?
cc.complexity-theory
quantum-computing
circuit-complexity
Bill GASARCH
fuente
fuente
Respuestas:
La pregunta tiene sentido, y la respuesta corta es que es un problema abierto.
Aquí está la respuesta larga: dependiendo de cómo defina circuitos cuánticos de profundidad constante sin límites, puede obtener diferentes clases. QAC 0 generalmente se define para tener puertas Toffoli de fanin ilimitadas y puertas de un solo qubit. QAC 0 wf es la clase donde también permitimos una puerta "fanout", que copia un bit de entrada a muchas salidas. (Implementa | a> | 0> ... | 0> -> | a> | a> ... | a>) Esta clase es realmente poderosa ya que contiene, además de PARITY y AC 0 , también ACC 0 y TC 0 .
Entonces, la pregunta obvia es si PARITY está contenido en QAC 0 , y este es un problema abierto. Es equivalente a preguntar si QAC 0 = QAC 0 wf . Supongo que la creencia es que PARITY no está en QAC 0 . Se puede encontrar más información en el estudio Circuitos cuánticos de pequeña profundidad de Bera, Green y Homer.
fuente
Sorprendentemente, el número de qubits de trabajo extra (ancilla) es importante. En este momento se sabe que PARITY no está en QAC_0 con anclas limitadas. Los límites inferiores cuánticos para la distribución en abanico dan una prueba para los circuitos que usan como máximo linealmente muchos anclas y doi: 10.1016 / j.ipl.2011.05.002 da otra prueba para los circuitos que no usan anclas.
fuente