⚛️ quantum physics

Verifiable quantum advantage in extremely low depth

Este artículo presenta un problema de muestreo resoluble mediante circuitos cuánticos extremadamente superficiales (ya sea $\mathsf{QNC}^0[\log\log]$ o $\mathsf{QAC}^0$ ) que es clásicamente difícil bajo supuestos basados en redes y eficientemente verificable por una computadora clásica, demostrando así una ventaja cuántica verificable sin mediciones de mitad de circuito ni retroalimentación.

Autores originales: Alexandru Gheorghiu

Publicado 2026-09-02

📖 8 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Alexandru Gheorghiu

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

En la búsqueda de comprender el verdadero poder de las computadoras cuánticas, los científicos se hacen constantemente una pregunta engañosamente simple: ¿cuánta maquinaria cuántica se requiere realmente para resolver un problema que una computadora clásica no puede? Durante décadas, la visión predominante sugería que, para obtener una ventaja decisiva, un sistema cuántico necesitaba realizar cálculos complejos y profundos, entrelazando miles de operaciones en una secuencia larga e intrincada. Se pensaba que esta profundidad era la fuente de la capacidad única de la máquina para explorar posibilidades que permanecen ocultas para las computadoras ordinarias. Sin embargo, una nueva línea de investigación desafía esta intuición, indagando si las versiones más restringidas y superficiales de los circuitos cuánticos —aquellos que realizan solo un puñado de operaciones— pueden aun así superar a los mejores algoritmos clásicos. Lo que está en juego es mucho, porque si un sistema cuántico tan mínimo puede resolver un problema difícil, demostraría que la ventaja cuántica no es solo una característica de máquinas masivas y propensas a errores, sino una propiedad fundamental incluso de las estructuras cuánticas más simples. Crucialmente, para que esta ventaja sea útil, un observador humano que utilice una computadora estándar debe ser capaz de verificar el resultado de forma rápida y con certeza, convirtiendo una posibilidad teórica en una prueba práctica.

Un investigador ha construido ahora un rompecabezas matemático específico que demuestra este fenómeno. Diseñó una tarea que una computadora cuántica puede resolver utilizando un circuito increíblemente superficial, uno tan corto que apenas se eleva por encima del nivel de las puertas lógicas básicas. Sin embargo, resolver este mismo rompecabezas sigue siendo efectivamente imposible para cualquier computadora clásica que opere dentro de un tiempo razonable, asumiendo que ciertas dificultades matemáticas estándar se mantengan ciertas. Lo que hace que este logro sea particularmente sorprendente es que la solución no es una caja negra; un observador clásico puede verificar la respuesta de manera eficiente y confirmar que la máquina cuántica realmente realizó la hazaña. El investigador logró esto creando dos formas diferentes de construir el solucionador cuántico. La primera utiliza un circuito ligeramente más profundo que depende solo de conexiones estándar y simples entre cúbits. La segunda, aún más impresionante, utiliza un circuito de profundidad constante, lo que significa que no se vuelve más profundo sin importar cuán grande sea el problema, pero requiere un tipo de puerta específico que puede manejar muchas entradas a la vez. Ambas versiones tienen éxito donde las computadoras clásicas fallan, y ambas producen resultados que pueden ser verificados instantáneamente. Además, debido a que los circuitos con fan-in no limitado pueden ser simulados por circuitos con fan-out no limitado, la tarea también es resoluble por este último, aunque el autor enfatiza la versión de profundidad constante con fan-in no limitado como el logro más significativo.

El núcleo del descubrimiento reside en cómo el investigador tradujo un desafío criptográfico conocido a un formato adecuado para estas máquinas superficiales. Comenzó con un problema basado en la dificultad de encontrar patrones ocultos en datos ruidosos, un concepto conocido como aprendizaje con errores (learning with errors). En intentos previos para demostrar la ventaja cuántica utilizando ideas similares, la computadora cuántica tenía que realizar un proceso de múltiples pasos que involucraba mediciones en medio del cálculo y la retroalimentación de esos resultados hacia la máquina para guiar los siguientes pasos. Este enfoque "interactivo" requería que el estado cuántico se mantuviera coherente y estable durante mucho tiempo, lo cual es difícil de mantener. El nuevo trabajo evita esto por completo. El investigador desarrolló un método para codificar el problema de modo que la computadora cuántica pueda ejecutar una secuencia de operaciones única, corta e ininterrumpida, y luego medir el resultado una sola vez al final. Esto elimina la necesidad de mediciones y retroalimentación a mitad del circuito, simplificando significamente los requisitos de hardware.

Para que esto funcionara, el investigador tuvo que apoyarse en un conjunto de supuestos matemáticos ligeramente más fuertes que los utilizados en estudios anteriores. Introdujo una condición específica respecto a cómo se comportan ciertos bits de información, conocidos como bits de acarreo (carry bits), cuando se suman números en un sistema modular. Si bien este supuesto aún no se ha demostrado como verdadero basándose en la matemática estándar, el autor proporcionó evidencia sólida que respalda su validez. Argumentó que si una computadora clásica pudiera resolver su rompecabezas, ello implicaría un avance en la ruptura de estos supuestos matemáticos subyacentes, lo cual se cree ampliamente que es imposible. El resultado es una demostración robusta de que los circuitos cuánticos superficiales poseen suficiente estructura interna para resolver problemas clásicamente difíciles. El investigador mostró que la máquina cuántica prepara una superposición de muchas entradas posibles, las procesa a través de una codificación local y superficial, y luego mide la salida para revelar un patrón que codifica la solución.

Las implicaciones de este trabajo son dobles. Primero, estrechan la brecha entre lo que es teóricamente posible y lo que es prácticamente alcanzable con dispositivos cuánticos de corto plazo. Al mostrar que los circuitos de profundidad constante pueden lograr esta ventaja, el estudio sugiere que las futuras pruebas cuánticas de "cuanticidad" podrían no requerir los circuitos masivos y profundos que actualmente están más allá de nuestras capacidades de ingeniería. Segundo, clarifica la frontera entre el poder cuántico y el clásico. El investigador señaló explícamente que su resultado también se aplica a circuitos con puertas de fan-out no limitado, un tipo diferente de operación poderosa que es conocida por ser computacionalmente más fuerte que su modelo de fan-in no limitado de profundidad constante. En cambio, su éxito depende de la estructura específica de su codificación y de la dureza de los problemas de redes (lattices) subyacentes. El estudio no pretende haber resuelto el problema de construir una computadora cuántica universal, ni sugiere que estos circuitos superficiales puedan factorizar números grandes o romper la encriptación actual. Más bien, proporciona una tarea de muestreo precisa y verificable que sirve como un banco de pruebas claro.

La construcción involucra un protocolo de desafío y respuesta donde un verificador envía una clave pública a un probador. El probador, actuando como la máquina cuántica, prepara un estado cuántico, aplica el circuito superficial y devuelve un conjunto de números. El verificador luego comprueba si estos números satisfacen una relación específica. Si el probador es una computadora clásica, fallará en producir la relación correcta más de tres cuartas partes de las veces, incluso con las mejores estrategias posibles. Si el probador es la máquina cuántica honesta, tendrá éxito casi siempre. El investigador verificó que su implementación cuántica utiliza solo un ancho polinómico, lo que significa que el número de cúbits crece razonablemente con el tamaño del problema, y la profundidad permanece extremadamente baja. Este equilibrio de baja profundidad, dureza clásica y verificación eficiente marca un paso significativo en la comprensión de los requisitos mínimos para la ventaja cuántica.

Si bien el estudio se basa en supuestos que aún no han sido plenamente probados, el autor es cuidadoso al enmarcar sus resultados como condicionales a estas creencias matemáticas. Reconoce que el supuesto específico del "predicado de acarreo" (carry-predicate) que utiliza es una nueva adición al campo, aunque proporciona evidencia parcial de que probablemente se sostiene. Esta transparencia asegura que la comunidad científica pueda probar y refinar los supuestos más adelante. El trabajo también destaca las limitaciones de los enfoques actuales; por ejemplo, señalan que reducir la profundidad del circuito aún más para usar solo puertas estándar sin las puertas especiales de fan-in sigue siendo un desafío abierto. El investigador sugiere que lograr un circuito de profundidad constante real utilizando solo puertas simples podría requerir nuevas construcciones matemáticas que son actualmente difíciles de encontrar.

En última instancia, este artículo ofrece un ejemplo concreto de cómo un sistema cuántico puede superar a uno clásico con recursos mínimos. Mueve la conversación de la teoría de la complejidad abstracta a un protocolo tangible y verificable. Al eliminar la necesidad de circuitos profundos y mediciones a mitad del circuito, el investigador ha demostrado que la esencia de la ventaja cuántica puede encontrarse en estructuras muy superficiales. Este hallazgo amplía el horizonte de lo que podría ser posible para los dispositivos cuánticos tempranos y proporciona un estándar riguroso para probar si una máquina está realmente aprovechando la mecánica cuántica. El camino a seguir implica refinar estos supuestos y explorar si técnicas similares pueden aplicarse a otras tareas criptográficas, pero el resultado central permanece: un circuito cuántico superficial puede, de hecho, resolver un problema que es difícil para las computadoras clásicas y fácil de verificar.

Resumen Técnico: Ventaja Cuántica Verificable en Profundidad Extremadamente Baja

Planteamiento del Problema
El artículo aborda una brecha fundamental en la teoría de la complejidad cuántica: la falta de una tarea que sea simultáneamente resoluble por circuitos cuánticos de profundidad extremadamente baja, difícil para algoritmos clásicos de tiempo polinomial y eficientemente verificable por una computadora clásica. Si bien trabajos previos han establecido que los circuitos cuánticos de profundidad constante (específicamente $QNC^0_f$ con fan-out ilimitado) pueden resolver problemas clásicamente difíciles, y que existen pruebas de interacción de la naturaleza cuántica, no se conoce ningún problema de "caja blanca" que satisfaga los tres criterios utilizando únicamente compuertas de aridad acotada en profundidad sub-logarítmica o profundidad constante con fan-in ilimitado. Específicamente, las pruebas de existencia de cualidad cuántica de baja profundidad existentes suelen depender de mediciones a mitad del circuito, retroalimentación clásica (feed-forward) o oráculos aleatorios de caja negra, lo que oscurece las garantías de profundidad del circuito o requiere compuertas de fan-out ilimitado. La cuestión central es si se puede lograr una ventaja cuántica verificable dentro de las clases restringidas $QNC^0[\log \log]$ (profundidad log-log con fan-in acotado) y $QAC^0$ (profundidad constante con fan-in ilimitado).

Metodología
El autor construye un problema de muestreo basado en el marco de Aprendizaje con Errores (LWE), compilando la prueba de un solo round de la cualidad cuántica de Arabadjieva et al. [AGGM25] en circuitos de muy baja profundidad. La innovación técnica central es el uso de codificaciones aleatorizadas para transformar la evaluación de funciones de trampa libre de garra (TCF) basadas en LWE en una computación local y superficial.

Estructura del Protocolo: El protocolo es una tarea de desafío-respuesta de un solo round. El verificador muestrea ya sea una TCF $f$ (basada en LWE) o una función inyectiva $g$ (basada en un supuesto de conocimiento de red/lattice) que son computacionalmente indistinguibles. El probador debe devolver una respuesta $(y, d)$ (o un equivalente codificado) que satisfaga relaciones algebraicas específicas.
Codificación Aleatorizada: Para lograr una baja profundidad, el autor generaliza una codificación de mapa afín binario a mapas sobre un anillo $\mathbb{Z}_q$ $Z_{q}$ . La codificación reemplaza la computación global de $Mv + \eta$ $M v + η$ (donde $M$ $M$ es una matriz, $v$ $v$ es un vector de entrada y $\eta$ $η$ es el ruido) con una cadena de símbolos computables localmente.
- Codificación de Máscara de Camino (Path-Mask Encoding): La suma de las entradas se codifica usando "máscaras de camino" ( $h$ ) que transportan valores aleatorios a lo largo de un camino, cancelándose al sumarse. Esto asegura que cada símbolo de salida dependa de un número constante de valores de origen.
- Enmascaramiento de Entrada: Para evitar la reutilización de entradas entre filas (lo que rompería la localidad), se aplica una segunda capa de máscaras ( $r$ ).
- Localidad: Cada símbolo codificado depende de como máximo tres palabras de origen (entrada, máscara o ruido). Esto permite que el probador cuántico evalúe la codificación en paralelo.
Estrategia Cuántica: El probador cuántico honesto prepara una superposición sobre el bit de rama, la entrada, el ruido y las máscaras de codificación. Evalúa la codificación localmente, borra el registro de ruido (que ahora está entrelazado con la salida) y mide los registros en la base de Hadamard. Esto produce una dirección $D$ y un bit $C$ que satisfacen una relación de paridad derivada de la estructura de "garra" de la TCF.
Verificación: El verificador utiliza una trampa para verificar ya sea la validez de la imagen (en el caso inyectivo) o para recuperar las dos preimágenes y sus máscaras asociadas (en el caso de la TCF) para verificar la ecuación de paridad.

Supuestos Clave
La dificultad clásica del problema se basa en dos supuestos no estándar pero bien motivados:

Conocimiento de Punto de Red Subexponencial (LK-1/4): Un algoritmo que produce un punto cercano a una red debe "conocer" el vector de red más cercano. Esto se utiliza para extraer preimágenes para la función inyectiva $g$ .
Bit de Núcleo Adaptativo con Predicados de Acarreo (Adaptive-Hardcore-Bit with Carry Predicates): Una variante fortalecida de la propiedad de bit de núcleo adaptativo para LWE. Postula que ningún algoritmo clásico eficiente puede predecir una paridad de el secreto que incluya no solo términos lineales, sino también "bits de acarreo" que surgen de las sumas parciales de las ecuaciones LWE. El autor proporciona evidencia para este supuesto, pero señala que no se sabe actualmente si se deriva directamente de LWE estándar.

Resultos
El artículo presenta dos implementaciones del muestreador cuántico:

$QNC^0[\log \log]$ : Un circuito de profundidad $O(\log \log \lambda)$ utilizando únicamente compuertas de uno y dos qubits (fan-in acotado).
$QAC^0$ : Un circuito de profundidad constante $O(1)$ utilizando compuertas de fan-in ilimitado (compuertas Toffoli generalizadas).

Teorema 1.1 (Informal): Bajo los supuestos declarados, existe una familia de problemas de muestreo donde:

Un muestreador cuántico honesto es aceptado con una probabilidad de $1 - \text{negl}(\lambda)$ .
Cualquier muestreador clásico uniforme que corra en tiempo $2^{o(\lambda)}$ es aceptado con una probabilidad de máximo $3/4 + \text{negl}(\lambda)$ .
La computación cuántica no requiere mediciones a mitad del circuito ni retroalimentación; consiste en un único circuito unitario seguido de una capa de medición final.

Significado y Reivindicaciones
El artículo afirma proporcionar el primer ejemplo de una ventaja cuántica verificable que no requiere compuertas de fan-out ilimitado (las cuales son lo suficientemente poderosas como para colapsar las jerarquías de profundidad) o mediciones a mitad del circuito. Al compilar el protocolo AGGM usando codificaciones aleatorizadas, el autor demuestra que los circuitos cuánticos superficiales poseen suficiente estructura para resolver tareas clásicamente difíciles cuyas soluciones son eficientemente verificables.

El autor es modesto respecto a las limitaciones:

La construcción depende del supuesto no estándar de "predicado de acarreo", el cual aún no se ha demostrado que siga de LWE estándar.
El ancho del circuito es polinomial pero grande (estimado en $e^{O(\lambda^4 \log^6 \lambda)}$ ), lo que hace que su implementación experimental inmediata sea inviable en el corto plazo.
El resultado aún no logra un circuito de profundidad constante utilizando únicamente compuertas de aridad acotada (un verdadero $QNC^0$ ), ya que la aritmética sobre números de $L$ bits ( $L = \Theta(\log^2 \lambda)$ ) requiere o bien una profundidad de $O(\log \log \lambda)$ o fan-in ilimitado.

El trabajo amplía la comprensión de la computación cuántica superficial al mostrar que, incluso sin el poder del fan-out ilimitado o la retroalimentación interactiva, los circuitos cuánticos pueden mantener una ventaja verificable sobre la computación clásica bajo supuestos criptográficos plausibles.

Más como este