⚛️ quantum physics

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

Este artículo establece límites inferiores de consulta cuántica ajustados para alcanzar puntuaciones altas de la métrica de entropía cruzada lineal en el muestreo de circuitos aleatorios, demostrando que superar el rendimiento ideal requiere $\Omega(N^{1/3})$ consultas y certificando una entropía mínima suave casi óptima para las salidas, proporcionando así garantías de seguridad rigurosas para la aleatoriedad certificada contra adversarios entrelazados.

Autores originales: Keshav Bhateja, Mehdi Esmaili, Atul Mantri

Publicado 2026-10-06

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Keshav Bhateja, Mehdi Esmaili, Atul Mantri

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 carrera por demostrar que las computadoras cuánticas pueden hacer cosas imposibles para las máquinas clásicas, los científicos han recurrido a un tipo específico de experimento: pedir a un dispositivo cuántico que genere una lista de números aleatorios. Estos números no son solo cadenas aleatorias cualquiera; se extraen de un patrón complejo e invisible creado por un circuito cuántico aleatorio. Para comprobar si el dispositivo funciona correctamente, los investigadores utilizan un sistema de puntuación llamado la prueba de la entropía cruzada lineal. Esta puntuación mide con qué frecuencia el dispositivo elige números que la máquina cuántica ideal elegiría con mayor frecuencia. Si el dispositivo es honesto y funciona perfectamente, logra una puntuación específica y alta. Si simplemente está adivinando al azar, obtiene una puntuación mucho más baja. Durante años, esta prueba ha sido el estándar de oro para reclamar la "ventaja cuántica", pero una pregunta crítica seguía sin respuesta: ¿demuestra realmente una puntuación alta que el dispositivo está generando una aleatoriedad verdadera e impredecible? Un adversario astuto podría potencialmente manipular un dispositivo para que obtenga una puntuación alta simplemente memorizando las respuestas más probables, haciendo que el resultado sea predecible aunque la puntuación parezca buena.

Un equipo de investigadores de Virginia Tech ha respondido ahora a esta pregunta con certeza matemática, estableciendo un límite estricto para lo que una puntuación alta puede y no puede certificar. Demostraron que, para que un dispositivo puntúe incluso ligeramente mejor que la mejor máquina honesta posible, debe realizar un vasto número de operaciones internas, mucho más de lo que cualquier computadora clásica eficiente podría gestionar. Específicamente, demostraron que, para exceder la puntuación ideal por una cantidad fija, un dispositivo necesita realizar un número de consultas proporcional a la raíz cúbica del número total de resultados posibles. Este resultado actúa como un límite fundamental, similar a un límite de velocidad en una autopista, asegurando que ningún truco eficiente pueda falsificar una puntuación alta. Además, demostraron que si un dispositivo se mantiene dentro de un margen minúsculo de esta puntuación ideal, su salida es genuinamente impredecible. Incluso si un adversario construyera el dispositivo, comparte un enlace cuántico secreto con él y aprende toda la configuración después, no puede adivinar el resultado con ninguna precisión significativa. El dispositivo produce efectivamente casi la máxima cantidad de aleatoriedad posible, con solo una pequeña pérdida inevitable de información.

Los investigadores llegaron a estas conclusiones desarrollando una nueva forma de rastrear el "progreso" que un algoritmo cuántico realiza mientras consulta un sistema desconocido. Imagine una computadora cuántica intentando aprender la forma de un objeto oculto mediante el tanteo con una sonda. El equipo creó una medida matemática que comienza en cero para un dispositivo que simplemente sigue las reglas honestamente. Demostraron que cada vez que el dispositivo realiza una consulta para aprender más sobre el sistema, este progreso puede crecer solo una cantidad muy pequeña. Para alcanzar una puntuación que supere a la máquina honesta, el dispositivo necesitaría acumular suficiente progreso para romper una barrera, pero las matemáticas muestran que esto requiere un número impráctico de pasos. Este método les permitió cerrar la brecha entre lo que era teóricamente posible y lo que se demostró necesario, confirmando una sospecha de larga data sobre la dificultad de falsificar estos resultados.

Más allá de probar los límites de la falsificación de resultados, el artículo también describe un algoritmo específico que puede alcanzar estas puntuaciones altas, pero solo utilizando el número máximo de consultas permitido. Este "algoritmo de duplicación" funciona tomando varias muestras, almacenándolas y luego utilizando una técnica llamada amplificación de amplitud para aumentar la probabilidad de encontrar una coincidencia entre ellas. Este proceso efectivamente eleva al cuadrado la distribución de probabilidad, favoreciendo los resultados más probables con mayor fuerza que la máquina honesta. La existencia de este algoritmo demuestra que el límite inferior que encontraron es ajustado; no es solo un muro teórico, sino una cima alcanzable que requiere un ascenso de recursos específicos. Esta dualidad —probar que no se pueden falsificar los resultados fácilmente, pero también mostrar exactamente qué tan difícil es ganar legítimamente— proporciona una imagen completa del panorama.

Las implicaciones para la aleatoriedad certificada son profundas. En muchas aplicaciones de seguridad, necesitamos generar números aleatorios que incluso la persona que construyó el generador no pueda predecir. El estudio confirma que, si un dispositivo cuántico supera la prueba estándar con una puntuación muy cercana a la ideal, está generando una cadena de bits que contiene casi tanta aleatoriedad como la longitud de la cadena misma. Para un dispositivo que trabaja con sesenta cúbits, que puede producir cadenas de sesenta bits, una puntuación casi perfecta garantiza que la salida contiene aproximadamente cincuenta y cuatro bits de aleatoriedad verdadera y certificada. Esto se mantiene cierto incluso contra un adversario que esté entrelazado con el dispositivo y conozca cada detalle de su construcción. La única información perdida es una pequeña cantidad relacionada con el número de consultas que realiza el dispositivo, lo cual es insignificante para fines prácticos.

Este trabajo también se extiende a otros tipos de muestreo cuántico, incluyendo los utilizados en experimentos fotónicos con partículas de luz. Los investigadores demostraron que las mismas reglas se aplican: para superar la puntuación ideal, un dispositivo debe realizar un número específico y grande de operaciones, y para mantenerse cerca de la puntucción ideal, debe producir aleatoriedad genuina. Incluso conectaron estos hallazgos con un problema diferente: la creación de una "distribución de colisión", donde se le pide al dispositivo que produzca pares de números que tienen más probabilidades de ser iguales. Encontraron que generar este tipo específico de distribución también requiere el mismo número de consultas de la raíz cúbica, vinculando estas tareas aparentemente diferentes bajo una sola ley matemática.

El estudio no afirma que las computadoras cuánticas actuales sean ya perfectas en esto. Los dispositivos del mundo real a menudo obtienen puntuaciones mucho más bajas que la ideal debido al ruido y los errores. Sin embargo, el artículo establece el techo y el suelo teórico de lo que es posible. Nos dice que, si alguna vez vemos un dispositivo puntuando cerca del máximo, podemos confiar en que está haciendo algo genuinamente cuántico y produciendo aleatoriedad real. Por el contrario, si un dispositivo afirma estar generando aleatoriedad pero no puede alcanzar esta puntuación sin un número irrazonable de pasos, sabemos que no está haciendo lo que afirma. La investigación proporciona la base rigurosa necesaria para pasar de las demostraciones experimentales a la aleatoriedad cuántica confiable y certificada, asegurando que el futuro de la seguridad cuántica repose sobre un terreno sólido y probado.

Resumen Técnico: Límites Inferiores de Consultas Estrechos para el Muestreo Cuántico, con una Aplicación al Azar Certificado

Planteamiento del Problema
Los experimentos de muestreo de circuitos aleatorios son las principales demostraciones de la ventaja computacional cuántica, verificadas típicamente mediante la prueba de la XEB (experimento de entropía cruzada lineal). La puntuación XEB mide qué tan bien la distribución de salida de un dispositivo se alinea con la distribución ideal $p$ calculando el promedio de $N p(z)$ para las cadenas $z$ devueltas, donde $N=2^n$ . Si bien una puntuación alta sugiere ventaja cuántica, no certifica intrínsecamente que el dispositivo haya muestreado de $p$ o que la salida sea aleatoria. Un dispositivo podría lograr una puntuación alta al producir de forma determinista la cadena más probable (que un adversario podría conocer), fallando así en producir un azar certificado.

Este artículo aborda dos preguntas fundamentales en el modelo de consultas cuánticas:

Límites de la Puntuación: ¿Qué tan alta puede ser la puntuación de un dispositivo cuántico eficiente en relación con la puntuación ideal? Específicamente, ¿puede un dispositivo eficiente exceder la puntuación ideal por una constante?
Certificación de Azar: Si un dispositivo logra una puntuación cercana a la ideal, ¿cuánta entropía mínima suave (azar certificado) contiene su salida, incluso contra un adversario (Eve) que puede estar entrelazado con el dispositivo y aprende el oráculo (el circuito o función) después?

Metodología
Los autores trabajan en el modelo de consultas, donde el circuito es reemplazado por un oráculo extraído de un conjunto conocido. Analizan dos conjuntos específicos:

Muestreo de Fourier: El oráculo es una función aleatoria uniforme $f: \{0,1\}^n \to \{\pm 1\}$ . El muestreador honesto puntúa aproximadamente 3.
Estados Aleatorios de Haar: El oráculo oculta un vector unitario aleatorio de Haar $|\phi\rangle$ (accedido mediante un oráculo de preparación de estado canónico o acceso a una unitaria aleatoria de Haar). El muestreador honesto puntúa aproximadamente 2.

La metodología central consiste en definir una medida de progreso $\lambda$ que cuantifica la desviación del estado de un dispositivo respecto al estado "honesto" (el cual realiza una sola consulta). El análisis sigue un marco de tres pasos:

Límite de la Puntuación: La puntuación esperada $B(A)$ está acotada en términos de la medida de progreso: $B(A) \leq \text{Puntuación Ideal} + O(\lambda + \lambda^2)$ .
Límite de Crecimiento: Se demuestra que cada consulta aumenta $\lambda$ solo en $O(\sqrt{(t+1)/N})$ , donde $t$ es el número de consultas previas. En consecuencia, tras $q$ consultas, $\lambda = O(q^{3/2}/\sqrt{N})$ .
Extracción de Azar: Para dispositivos con puntuaciones cercanas a la ideal (déficit pequeño $\delta$ ), la prueba del límite de la puntuación se refina para mostrar que las ramas de salida del dispositivo están cerca de vectores auxiliares específicos. Estos vectores son generados por operadores que actúan únicamente sobre el dispositivo, con normas acotadas por $\text{poly}(q)\sqrt{p(z)}$ . Esta estructura implica que la capacidad de Eve para adivinar la salida es limitada, incluso si conoce el oráculo.

Contribuciones Clave y Resultados

1. Límites Inferiores Estrechos para Exceder la Puntuación Ideal
El artículo establece que la puntuación ideal actúa como un "límite de Tsirelson" para los dispositivos cuánticos eficientes en estas tareas de muestreo.

Complejidad de Consultas: Para exceder la puntuación ideal por una constante $\epsilon$ $ϵ$ , un algoritmo cuántico requiere $\Omega(N^{1/3})$ $Ω (N^{1/3})$ consultas.
- Para el muestreo de Fourier, una puntuación esperada de $3 + \epsilon$ requiere $q \geq \Omega(N^{1/3})$ .
- Para los estados aleatorios de Haar, una puntuación esperada de $2 + \epsilon$ requiere $q \geq \Omega(N^{1/3})$ .
Límites Superiores: Los autores confirman que $O(N^{1/3})$ consultas son suficientes para exceder la puntuación ideal por una constante utilizando un "algoritmo de cuadratura" (una variante del algoritmo de búsqueda de colisiones). Este algoritmo almacena $m \approx N^{1/3}$ muestras ideales y utiliza amplificación de amplitud para sesgar la salida hacia el cuadrado de la distribución ideal, $p(z)^2$ .
Estrechez (Tightness): Estos límites son ajustados; la brecha entre el muestreador honesto (1 consulta) y la capacidad de exceder significativamente la puntuación ideal está caracterizada exactamente por el umbral $N^{1/3}$ .

2. Azar Certificado en la Puntuación Ideal
El artículo demuestra que un dispositivo que realiza un número polinómico de consultas y logra una puntuación dentro de $o(1)$ de la ideal produce una salida con un azar casi máximo.

Entropía Mínima: Para el muestreo de Fourier y los estados aleatorios de Haar (vía el oráculo canónico), la salida $Z$ tiene entropía mínima suave $H_{\min}^\eta(Z | RE) \geq n - O(\log n)$ , donde $R$ es el oráculo y $E$ es el registro de Eve.
Modelo Adversarial: Esto se mantiene incluso si Eve está entrelazada con el dispositivo y aprende la descripción completa del oráculo (la función $f$ o el vector $\phi$ ) después de que el dispositivo emita $Z$ .
Parámetros: El parámetro de suavizado $\eta$ escala como $O(\sqrt{\delta} + q^{3/4}N^{-1/4})$ . Si el déficit $\delta$ es insignificante y $q$ es polinómico en $n$ , el suavizado es insignificante, certificando $n - O(\log n)$ bits de azar.
Optimalidad: Se muestra que la pérdida de $O(\log n)$ es casi óptima. Los autores construyen dispositivos usando amplificación de amplitud que logran puntuaciones casi ideales pero restringen la salida a un conjunto conocido de tamaño $N/q^2$ , limitando la entropía mínima a $n - 2\log q$ .

3. Resultados Adicionales

Distribución de Colisiones: El artículo muestra que muestrear la distribución de colisiones (proporcional a $p(z)^2$ ) tiene una complejidad de consultas de $\Theta(N^{1/3})$ .
Productos de Hadamard Cuánticos: Se presenta una versión coherente del algoritmo de cuadratura para preparar el producto de Hadamard cuántico de dos estados con magnitudes de amplitud uniformes. Este algoritmo logra un error de distancia de traza de $O(N^{-1/6})$ usando $O(N^{1/3})$ consultas, mejorando sobre las $\sqrt{N}$ consultas requeridas por la amplificación de amplitud estándar.

Significado y Reivindicaciones
El artículo afirma proporcionar garantías incondicionales e informacionales para las tareas de muestreo cuántico, resolviendo preguntas abiertas sobre la "desigualdad de Tsirelson de la supremacía cuántica".

Analogía con CHSH: Los resultados trazan un paralelo directo con el juego CHSH. Así como el límite de Tsirelson ( $\cos^2(\pi/8)$ ) limita la probabilidad de ganar de las estrategias cuánticas y certifica el azar en ese límite, la puntuación ideal de XEB limita el rendimiento de los muestreadores cuánticos eficientes y certifica el azar cerca de ese valor.
Seguridad Incondicional: A diferencia de resultados previos que dependían de supuestos de dureza computacional o de la restricción del conocimiento del adversario (por ejemplo, no aprender el oráculo completo), este trabajo proporciona límites incondicionales contra un adversario que aprende el oráculo y posee entrelazamiento arbitrario.
Limitaciones: Los autores señalan que sus resultados se aplican al modelo de oráculo. Para dispositivos del mundo real (como los de [AAB+19]), las puntuaciones actuales están lejos de la ideal (por ejemplo, 1.002 frente a 2), lo que significa que las garantías actuales para el azar certificado en entornos experimentales dependen de supuestos diferentes y más débiles (por ejemplo, [AH23]). Además, para los estados aleatorios de Haar, el resultado requiere el oráculo de preparación de estado canónico en lugar del acceso a una unitaria completa, ya que un adversario que aprenda una unitaria aleatoria de Haar completa podría potencialmente correlacionar las salidas con las columnas de la unitaria.

En resumen, el artículo define rigurosamente los límites del muestreo cuántico eficiente, probando que la puntuación ideal es una barrera dura para los dispositivos eficientes y que aproximarse a esta barrera certifica casi todo el azar posible, incluso contra poderosos adversarios cuánticos.

Más como este