Distribuciones de probabilidad de profundidad limitada

Dos preguntas relacionadas sobre la computación de profundidad limitada:

1) Suponga que comienza con n bits, y para comenzar con el bit i puede ser 0 o 1 con alguna probabilidad p (i), independientemente. (Si simplifica el problema, podemos suponer que todos los p (i) s son 0,1 o 1/2.o incluso que todos ellos son 1/2.)

Ahora realiza una ronda limitada de cómputo. En cada ronda aplicas puertas clásicas reversibles en conjuntos de bits disjuntos. (Arregle su conjunto favorito de puertas reversibles clásicas universales).

Al final obtienes una distribución de probabilidad en cadenas de n bits. ¿Hay resultados sobre la restricción de tales distribuciones?

Estoy buscando algo análogo al cambio de Leme de Hastad, el resultado de Boppana es que la influencia total es pequeña o el teorema de LMN.

2) La misma pregunta que 1) pero con circuitos cuánticos de profundidad acotada.

Hay algunos documentos relativamente recientes de Emanuele Viola et al., Que tratan sobre la complejidad de las distribuciones de muestreo. Se centran en el modelo restringido de cálculos, como los árboles de decisión de profundidad limitada o los circuitos de profundidad limitada.

Lamentablemente no discuten las puertas reversibles. Por el contrario, a menudo hay pérdida en la longitud de salida. Sin embargo, estos documentos pueden ser un buen punto de partida.

Los circuitos de profundidad limitada no pueden probar buenos códigos

La complejidad de las distribuciones

Respuesta corta.

Para los circuitos cuánticos, hay al menos un resultado no limitativo: es poco probable que los circuitos cuánticos arbitrarios de profundidad limitada sean simulables con un pequeño error multiplicativo en la probabilidad del resultado, incluso para circuitos clásicos de profundidad polinómica .

Esto, por supuesto, no te dice qué circuitos de resctricciones realmente tendrán; particularmente si está interesado en problemas de decisión con error acotado, en lugar de distribuciones de probabilidad. Sin embargo, significa que un análisis en términos de árboles de decisión, como con el Lema de conmutación de Håstad , no es probable que esté en perspectiva para la simulación clásica de estos circuitos.$\mathsf{QNC^0}$

Detalles

Podemos considerar la definición de circuitos cuánticos de profundidad de polylog dada por Fenner et al. (2005) :

Definición. es la clase de familias de circuitos cuánticos para las cuales existe un polinomio para el cual cada contiene qubits de entrada y como máximo ancillas frescas, utiliza solo compuertas de un solo qubit y compuertas no controladas, y tiene una profundidad .$\mathsf{QNC^k}$ p C n n p ( n ) O ( log k ( n ) $\{C_n\}_{n\geqslant0}$$p$$C_n$$n$$p(n)$$O(\log^k(n))$

Las puertas de un solo qubit deben ser de un conjunto finito fijo, aunque esto es suficiente para simular cualquier unidad unitaria fija en un número constante de qubits con una precisión fija. También permitimos que cualquier subconjunto de qubits en el final del circuito se use para representar la salida de la familia de circuitos (por ejemplo, un solo qubit para funciones booleanas).

Bremner, Jozsa y Sheppard (2010) señalan (ver Sección 4) que, utilizando una adaptación de la técnica de teletransportación de puerta debido a Terhal y DiVincenzo (2004) , la selección posterior en algunos de los qubits en un circuito permite decidir problemas en . Al usar sus resultados al simular circuitos postseleccionados, esto implica que el problema del muestreo clásico de la distribución de salida de un circuito arbitrario con salida booleana, con un error multiplicativo como máximo en la probabilidad de muestreo, está en imposible con circuitos aleatorios de profundidad polinómica a menos que la jerarquía polinómica se colapse parcialmente (específicamente P o s t B Q P = P P Q N C 0 $\mathsf{QNC^0}$$\mathsf{PostBQP = PP}$$\mathsf{QNC^0}$ PH⊆Δ$\sqrt 2$$\mathsf{PH} \subseteq \Delta_3$ ).