⚛️ quantum physics

On the practicality of quantum sieving algorithms for the shortest vector problem

Este trabajo concluye que, incluso bajo supuestos optimistas sobre la tecnología cuántica, los algoritmos de cribado cuántico no ofrecen una ventaja práctica significativa frente a los ordenadores clásicos para resolver el problema del vector más corto en dimensiones relevantes para la criptografía postcuántica, debido a los enormes requisitos de recursos físicos y tiempo de ejecución.

Autores originales: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

Publicado 2026-04-13

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

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

Imagina que la criptografía moderna (la que protege tus bancos, correos y secretos en internet) se basa en un rompecabezas matemático extremadamente difícil de armar: encontrar la "aguja" más pequeña en un "pajero" gigante y multidimensional. A esto los matemáticos le llaman el Problema del Vector Más Corto (SVP).

Hasta hace poco, pensábamos que las computadoras cuánticas (esas máquinas del futuro que prometen resolver cosas imposibles) podrían encontrar esa aguja en un abrir y cerrar de ojos, rompiendo toda la seguridad actual.

Este artículo, escrito por un equipo de investigadores, llega con una noticia que calmará a los paranoicos y decepcionará a los entusiastas de la ciencia ficción: las computadoras cuánticas actuales, y las que podemos imaginar en un futuro cercano, no son tan rápidas como pensábamos para romper estos códigos.

Aquí te explico qué descubrieron usando analogías sencillas:

1. La Búsqueda de la Aguja (El Algoritmo de Sieving)

Imagina que tienes una lista de millones de vectores (flechas en el espacio) y quieres encontrar dos que, al restarse, te den una flecha muy pequeña.

El método clásico: Es como revisar la lista una por una, comparando flechas. Lento, pero seguro.
El método cuántico (Grover): Es como tener un "detective mágico" que puede revisar muchas flechas a la vez, reduciendo el tiempo de búsqueda. Teóricamente, debería ser mucho más rápido.

2. El Problema de la "Memoria Mágica" (QRAM)

Aquí es donde el artículo pone un freno de mano. Para que el detective cuántico funcione, necesita acceso instantáneo a una base de datos gigante. En el mundo cuántico, esto se llama QRAM (Memoria de Acceso Aleatorio Cuántica).

La analogía: Imagina que el detective cuántico es un genio que puede leer 1 millón de libros en un segundo. Pero, para leerlos, necesita que alguien le traiga los libros de una biblioteca infinita.
El cuello de botella: Construir esa "biblioteca cuántica" (QRAM) es tan costoso y difícil que requiere una cantidad de "ladrillos" (qubits físicos) casi infinita. El artículo calcula que, para resolver el problema en el nivel de seguridad que usa el mundo hoy (dimensión 400), necesitarías 10 trillones de qubits físicos.
- Para que te hagas una idea: Hoy tenemos computadoras cuánticas con unos cientos de qubits. Necesitaríamos una máquina miles de veces más grande que todo el hardware cuántico que existe en el universo combinado.

3. El Costo de la "Seguridad" (Corrección de Errores)

Las computadoras cuánticas son muy frágiles; un poco de ruido (como un golpe de aire o una fluctuación de temperatura) y el cálculo se arruina. Para arreglar esto, usamos "códigos de corrección de errores".

La analogía: Es como intentar mantener una torre de naipes en medio de un huracán. Para que la torre no se caiga, tienes que rodearla con 100 guardias que vigilen cada carta.
El resultado: Por cada "qubit lógico" (el cerebro del cálculo) que necesitas, tienes que usar miles de "qubits físicos" (los guardias) para protegerlo. Esto infla el tamaño de la computadora cuántica a niveles astronómicos.

4. La Conclusión: ¿Quién gana la carrera?

Los autores hicieron los cálculos con los mejores escenarios posibles (asumiendo que la tecnología avanza mucho, que los errores son mínimos y que tenemos las mejores herramientas teóricas).

El veredicto: Para romper un código de seguridad estándar (como los que propone el NIST para proteger el futuro), una computadora cuántica tardaría 10^31 años.
- ¿Cuánto es eso? La edad del universo es de unos 13.800 millones de años. 10^31 años es un número tan grande que es imposible de imaginar. Es como si el universo se hubiera repetido trillones de veces y aún no hubieras terminado el trabajo.
La comparación: Una computadora clásica normal (como la de tu escritorio, pero muy potente) tardaría exactamente el mismo tiempo.

¿Qué significa esto para nosotros?

No entres en pánico: La criptografía basada en "retículos" (lattice-based cryptography), que es la favorita para proteger nuestros datos contra computadoras cuánticas, sigue siendo segura. Las computadoras cuánticas no van a romperla mañana, ni el próximo siglo.
La ventaja cuántica es ilusoria (por ahora): Aunque la teoría dice que las computadoras cuánticas son más rápidas, en la práctica, el costo de construir la máquina (la memoria y la corrección de errores) es tan alto que anula cualquier ventaja de velocidad. Es como tener un Ferrari (el algoritmo cuántico) pero tener que empujarlo por una montaña de arena (el hardware necesario).
El futuro: Para que las computadoras cuánticas sean una amenaza real, no basta con mejorar el software; necesitamos revoluciones físicas. Necesitamos descubrir cómo hacer memorias cuánticas baratas y cómo corregir errores sin necesitar millones de qubits extra.

En resumen: El artículo nos dice que, aunque las computadoras cuánticas son fascinantes y prometedoras, para el problema de romper la seguridad actual, siguen siendo como intentar apagar un incendio forestal con una jeringa llena de agua. La teoría es bonita, pero la práctica nos dice que estamos a salvo por mucho tiempo.

Resumen Técnico: Evaluación de Recursos para Algoritmos de Cribado Cuántico en Criptografía Post-Cuántica

1. El Problema

La criptografía basada en retículos (lattice-based cryptography) es uno de los principales candidatos para la criptografía post-cuántica, con estándares siendo definidos por el NIST. Su seguridad se basa en la dificultad computacional del Problema del Vector Más Corto (SVP): encontrar el vector no nulo más corto en un retículo entero.

Aunque se conocen aceleraciones cuánticas asintóticas para resolver el SVP utilizando la búsqueda de Grover sobre algoritmos de cribado (sieving), existe una brecha crítica en la comprensión de los recursos reales necesarios para implementar estas soluciones. La mayoría de los estudios anteriores ignoran costos críticos como:

La memoria de acceso aleatorio cuántica (QRAM).
La corrección de errores cuánticos (QEC).
La aritmética cuántica de punto fijo.
Las arquitecturas físicas específicas.

El objetivo de este trabajo es realizar una estimación de recursos precisa y no asintótica para determinar si los algoritmos de cribado cuántico ofrecen una ventaja real frente a los clásicos en dimensiones de interés criptográfico (alrededor de $D=400$ ).

2. Metodología

Los autores realizan un análisis exhaustivo de los recursos necesarios para ejecutar algoritmos de cribado mejorados con la búsqueda de Grover. Su metodología se basa en los siguientes pilares:

Algoritmos Analizados: Evalúan el NVSieve (Nguyen-Vidick) y el GaussSieve, tanto en sus versiones puras como mejoradas con técnicas de búsqueda de vecinos más cercanos:
- Hashing Sensible a la Localidad (LSH): Angular y Esférico.
- Filtrado Sensible a la Localidad (LSF): Esférico.
Modelo de Hardware y Corrección de Errores:
- Arquitecturas Físicas: Comparan arquitecturas de "baselines" (interacciones vecinas en 2D) y arquitecturas de "volumen activo" (conexiones no locales logarítmicas).
- Corrección de Errores: Utilizan códigos de superficie (Surface Codes) con un modelo de ruido de circuito incoherente ( $p_{phy} = 10^{-5}$ ).
- Distilación de Estados Mágicos: Implementan protocolos de distilación concatenados de tres niveles (usando códigos de Reed-Muller) para lograr tasas de error en estados mágicos $|CCZ\rangle$ inferiores a $10^{-40}$ , necesarias para operaciones Toffoli fiables.
- Ciclos de Código: Asumen un ciclo de código de 100 ns y un tiempo de reacción (decodificación clásica) de 1 µs.
Aritmética Cuántica: Descomponen los oráculos de Grover en operaciones aritméticas básicas (suma, comparación, multiplicación) utilizando circuitos de punto fijo de 32 bits ( $\kappa=32$ ). Utilizan sumadores de Gidney y multiplicadores basados en el método escolar optimizado para minimizar el conteo de puertas Toffoli.
QRAM: Incorporan el costo de la memoria de acceso aleatorio cuántica (QRAM) utilizando la arquitectura de "bucket-brigade", que permite acceso superpuesto a datos clásicos, pero con un alto costo en qubits físicos.
Búsqueda No Asintótica: Utilizan variantes de Grover que no requieren conocer el número de soluciones de antemano (búsqueda exponencial), lo cual es crucial para algoritmos heurísticos como el GaussSieve.

3. Contribuciones Clave

Estimación de Recursos Realista: Es el primer trabajo que integra simultáneamente QRAM, corrección de errores de múltiples niveles, aritmética cuántica detallada y arquitecturas físicas específicas para algoritmos de cribado de retículos.
Análisis de la QRAM: Demuestran que la QRAM es el componente dominante en el costo de los qubits físicos, requiriendo un número de qubits lógico aproximadamente igual al tamaño de la base de datos accesada.
Comparación Clásica vs. Cuántica: Realizan una comparación directa de tiempos de ejecución, desglosando tanto las operaciones cuánticas (búsqueda de Grover) como las operaciones clásicas necesarias (hashing y pre-procesamiento), algo que estudios previos omitieron al comparar solo conteos de operaciones.
Evaluación de Dimensiones Críticas: Se centran en la dimensión $D=400$ , que corresponde al nivel de seguridad mínimo de los estándares post-cuánticos del NIST (Nivel 1).

4. Resultados Principales

Los resultados son contundentes y muestran una falta de ventaja cuántica práctica en las dimensiones relevantes:

Recursos de Qubits: Para resolver el SVP en una dimensión $D=400$ $D = 400$ utilizando el algoritmo más eficiente (GaussSieve con LSF esférico) bajo una arquitectura de volumen activo, se requieren aproximadamente $10^{13}$ qubits físicos.
- La gran mayoría de estos qubits se deben a la QRAM necesaria para almacenar y acceder a la lista de vectores candidatos.
Tiempo de Ejecución: El tiempo estimado para completar la tarea es de aproximadamente $10^{31}$ años.
- Curiosamente, un ordenador clásico de un solo núcleo con una velocidad de reloj de 6 GHz tardaría un tiempo comparable ( $\approx 10^{31}$ años) para resolver el mismo problema.
Comparación con la Edad del Universo: El tiempo de ejecución excede en órdenes de magnitud la edad del universo, lo que hace que la implementación sea físicamente imposible con la tecnología actual o previsible.
Impacto de la QRAM: Si se asume un escenario optimista donde la QRAM tiene un costo despreciable, el número de qubits físicos cae drásticamente (a $\approx 10^9$ para $D=1000$ ), pero el tiempo de ejecución sigue siendo prohibitivo debido a la profundidad del circuito y la corrección de errores.
Aceleración Cuántica: En dimensiones criptográficas ( $D \approx 400$ ), la aceleración cuántica es insignificante. Solo en dimensiones extremadamente grandes ( $D > 1000$ ) se observa una ventaja de velocidad de unos 5 órdenes de magnitud, pero esto está muy lejos de las necesidades de los estándares criptográficos actuales.

5. Significado y Conclusión

El estudio concluye que, bajo las suposiciones más optimistas actuales sobre hardware, corrección de errores y protocolos teóricos, no existe una ventaja cuántica práctica para romper la criptografía basada en retículos mediante algoritmos de cribado en las dimensiones de seguridad estándar.

Implicaciones para la Seguridad: Los estándares post-cuánticos propuestos por el NIST (como Kyber, Dilithium, Falcon) parecen estar seguros contra ataques cuánticos basados en Grover y cribado, al menos en el horizonte de tiempo previsible.
Barreras Tecnológicas: Para que exista una ventaja cuántica significativa, se necesitarían avances revolucionarios en:
1. Arquitectura de Memoria Cuántica (QRAM): Reducir drásticamente el costo de qubits físicos para el almacenamiento de datos.
2. Corrección de Errores: Mejoras sustanciales en la tasa de error de los qubits físicos o en la eficiencia de los códigos de corrección.
3. Protocolos Teóricos: Nuevos algoritmos que no dependan de la búsqueda de Grover o que reduzcan la complejidad de los oráculos.

En resumen, el trabajo desmitifica la idea de que la computación cuántica romperá inminentemente la criptografía basada en retículos, estableciendo que los requisitos de recursos físicos son actualmente inalcanzables y que la ventaja cuántica es marginal en el régimen de seguridad relevante.