⚛️ física cuántica

Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

Este artículo presenta construcciones de circuitos cuánticos mejoradas tanto para la Transformada de Fourier Cuántica exacta como para la aproximada que reducen la complejidad de compuertas de $O(q (\log q)^{\alpha+1})$ y $O(q (\log \log(q/\varepsilon))^{\alpha+1})$ a $O(q (\log q)^{\alpha})$ y $O(q (\log \log(q/\varepsilon))^{\alpha})$ , respectivamente, mediante el aprovechamiento de avances en algoritmos de multiplicación de enteros.

Autor original: Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

Publicado 2026-11-05

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autor original: Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por el autor. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el ámbito de la computación cuántica, las máquinas no procesan la información de la forma simple y lineal de las computadoras portátiles y los teléfonos inteligentes que usamos cada día. En su lugar, manipulan estados delicados de la materia que pueden existir en muchas configuraciones simultáneamente. Para lograr que estas máquinas resuelvan problemas complejos, los científicos confían en una operación matemática específica llamada transformada de Fourier cuántica. Piense en esta operación como una lente poderosa que toma una mezcla desordenada de posibilidades y las clasifica en un patrón claro, revelando estructuras ocultas dentro de los datos. Este proceso de clasificación es el motor detrás de algunos de los algoritmos cuánticos más famosos, incluidos los diseñados para romper los códigos de encriptación modernos o simular reacciones químicas. Durante décadas, la forma estándar de construir esta lente en un circuito cuántico requirió un número de componentes físicos que crecía muy rápidamente a medida que aumentaba el tamaño del problema, lo que dificultaba la realización de aplicaciones a gran escala.

Un equipo de investigadores ha propuesto ahora una forma de construir esta lente esencial de manera mucho más eficiente. Al repensar cómo se construye la operación, han demostrado que el número de componentes físicos necesarios puede reducirse significلmente, siempre que se utilice un método específico para multiplicar números. Su trabajo muestra que, si uno puede multiplicar números grandes utilizando un cierto método eficiente, la transformada de Fourier cuántica puede construirse con muchos menos pasos de los que se creía posible anteriormente. Esta mejora se aplica tanto a la versión exacta y perfecta de la operación como a la versión ligeramente aproximada que se utiliza con frecuencia en la práctica. Los investigadores lograron esto combinando técnicas existentes con un truco ingenioso que consiste en copiar estados cuánticos y una comprobación final que asegura que la respuesta sea correcta en todo momento.

El núcleo del desafío radica en la enorme cantidad de puertas físicas necesarias para realizar la transformada. En el enfoque estándar, el número de puertas crece con el cuadrado del número de bits involucrados, lo que se vuelve inmanejable para problemas grandes. Una generación anterior de investigadores mejoró esto vinculando la transformada al problema de la multiplicación de enteros, reduciendo la tasa de crecimiento a un nivel que involucra logaritmos. Sin embargo, el nuevo estudio lleva este límite aún más allá. Los autores muestran que el número de puertas puede reducirse para coincidir con la eficiencia del método de multiplicación mismo, en lugar de ser un paso más lento. Si el método de multiplicación es altamente eficiente, la transformada de Fourier cuántica se vuelve correspondientemente eficiente.

Para lograr esto, los investigadores construyeron primero una versión exacta de la transformada. Comenzaron con un circuito aproximado, que es más fácil de construir pero no es perfectamente preciso. Luego utilizaron una técnica para copiar el estado cuántico producido por este circuito aproximado. Al comparar el estado original con la copia, pudieron verificar el resultado. Si el resultado era correcto, amplificaban su probabilidad hasta que se volviera seguro. Este proceso requería una rotación específica de un bit cuántico, un ángulo que depende del tamaño del problema. Si bien esta rotación no es un componente estándar en todos los circuitos cuánticos, su inclusión permitió al equipo convertir una solución aproximada en una perfecta sin añadir un número masivo de puertas adicionales.

Luego, el equipo aplicó este circuito exacto mejorado al problema de construir una transformada aproximada, que suele ser suficiente para aplicaciones del mundo real. Utilizaron un método recursivo, dividiendo el gran problema en piezas más pequeñas y manejables. En el pasado, las piezas más pequeñas de este rompecabezas se resolvían utilizando métodos antiguos y menos eficientes. Al reemplazar esas pequeñas piezas con su nuevo y altamente eficiente circuito exacto, toda la estructura se volvió mucho más ligera. El resultado es un circuito que utiliza significativamente menos puertas que cualquier diseño anterior, escalando de una manera que sigue de cerca la eficiencia de los algoritmos modernos de multiplicación de enteros.

Este trabajo también aborda la cuestión de cómo se construyen estos circuitos. Los investigadores señalan que su diseño depende de un ángulo de rotación que es difícil de calcular rápidamente utilizando computadoras clásicas. Debido a esto, la familia de circuitos que describen no es "uniforme", lo que significa que no existe una regla única y simple que genere cada versión del circuito para cada tamaño de problema sin ayuda externa. Esta es una limitación que reconocen, dejando abierta la pregunta de si se puede encontrar una versión totalmente uniforme que mantenga este alto nivel de eficiencia. No obstante, los hallazgos establecen una conexión nueva y más estrecha entre el costo de multiplicar números y el costo de realizar la transformada de Fourier cuántica.

Las implicaciones de este descubrimiento son significativas para el futuro de la computación cuántica. Si las recientes afirmaciones sobre algoritmos de multiplicación de enteros aún más rápidos resultan ser ciertas, la nueva construcción sugiere que la transformada de Fourier cuántica podría construirse con un número de puertas que crece incluso más lentamente de lo imaginado anteriormente. Esto acerca la posibilidad de ejecutar algoritmos cuánticos a gran escala, como los destinados a la factorización de números grandes, a la realidad. Los investigadores no solo han encontrado una pequeña optimización; han remodelado fundamentalmente los límites teóricos de cuán eficientemente se puede realizar esta operación crítica, demostrando que el camino hacia las computadoras cuánticas potentes puede ser más corto que los mapas que estábamos usando antes.

Resumen Técnico: Mejora de las Transformadas de Fourier Cuánticas Exactas y Aproximadas a partir de la Multiplicación

Planteamiento del Problema

La Transformada de Fourier Cuántica (QFT) es un subprocedimiento fundamental en algoritmos cuánticos, notablemente en el algoritmo de factorización de Shor y la estimación de fase cuántica. La implementación de circuito estándar de la QFT sobre $F_{2^q}$ requiere $O(q^2)$ puertas. Mientras que Cleve y Watrous (2000) redujeron el conteo de puertas para la QFT exacta a $O(q(\log q)^2 \log \log q)$ aprovechando algoritmos de multiplicación de enteros, y Ahokas, Cleve y Hales (2003) proporcionaron optimizaciones adicionales para la QFT aproximada, los autores identifican una brecha entre la complejidad de la multiplicación de enteros y la complejidad resultante del circuito QFT.

Específicamente, si la multiplicación de enteros de números de $n$ bits puede realizarse con $M(n) = O(n(\log n)^\alpha)$ puertas, la construcción de Cleve-Watrous produce una QFT exacta con $O(q(\log q)^{\alpha+1})$ puertas. El artículo aborda la cuestión de si este exceso de complejidad puede reducirse, con el objetivo de igualar más de cerca la complejidad de la multiplicación (es decir, lograr $O(q(\log q)^\alpha)$ ) tanto para las QFT exactas como para las aproximadas.

Metodología

Los autores proponen un enfoque de dos vertientes para mejorar la complejidad de puertas de las construcciones QFT:

1. Construcción de QFT Exacta

Los autores combinan el método de "exactificación" de Mosca y Zalka (2003) con la implementación basada en la multiplicación de Cleve y Watrous (2000).

Amplificación de Amplitud: Utilizan una técnica para convertir un circuito QFT aproximado (con probabilidad de éxito $p \geq 3/4$ $p \geq 3/4$ ) en uno exacto. Esto implica:
1. Copiar el Estado de Fourier: Utilizar el circuito de copia de Cleve-Watrous para duplicar el estado de Fourier, permitiendo que el original se preserve para la verificación.
2. Ajuste de Probabilidad: Introducir un qubit auxiliar y aplicar una rotación de un solo qubit específica $B(\theta_q)$ para ajustar la probabilidad de éxito conjunta de la respuesta correcta y el estado del qubit auxiliar a exactamente $1/4$ .
3. Iteración de Grover: Aplicar un único paso de amplificación de amplitud (una iteración de Grover) para aumentar la probabilidad de éxito a 1.
Conjunto de Puertas: La construcción utiliza puertas estándar (Hadamard, CNOT, puertas de Fase) más una rotación de un solo qubit específica $B(\theta_q)$ cuyo ángulo depende de $q$ . Esta puerta no estándar es necesaria para establecer la amplitud inicial para el paso de amplificación.

2. Construcción de QFT Aproximada

Para la QFT aproximada, los autores adaptan la construcción recursiva de Ahokas, Cleve y Hales (ACH).

División Recursiva: El registro de entrada se divide recursivamente en mitades superior e inferior. La construcción aplica una QFT recursiva al registro superior, realiza una operación de "fase-producto" entre los registros, aplica una QFT recursiva al registro inferior y permuta los registros.
Truncamiento: En la operación de fase-producto, solo se utilizan los $k = \Theta(\log(q/\varepsilon))$ bits más significativos de las entradas, donde $\varepsilon$ es el error de aproximación.
Casos Base: La recursión se detiene cuando un registro tiene un tamaño de por lo sumo $2k$ . En lugar de usar la QFT exacta estándar de Cleve-Watrous para estos casos base (que cuesta $O(k(\log k)^{\alpha+1})$ ), los autores sustituyen su QFT exacta mejorada (costo de $O(k(\log k)^\alpha)$ ).
Aproximación de Rotación: Dado que la QFT exacta mejorada depende de la rotación no estándar $B(\theta_q)$ , los autores demuestran que estas rotaciones pueden aproximarse eficientamente utilizando puertas de fase estándar $P(2\pi a/2^d)$ sin aumentar el conteo de puertas asintótico ni el espacio auxiliar. Consecuentemente, la construcción final para la QFT $\varepsilon$ -aproximada utiliza el mismo conjunto de puertas que Cleve y Watrous (Hadamard, NOT controlada y puertas de fase exactas).

Principales Contribuciones y Resultados

1. Mejora de la Complejidad de Puertas

La contribución principal es una reducción en el conteo de puertas asintótico para las QFT exactas y aproximadas, vinculándolas directamente con la complejidad de la multiplicación de enteros $M(n) = O(n(\log n)^\alpha)$ .

QFT Exacta (Teorema 1.1): Los autores construyen una QFT exacta en $q$ $q$ qubits usando $O(q(\log q)^\alpha)$ puertas. Esto mejora el límite previo de $O(q(\log q)^{\alpha+1})$ $O (q (lo g q)^{α + 1})$ de Cleve y Watrous.
- Nota: Esta construcción requiere una rotación adicional de un solo qubit $B(\theta_q)$ dependiente de $q$ .
QFT Aproximada (Teorema 1.2): Para un error de aproximación $\varepsilon$ $ε$ , los autores construyen un circuito utilizando $O(q(\log \log(q/\varepsilon))^\alpha)$ puertas. Esto mejora el límite previo de $O(q(\log \log(q/\varepsilon))^{\alpha+1})$ $O (q (lo g lo g (q / ε))^{α + 1})$ de Ahokas, Cleve y Hales.
- Nota: Esta construcción utiliza el mismo conjunto de puertas que Cleve y Watrous (Hadamard, NOT controlada y puertas de fase exactas) mediante la aproximación de las rotaciones necesarias.

2. Implicaciones de Reclamaciones Recientes sobre Multiplicación

El artículo destaca el impacto potencial de una reclamación reciente de OpenAI respecto a la multiplicación de enteros con complejidad $O(n(\log n)^{1-\kappa})$ para una constante $0 < \kappa < 1$ .

Si esta reclamación se sostiene para circuitos booleanos, establecer $\alpha = 1-\kappa$ resultaría en una QFT exacta de $o(q \log q)$ puertas y una QFT aproximada de $o(q \log \log q)$ puertas.
Esto sugiere un camino hacia circuitos QFT significativamente más eficientes que los límites de $O(q^2)$ o incluso $O(q \log q)$ que se creía alcanzables anteriormente sin tales avances en la multiplicación.

3. Límites de Recursos

Qubits Auxiliares: La construcción exacta utiliza $O(a(q) + M(q))$ qubits auxiliares (donde $a(q)$ es el conteo auxiliar del circuito aproximado). La construcción aproximada utiliza $O(L(\log L)^\alpha)$ qubits auxiliares, donde $L = \log(q/\varepsilon)$ .
Uniformidad: Los autores declaran explícitamente que sus familias de circuitos son no uniformes. Esto se debe a que el ángulo $\theta_q$ para la rotación $B(\theta_q)$ no puede ser computado actualmente de manera eficiente por un algoritmo clásico. Identifican la generación eficiente de estos ángulos como una pregunta abierta natural.

Significado y Reclamaciones

El artículo afirma que se está estrechando la conexión teórica entre el costo de la multiplicación de enteros y el costo de la Transformada de Fourier Cuántica. Al eliminar un factor logarítmico adicional en la complejidad de puertas, los autores demuestran que la QFT puede hacerse casi tan eficiente como el algoritmo de multiplicación subyacente.

Los autores son modestos respecto a la uniformidad de sus circuitos, reconociendo que la dependencia de un ángulo de rotación específico impide la construcción uniforme en el estado actual del conocimiento. También reiteran el problema abierto planteado por Aaronson (2025) sobre si una QFT exacta en $q$ qubits puede implementarse con $O(q)$ puertas, señalando que sus resultados mejoran el exponente pero aún no alcanzan el tamaño lineal.

El trabajo no propone nuevas implementaciones experimentales o aplicaciones específicas más allá de la utilidad general de la QFT en algoritmos como Shor y la estimación de fase. En su lugar, se centra en los límites de complejidad de circuito teóricos, ofreciendo una construcción refinada que aprovecha los avances recientes en la multiplicación de enteros clásica para reducir la sobrecarga de puertas cuánticas.