⚛️ quantum physics

Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm

Este trabajo presenta un algoritmo de multiplicación de matrices basado en núcleos cuánticos (QKMM) que logra una complejidad computacional asintóticamente óptima de $O(N^2 \log_2 N)$ , superando la eficiencia de los algoritmos clásicos actuales.

Autores originales: Jiaqi Yao, Ding Liu

Publicado 2026-02-10

📖 4 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Jiaqi Yao, Ding Liu

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 los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

El Gran Problema: El "Cuello de Botella" de la Inteligencia Artificial

Imagina que quieres construir la ciudad más grande y avanzada del mundo (esto sería la Inteligencia Artificial). Para construirla, necesitas mover millones de ladrillos cada segundo. En el mundo de la computación, esos "ladrillos" son las multiplicaciones de matrices (tablas gigantes llenas de números).

Actualmente, las computadoras más potentes del mundo son como obreros muy rápidos, pero que tienen que mover los ladrillos de uno en uno o en montones pequeños. A medida que la ciudad (la IA) crece, los obreros se cansan y el proceso se vuelve increíblemente lento y costoso. Es lo que los científicos llaman un "cuello de botella".

La Propuesta: El "Teletransporte de Ladrillos" (Algoritmo QKMM)

Este artículo presenta una nueva forma de trabajar usando la Computación Cuántica. Si la computación clásica es un obrero con un carretilla, la computación cuántica es como tener magia o teletransporte.

Los investigadores han creado un nuevo método llamado QKMM. Para entenderlo, usemos una analogía:

1. El método antiguo (Como el "Test de Swap"):

Imagina que para saber cuánto pesan dos sacos de arena, tienes que pesarlos uno por uno, compararlos, y cada vez que lo haces, el saco se ensucia o se rompe un poco. Es lento y, si lo haces muchas veces, al final no tienes sacos, sino un desastre de arena.

2. El nuevo método QKMM (El "Espejo Mágico"):

En lugar de mover los sacos, los científicos usan algo llamado "Kernel Cuántico". Imagina que tienes dos sacos de arena y, en lugar de pesarlos, los pones frente a un espejo mágico. El espejo no solo refleja la imagen, sino que, al observar el reflejo, te dice instantáneamente la relación exacta entre ambos sin que tengas que tocar los sacos originales.

¿Por qué es mejor?

No rompe nada: No daña los datos originales (lo que en ciencia llaman "preservar la coherencia").
Es ultra eficiente: En lugar de hacer millones de cálculos separados, el algoritmo usa la "superposición" (la capacidad cuántica de estar en varios estados a la vez) para resolver muchísimas multiplicaciones al mismo tiempo, como si un solo obrero pudiera estar en mil lugares a la vez.

¿Qué tan rápido es realmente? (La parte matemática simplificada)

El papel dice que su complejidad es $O(N^2 \log^2 N)$ . Suena complicado, pero piénsalo así:

Si el tamaño de tu problema (la cantidad de números) se duplica, una computadora normal se vuelve muchísimo más lenta (su esfuerzo crece de forma explosiva). Pero con este nuevo algoritmo cuántico, el esfuerzo crece de forma casi lineal. Es como si, aunque la ciudad creciera al doble de tamaño, tus obreros solo tuvieran que trabajar un poquito más, en lugar de tener que trabajar mil veces más.

¿Qué pasa si hay "ruido"? (El desafío del mundo real)

Aquí viene la parte honesta: las computadoras cuánticas actuales son como instrumentos musicales muy sensibles que se desafinan con el más mínimo soplido de viento (esto es el "ruido cuántico").

Los autores hicieron experimentos simulando este "viento". Descubrieron que:

Su método es más resistente que los anteriores. Es como un instrumento que, aunque haya ruido, sigue sonando bastante bien.
Sin embargo, si el problema es demasiado grande y hay mucho ruido, la precisión cae. Es un recordatorio de que todavía estamos en la "era de los instrumentos experimentales" y que necesitamos computadoras cuánticas más estables.

En resumen: ¿Por qué debería importarnos?

Este estudio es como haber encontrado un plano para un motor de teletransporte. Aunque todavía no tenemos la máquina perfecta para usarlo, los científicos han demostrado que matemáticamente es posible multiplicar matrices de una forma mucho más rápida que cualquier computadora actual.

Cuando esto se aplique a la realidad, la Inteligencia Artificial no solo será más inteligente, sino que podrá aprender y procesar información a una velocidad que hoy nos parece ciencia ficción.

Resumen Técnico: Reducción de la Complejidad de la Multiplicación de Matrices a $O(N^2 \log^2 N)$ mediante un Algoritmo Cuántico Asintóticamente Óptimo

1. El Problema

La multiplicación de matrices es una operación fundamental en la computación clásica, esencial para el entrenamiento de modelos de aprendizaje profundo (Deep Learning). A pesar de décadas de investigación, la complejidad de los mejores algoritmos clásicos (como el método de láser mejorado) se sitúa en torno a $O(N^{2.371552})$ , lo que significa que no han logrado alcanzar el límite teórico inferior de $O(N^2)$ .

En el ámbito cuántico, aunque existe el potencial de paralelismo, los algoritmos actuales carecen de un marco de evaluación estandarizado. Los métodos existentes (como el Swap Test o el Hadamard Test) presentan limitaciones significativas: el primero altera los qubits de datos impidiendo su reutilización, y el segundo requiere un exceso de qubits auxiliares y puertas lógicas, lo que resulta en una escalabilidad pobre para la era NISQ (Dispositivos Cuánticos de Escala Intermedia con Ruido).

2. Metodología

Los autores proponen un nuevo marco denominado Multiplicación de Matrices Basada en Kernel Cuántico (QKMM). La metodología se basa en la descomposición de la multiplicación de matrices en operaciones de producto interno (inner product) utilizando el método de módulo de producto interno de kernel cuántico.

El algoritmo se desarrolla en cuatro niveles de complejidad creciente:

V2V (Vector-to-Vector): El bloque fundamental que calcula el módulo del producto interno de dos vectores sin necesidad de qubits auxiliares adicionales para establecer relaciones, permitiendo la lectura directa desde el estado fundamental.
V2M (Vector-to-Matrix): Una extensión que utiliza un registro de índices para tratar cada fila de una matriz como un vector individual, permitiendo la multiplicación matriz-vector en un solo circuito.
M2M (Matrix-to-Matrix): Una extensión dual que utiliza dos registros de índices (uno para filas y otro para columnas), permitiendo la computación completa de la multiplicación de dos matrices en un único circuito cuántico.
M-MM (Multi-Matrix-Matrix): Una optimización que permite multiplicar una matriz por múltiples matrices de forma simultánea aprovechando la superposición cuántica.

La implementación utiliza codificación de amplitud para mapear los datos en estados cuánticos y emplea puertas RY multicontroladas para la transformación de datos.

3. Contribuciones Clave

Optimización Asintótica: El algoritmo logra una complejidad de tiempo de $O(N^2 \log^2 N)$ en términos de conteo de puertas cuánticas. Los autores demuestran matemáticamente que, a medida que $N \to \infty$ , esta complejidad se aproxima al límite teórico inferior de $O(N^2)$ , lo que lo hace asintóticamente óptimo.
Nuevo Estándar de Medición: Propone el uso del conteo de puertas cuánticas básicas como la métrica fundamental para evaluar la complejidad de la multiplicación de matrices cuánticas (QMM), superando la ambigüedad de métricas anteriores como la complejidad de consultas o de qubits.
Eficiencia de Recursos: A diferencia de los métodos anteriores, el QKMM minimiza el uso de qubits auxiliares y evita la redundancia en la codificación de datos, permitiendo un mayor paralelismo.

4. Resultados

Los autores validaron su algoritmo mediante simulaciones tanto en modelos sin ruido como en modelos con ruido realistas (simulando hardware de superconductores de Origin Quantum):

Simulación sin ruido: Se demostró que el QKMM supera significativamente al Swap Test y al Hadamard Test en eficiencia temporal y uso de recursos a medida que aumenta la dimensión $N$ . El paralelismo implementado reduce drásticamente el tiempo de cómputo en las tareas M2M y M-MM.
Simulación con ruido (Modelo NISQ):
- El algoritmo mostró una alta fidelidad ( $>0.95$ ) en dimensiones pequeñas (2 a 4).
- Se identificó que, en dimensiones mayores, el ruido de las puertas lógicas es el factor dominante que degrada la fidelidad, por encima del ruido ambiental ( $T_1$ y $T_2$ ).
- A pesar de la degradación en entornos de ruido combinado, el QKMM demostró una mayor resiliencia y una acumulación de error más lenta en comparación con los métodos tradicionales.

5. Significado e Impacto

Este trabajo marca un avance crítico hacia la "computación intensiva cuántica". Al proporcionar un algoritmo que se acerca al límite teórico de eficiencia, abre la puerta para acelerar tareas de computación científica y el entrenamiento de modelos de Inteligencia Artificial masivos. Además, establece un marco de evaluación unificado que permitirá a la comunidad científica comparar de manera justa futuros algoritmos de multiplicación de matrices cuánticas.