A log-depth in-place quantum Fourier transform that rarely needs ancillas

Resumen Técnico: Una Transformada de Fourier Cuántica In-Situ de Profundidad Logarítmica que Raramente Necesita Ancillas

Planteamiento del Problema
El diseño de circuitos cuánticos para unitarias específicas a menudo requiere equilibrar las restricciones de recursos (profundidad, número de cúbits, localidad) frente al error de aproximación. Los enfoques tradicionales exigen que un circuito aproxime una unitaria con un error bajo para todos los estados de entrada posibles. Sin embargo, lograr esta garantía de "peor caso" a menudo requiere recursos significativos, como un gran número de cúbits ancilla, compuertas de largo alcance o circuitos profundos. Por ejemplo, las construcciones previas de la Transformada de Fourier Cuántica (QFT) de profundidad logarítmica requerían $O(n)$ cúbits ancilla, conectividad de largo alcance o alimentación directa (feedforward) basada en mediciones. Los autores postulan que, para muchas aplicaciones dentro de algoritmos cuánticos más grandes, es suficiente lograr una buena aproximación en la mayoría de los inputs, en lugar de en todos, siempre que los inputs "malos" (donde el error es alto) sean raros o puedan gestionarse mediante una reducción.

Metodología
El artículo introduce un marco para "circuitos cuánticos optimistas" y lo aplica a la QFT, seguido de una técnica de reducción para manejar los inputs del peor caso.

1. Circuitos Cuánticos Optimistas:
   Los autores definen un circuito cuántico optimista $C$ (que induce la unitaria $\tilde{U}$) para una unitaria objetivo $U$ como uno donde el error cuadrático promedio sobre cualquier base ortonormal está acotado por $\epsilon$. Formalmente, $\frac{1}{\dim \mathcal{H}} \sum_i \|\tilde{U}|\phi_i\rangle - U|\phi_i\rangle\|^2 < \epsilon$. Esta definición es independiente de la base y equivalente a acotar la norma de Frobenius del operador de error. Crucialmente, esto permite un pequeño subespacio de inputs "malos" donde el error es $O(1)$, siempre que este subespacio ocupe solo una fracción $O(\epsilon)$ del espacio de Hilbert.

2. Construcción de la QFT Optimista:
   Los autores construyen una $\widetilde{\text{QFT}}$ optimista para $n$ cúbits con un parámetro de error $\epsilon$.

• Enfoque por bloques: El registro de entrada se divide en bloques de tamaño $m = O(\log(n/\epsilon))$.
• Truco de Estimación de Fase: El circuito aprovecha el hecho de que aplicar una QFT inversa a un bloque aproxima una estimación de fase del factor de fase. Al aplicar $\text{QFT}^\dagger$ a un bloque, el circuito estima la contribución de fase de los bloques vecinos.
• Conmutación: La construcción inserta identidades de la forma $\text{QFT}^\dagger \text{QFT}$ y mueve los bloques que conmutan entre sí. Esto rompe la cadena de dependencia lineal de las QFT aproximadas estándar.
• Modo de Fallo: La estimación de fase falla (al dar la vuelta módulo $2^m$) solo cuando el estado de entrada en un bloque está cerca de $0$o$2^m$ (es decir, una cadena larga de 0s o 1s). Estos constituyen el subespacio "malo".
• Recursos: El circuito resultante tiene una profundidad de $O(\log(n/\epsilon))$, utiliza exactamente $n$ cúbits (sin ancillas), es local para arreglos de cúbits 1D (con rango $O(\log(n/\epsilon))$) y no requiere mediciones.

3. Reducción de Peor Caso a Promedio:
   Para abordar los escenarios donde los inputs podrían concentrarse en el subespacio "malo", los autores proponen una reducción para transformar circuitos optimistas en circuitos aproximados generales.

• Reducción Aleatorizada: Antes de aplicar el circuito optimista, se aplica una unitaria aleatoria $V$ de un 1-diseño unitario. Después, se aplica $\hat{V}^\dagger = U V^\dagger U^\dagger$. Esto aleatoriza el estado de entrada, asegurando que la probabilidad de caer en el subespacio de alto error sea baja.
• Reducción Desaleatorizada: El proceso aleatorizado puede purificarse en una operación unitaria codificando la elección de $V$ en un registro de control.
• 1-Diseño Específico: Para la QFT, los autores utilizan el grupo de Weyl-Heisenberg (muestreo uniforme de desplazamientos tipo Pauli y gradientes de fase) como el 1-diseño. Esta elección asegura que las operaciones de aleatorización y desaleatorización requeridas sean eficientes.

Contribuciones Clave y Resultados

• QFT Optimista: El artículo presenta la primera construcción de QFT que logra simultáneamente:
  • Profundidad: $O(\log(n/\epsilon))$.
  • Número de Cúbits: $n$ (sin ancillas).
  • Localidad: Rango $O(\log(n/\epsilon))$ (local para 1D).
  • Sin mediciones.
  • Error: Acotado por $\epsilon$ en todos los estados excepto en una fracción $O(\epsilon)$ del espacio de Hilbert.
• Multiplicación y Factorización Optimista: Los autores demuestran que la QFT optimista puede usarse directamente en el algoritmo de Shor para la factorización de enteros. Al integrar la QFT optimista en las recientes construcciones de aritmética rápida basadas en QFT (específicamente un multiplicador optimista), logran circuitos de factorización con profundidad $O(n^{1+\delta})$ (para un $\delta > 0$ ajustable) utilizando solo $2n + O(n/\log n)$ cúbits totales. Esto representa una mejora significativa en profundidad y eficiencia de cúbits comparado con métodos previos que requerían $O(n)$ ancillas o circuitos más profundos.
• QFT Aproximada General: Al aplicar la técnica de reducción, los autores derivan una QFT aproximada que funciona con bajo error en arbitrarios inputs.
  • Versión Aleatorizada: Logra una profundidad $O(\log(n/\epsilon))$ usando $n + O(n/\log(n/\epsilon))$ cúbits totales (ancillas sublineales).
  • Versión Desaleatorizada (Unitaria): Logra una profundidad $O(\log(n/\epsilon))$ usando $3n + O(n/\log(n/\epsilon))$ cúbits totales.
    Estas son alegadas como las primeras construcciones que logran una profundidad logarítmica asintóticamente óptima con conteos de ancillas sublineales (aleatorizada) o sin mediciones/alimentación directa (desaleatorizada).

Significancia
El artículo sostiene que los "circuitos cuánticos optimistas" ofrecen un cambio de paradigma práctico para el diseño de algoritmos cuánticos. Al aceptar modos de fallo raros que son estadísticamente improbables de ocurrir en contextos algorítmicos típicos (como el algoritmo de Shor), se pueden reducir drásticamente las sobrecargas de recursos (profundidad y conteo de ancillas). La construcción específica de la QFT optimista elimina el cuello de botella de las QFT en circuitos de factorización, permitiendo la factorización de profundidad casi lineal con un overhead de cúbits mínimo. Además, la técnica de reducción proporcionada ofrece un método general para convertir tales circuitos optimistas en garantías robustas de peor caso cuando sea necesario, cerrando la breancia entre la eficiencia heurística y la corrección rigurosa. El trabajo sugiere que, a medida que el hardware cuántico madure, el compromiso entre el volumen de espacio-tiempo y la profundidad será crítico, y estas construcciones proporcionan un camino para optimizar ambos.