Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms

Planteamiento del Problema

El artículo aborda el desafío de computar eficientemente la Transformada de Chebyshev No Uniforme (NUCT) en una computadora cuántica. La NUCT mapea una función $f$ definida sobre nodos equiespaciados $x_k \in [-1, 1]$ a su proyección sobre los polinomios de Chebyshev $T_j(x)$.

• La Dificultad: Mientras que la Transformada de Chebyshev Discreta clásica sobre nodos de Chebyshev (que son no uniformes en $x$ pero uniformes en el ángulo $\theta = \arccos x$) se reduce a una Transformada de Fourier Discreta (DFT) estándar, la NUCT sobre nodos $x$ equiespaciados corresponde a una DFT en ángulos $\theta_k = \arccos(x_k)$ no uniformes.
• Limitaciones Previas: Los enfoques cuánticos anteriores, como la Transformada de Fourier Cuántica No Uniforme (NUQFT) de [AKY26], dependen de una factorización de bajo rango de la matriz de la transformada. Sin embargo, las cotas de error de estos métodos existentes dependen de un parámetro dependiente de la geometría $\kappa$, definido como el máximo de $1/\sqrt{1-(y^*)^2}$ donde $y^*$ es un punto intermedio en el teorema del valor medio aplicado a la función $\arccos$. Para nodos cerca de los límites de la rejilla (donde $y^* \to \pm 1$), $\kappa$ puede volverse arbitrariamente grande, destruyendo potencialmente las garantías de eficiencia del algoritmo. Además, trabajos previos a menudo asumían la existencia de "oráculos de acceso a filas" para las matrices dispersas subyacentes sin una construcción explícita.

Metodología

Los autores proponen una NUQFT libre de condicionamiento y la aplican a la NUCT a través de los siguientes pasos metodológicos:

1. Tratamiento de Punto Fijo Exacto: En lugar de tratar los valores de los nodos almacenados como aproximaciones ruidosas de números reales, el algoritmo trata las representaciones de punto fijo de $m$ bits $\tau_k$ como los nodos de entrada exactos para la transformada. La matriz de la transformada $F_\tau$ se construye a partir de estos valores exactos almacenados.
2. Descomposición del Error: El error total se divide en dos componentes independientes:
   • Error de Implementación: La diferencia entre la implementación del circuito y la transformada sobre los nodos almacenados ($F_\tau$).
   • Error de Nodo: La diferencia entre la transformada sobre los nodos almacenados ($F_\tau$) y los nodos reales objetivo ($F_t$).
3. Eliminación de $\kappa$:
   • En el análisis del error de implementación, el algoritmo computa $\arccos$ sobre el desplazamiento (offset) exacto almacenado $z_j$. Dado que la entrada al $\arccos$ es exacta, el error surge únicamente del redondeo del ángulo de salida. Esto evita que la derivada no acotada de $\arccos$ en $\pm 1$ actúe sobre un error de entrada, eliminando así la dependencia de $\kappa$.
   • El error de nodo se acota por separado analizando la sensibilidad de las fases de Fourier a las perturbaciones de los nodos, obteniendo una cota proporcional a $\|t - \tau\|_\infty$ sin singularidades geométricas.
4. Factorización de Bajo Rango y LCU: La matriz NUCT se reduce al promedio de dos NUDFTs de Tipo II. Cada NUDFT se aproxima mediante una expansión de Chebyshev-Bessel de bajo rango (rango $K$). Los autores implementan esto utilizando una Combinación Lineal de Unidades (LCU) con un estado exterior ponderado, lo que mejora el factor de normalización en comparación con los enfoques de LCU uniformes.
5. Construcción Explícita de Oráculos: El artículo proporciona circuitos cuánticos explícitos para:
   • Oráculo de Nodo ($O_\tau$): Computa aproximaciones de $m$ bits de $\arccos(x_k)$ de forma reversible.
   • Oráculo de Acceso a Filas ($O_r$): Explota la estructura específica de los nodos de NUCT (donde como máximo 5 nodos mapean al mismo punto de la rejilla e los índices son consecutivos) para proporcionar acceso a filas dispersas sin tablas de búsqueda.
   • Preparación de Coeficientes: Construye los coeficientes de la función Bessel clásicamente y los carga en estados cuánticos, demostrando que estos son independientes de la instancia.

Contribuciones Clave

1. NUQFT Libre de Condicionamiento: La principal contribución teórica es un algoritmo NUQFT modificado (Teorema 4.7) donde las cotas de error y los requisitos de recursos son independientes del parámetro geométrico $\kappa$. El error depende solo del número de bits por nodo ($m$), la precisión objetivo ($\epsilon$) y la dispersión de filas ($d_r$).
2. Normalización Mejorada: Al utilizar un LCU exterior ponderado y cotas más ajustadas para el peso total de Bessel ($\Lambda < 24$), los autores logran una normalización de codificación de bloque de $O(\sqrt{d_r})$. Para la NUCT, donde $d_r \le 5$, esto resulta en una normalización $O(1)$, una mejora significativa respecto a la escala $O(K^2\sqrt{d_r})$ u $O(K\sqrt{d_r})$ de métodos anteriores.
3. Construcciones de Oráculos Explícitos: El artículo elimina la suposición de oráculos preexistentes al proporcionar circuitos cuánticos explícitos y eficientes para la generación de nodos y el acceso a filas, diseñados específicamente para el entorno de Chebyshev equiespaciado.
4. Algoritmo NUCT de Extremo a Extremo: Los autores presentan un circuito cuántico completo (Algoritmo 2) para la NUCT, incluyendo un análisis riguroso de complejidad que cubre el conteo de cúbits, la profundidad de compuertas y la probabilidad de éxito.

Resultados

El artículo establece los siguientes resultados de complejidad para la NUCT con $N=2^q$ nodos y precisión objetivo $\epsilon$:

• Complejidad de Cúbits: $O(L)$ cúbits, donde $L = q + \log(1/\epsilon)$.
• Complejidad de Compuertas: $\tilde{O}(L^2)$ compuertas lógicas (aritmética reversible, Clifford, Toffoli, rotaciones controladas). Cuando se sintetiza en compuertas Clifford+T, la complejidad es $\tilde{O}(L^3)$.
• Normalización: $O(1)$ (específicamente acotada por $24\sqrt{5}$).
• Precisión: El algoritmo produce una codificación de bloque $\epsilon$-precisa de la matriz NUCT.
• Estado de Salida: Dado un estado de entrada $|f\rangle$, el algoritmo prepara un estado que aproxima la salida normalizada $C_N|f\rangle / \|C_N|f\rangle\|$ con un error de $O(\epsilon / (r-\epsilon))$, donde $r = \|C_N|f\rangle\|$. El número de rondas de amplificación de amplitud requeridas es $O(1/(r-\epsilon))$.

Significancia y Reivindicaciones

Los autores afirman que este trabajo proporciona el primer algoritmo cuántico eficiente y libre de condicionamiento para la transformada de Chebyshev no uniforme en nodos equiespaciados.

• Aceleración Exponencial: El algoritmo clásico para esta transformada (por Driscoll, Healy y Rockmore [DHR97]) requiere $O(N \log^2 N)$ operaciones. El algoritmo cuántico propuesto es polilogarítmico en $N$ ($\tilde{O}(\log^2 N)$), ofreciendo una aceleración exponencial para la transformada en sí.
• Base para Transformadas Generales: Los autores posicionan la NUCT como un bloque de construcción crítico para implementar el flujo completo de [DHR97], que computa transformadas de polinomios discretos para familias generales de polinomios ortogonales utilizando un enfoque de divide y vencerás basado en recurrencias de tres términos.
• Robustez: Al eliminar la dependencia de $\kappa$, el algoritmo es robusto para cualquier distribución de nodos, incluyendo aquellos donde los nodos están arbitrariamente cerca de los límites de la rejilla, un escenario donde los métodos anteriores fallarían o requerirían supuestos no probados sobre la colocación de los nodos.

El artículo concluye señalando que, si bien la transformada en sí es exponencialmente más rápida, la aceleración de extremo a extremo para aplicaciones prácticas depende del costo de la preparación del estado de entrada, la norma de la salida y el número de coeficientes de salida requeridos. El trabajo futuro pretende extender estas técnicas a familias generales de polinomios ortogonales.