The power of constant-depth quantum circuits of unbounded size

Resumen Técnico: El Poder de los Circuitos Cuánticos de Profundidad Constante de Tamaño No Acotado

Planteamiento del Problema
El artículo investiga el poder computacional de los circuitos cuánticos cuando se eliminan las restricciones sobre el tamaño del circuito y el espacio ancilar. En la complejidad clásica, la clase $AC^0$ (circuitos de profundidad constante con puertas AND/OR de entrada no acotada) no puede computar la paridad. Sin embargo, si se levanta la restricción de tamaño polinómico, cada función booleana puede ser computada en profundidad constante mediante construcciones de Forma Normal Disyuntiva (DNF). Los autores plantean esta indagación a través de cuatro tareas cada vez más generales:

1. Computar la membresía en cualquier conjunto $L \subseteq \{0, 1\}^n$.
2. Implementar cualquier permutación de los estados de la base computacional.
3. Preparar cualquier estado puro.
4. Implementar cualquier unitaria arbitraria en cada estado de entrada.

Metodología
Los autores emplean una combinación de construcciones de circuitos clásicos reversibles, técnicas clásicas probabilísticas adaptadas al dominio cuántico y protocolos de teletransportación cuántica.

• Construcciones Clásicas Reversibles: Los autores establecen primero que las permutaciones arbitrarias de cadenas de bits pueden implementarse en profundidad constante utilizando puertas Toffoli y fanout. Esto se logra mediante un esquema de "codificación de indicador": la entrada se mapea a un vector indicador de dimensión $2^n$ (donde exactamente una entrada es 1), se manipula, y luego se decodifica de vuelta a la cadena original. Esto permite la evaluación paralela de todas las posibles cadenas de entrada.
• Adaptación Probabilística a lo Cuántico: Para preparar distribuciones de probabilidad y estados puros arbitrarios, los autores adaptan una construcción clásica probabilística. Esto implica muestrear bits de forma independiente para codificar una distribución basada en la posición del primer '1'. En el entorno cuántico, esto se hace coherente aplicando rotaciones inversas a los qubits que siguen al primer '1' para devolverlos a $|0\rangle$ sin destruir la superposición.
• Extensiones del Conjunto de Puertas: Aunque el conjunto de puertas principal incluye puertas de un solo qubit y puertas Toffoli generalizadas, los autores utilizan puertas fanout como una herramienta conceptual. Citan resultados de Grier, Morris y Wu [GMW26] y Rosenthal [Ros20] para mostrar que el fanout puede implementarse exactamente en profundidad constante usando solo el conjunto de puertas primario, aunque con un posible aumento del tamaño del circuito a límites doblemente exponenciales.
• Reducciones para Unitarias: Para la implementación de unitarias arbitrarias, los autores no proporcionan una construcción directa. En su lugar, ofrecen varias formulaciones equivalentes y reducciones. Estas incluyen reducir la implementación de una unitaria a:
  • Clonar vectores de una base ortonormal especificada.
  • Permutar listas de vectores de la base.
  • Decodificar etiquetas de la base.
  • Implementar unitarias con sumas de fila y columna unitarias (vía la forma normal de Idel-Wolf).
  • Implementar involuciones unitarias sin traza (usando un qubit limpio adicional).
• Teletransportación Basada en Puertos (PBT): Para acercarse a la implementación de unitarias arbitrarias sin correcciones unitarias dependientes de la puerta específica, los autores utilizan la Teletransportación Basada en Puertos (PBT). Construyen un circuito unitario que realiza PBT utilizando estados máximamente entrelazados (o estados de Choi de la unitaria objetivo) y una medición conjunta, seguido de la selección de puertos.

Contribuciones Clave y Resultados

1. Construcciones de Profundidad Constante Exactas para Tareas Específicas:

   • Permutaciones: Arbitrarias permutaciones de cadenas de bits pueden implementarse en profundidad constante (profundidad $\le 20$) usando $O(n2^n)$ puertas y qubits ancilares.
   • Unitarias Diagonales: Arbitrarias unitarias diagonales pueden implementarse en profundidad constante (profundidad 7) computando indicadores, aplicando fases en paralelo y descomputando.
   • Preparación de Estados: Arbitrarios estados puros pueden prepararse en profundidad constante (profundidad $\le 37$) usando $O(4^n)$ qubits y $O(n2^n)$ puertas. Todos los qubits ancilares son devueltos a cero.
   • Implementación de Fanout: El fanout puede implementarse exactamente en profundidad constante usando solo puertas de un solo qubit y puertas Toffoli generalizadas, aunque esto puede requerir un tamaño doblemente exponencial.

2. Reducciones para Unitarias Arbitrarias:
   El artículo demuestra que implementar unitarias arbitrarias en profundidad constante es equivalente a implementar cualquiera de varias operaciones específicas (por ejemplo, clonar vectores de la base, decodificar etiquetas o implementar involuciones sin traza). Esto replantea el problema abierto de la implementación de unitarias arbitrarias como un conjunto de desafíos estructurales equivalentes.

3. Mediciones Adaptativas y Teletransportación de Puertas:
   Los autores muestran que si se permiten mediciones intermedias adaptativas, cualquier puerta en el nivel $\ell$ de la jerarquía de Clifford puede implementarse con una profundidad de $O(\ell)$. Además, la implementación de una unitaria arbitraria se reduce a implementar involuciones unitarias sin traza en este modelo adaptativo.

4. Aproximación de Teletransportación Basada en Puertos (PBT):
   Los autores construyen un circuito unitario para la Teletransportación Basada en Puertos (PBT) para una dimensión de entrada $d$ y $M \ge d^2 - 1$ puertos.

   • Profundidad: La profundidad del circuito es $O(\sqrt{d})$, la cual es independiente del número de puertos $M$.
   • Fidelidad: La fidelidad de entrelazamiento está acotada por $F_e \ge (1 - \frac{d^2-1}{2M})^2$.
   • Precisión vs. Profundidad: Para cualquier dimensión de entrada $d$ fija, la aproximación puede hacerse arbitrariamente precisa aumentando $M$ sin aumentar la profundidad del circuito. Sin embargo, la dependencia de la dimensión de entrada $d$ permanece; si se puede lograr un límite de profundidad independiente de $d$ sigue siendo una pregunta abierta.
   • Implementación: El circuito utiliza únicamente puertas de un solo qubit y puertas Toffoli generalizadas, y no requiere mediciones intermedias.

Significado y Afirmaciones
El artículo establece que eliminar las restricciones de tamaño y espacio ancilar permite que los circuitos cuánticos de profundidad constante realicen tareas que son generalmente imposibles en modelos de tamaño polinómico de profundidad constante, tales como la preparación de estados arbitrarios y la permutación de estados de la base. Esto conecta la preparación de estados cuánticos directamente con la computación clásica reversible y la preparación de distribuciones de probabilidad.

No obstante, el artículo mantiene una postura modesta respecto a la implementación de unitarias arbitrarias. Si bien proporciona construcciones exactas de profundidad constante para permutaciones, unitarias diagonales y preparación de estados, la implementación de unitarias generales sigue siendo un problema abierto. Los autores ofrecen caracterizaciones equivalentes de este problema pero no lo resuelven.

La contribución principal respecto a las unitarias generales es la construcción de PBT. Los autores demuestran que, para cualquier dimensión de entrada fija, las unitarias arbitrarias pueden aproximarse con una precisión arbitraria sin aumentar la profundidad del circuito al incrementar el número de puertos. Sin embargo, la profundidad de esta construcción escala como $O(\sqrt{d})$ con la dimensión de entrada $d$. Los autores declaran explícitamente que si esta dependencia de $d$ puede eliminarse (es decir, lograr un límite de profundidad independiente de $d$) sigue siendo una pregunta abierta. El trabajo destaca que la dificultad fundamental en la implementación de unitarias en profundidad constante no radica en producir una salida arbitraria a partir de una entrada fija, sino en prescribir la acción sobre cada estado de entrada simultáneamente preservando la unitariedad.