Es PARITY en QAC_0 (si eso tiene sentido)

17

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?

Bill GASARCH
fuente
2
Esto parece relevante: eccc.uni-trier.de/eccc-reports/1999/TR99-032
Ross Snider

Respuestas:

20

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.

Robin Kothari
fuente
¿Tiene una cita que muestra que ? TC0 0QUNCC0 0
Samuel Schlesinger el
@SamuelSchlesinger: Este documento muestra que puede calcular el umbral, la paridad, la mayoría, etc. con solo puertas de fanout y puertas de 2 qubits: theoryofcomputing.org/articles/v001a005
Robin Kothari