Separating Quantum and Classical Advice with Good Codes

1. Introducción y Problema

El artículo aborda dos preguntas fundamentales en la teoría de la complejidad cuántica que han permanecido abiertas durante mucho tiempo:

1. ¿Son las pruebas cuánticas más poderosas que las clásicas? Específicamente, ¿son distintas las clases de complejidad QMA (Quantum Merlin-Arthur, con pruebas cuánticas) y QCMA (Quantum Classical Merlin-Arthur, con pruebas clásicas)?
2. ¿Son los consejos (advice) cuánticos más poderosos que los clásicos? ¿Son distintas las clases BQP/qpoly (algoritmos cuánticos con consejos cuánticos) y BQP/poly (algoritmos cuánticos con consejos clásicos)?

Hasta la fecha, las separaciones incondicionales entre estas clases eran imposibles de demostrar sin oráculos (funciones de caja negra) debido a que implicarían resultados mayores como $P \neq PSPACE$. Trabajos anteriores habían logrado separaciones usando oráculos cuánticos (unitarios) o oráculos clásicos bajo modelos restringidos, pero una separación clásica incondicional para BQP/qpoly vs BQP/poly permanecía resuelta.

El objetivo de este trabajo es proporcionar la primera separación incondicional de oráculo clásico tanto para QMA vs QCMA como para BQP/qpoly vs BQP/poly, utilizando una prueba conceptual y técnicamente más simple que trabajos previos recientes (como Bostanci et al., STOC 2026).

2. Metodología y Construcción Técnica

La metodología se basa en una modificación del Problema de Intersección de Códigos (Code Intersection Problem) introducido por Yamakawa y Zhandry, combinado con el uso de códigos con propiedades excepcionales de recuperación de listas (list-recovery).

A. El Problema de Intersección de Códigos Generalizado

El problema central consiste en encontrar un codeword (palabra de código) $v$ en un código $C$ tal que, dado un hash $H$, se cumpla $H(v) = x$.

• En QMA: Un verificador puede recibir un estado cuántico de prueba que codifica superposiciones de preimágenes de $H$ y codewords de $C$, permitiendo resolver el problema eficientemente.
• En QCMA: Un verificador recibe una cadena clásica. El desafío es demostrar que ninguna cadena clásica de tamaño polinomial puede permitir al verificador distinguir entre instancias "SÍ" (donde el conjunto de soluciones es grande) y "NO" (donde es pequeño).

B. Uso de Códigos Multiplicidad (Multiplicity Codes)

A diferencia de trabajos anteriores que usaban códigos Reed-Solomon doblados (FRS), los autores utilizan Códigos Multiplicidad Univariables.

• Propiedad Clave 1 (Recuperación de Listas): Estos códigos tienen propiedades de recuperación de listas casi óptimas. Esto significa que si un algoritmo clásico intenta "adivinar" múltiples soluciones (codewords) y sus hashes, la cantidad de símbolos que debe acertar crece linealmente con el número de soluciones, haciendo la probabilidad de éxito exponencialmente pequeña.
• Propiedad Clave 2 (Distancia del Dual): Los códigos duales tienen buena distancia, lo que permite la decodificación eficiente necesaria para el algoritmo cuántico.

C. Oráculos Sesgados (Biased Oracles)

Un obstáculo técnico importante es que los códigos multiplicidad tienen una tasa relativa sub-constante, lo que implica que su código dual tiene una distancia relativa sub-constante. Esto haría que la decodificación fallara con ruido aleatorio estándar.

• Solución: Los autores introducen oráculos sesgados. En lugar de usar funciones hash completamente aleatorias, definen $H$ de manera que el valor 0 aparezca con una probabilidad $p \gg 1/2$.
• Restricción de Entrada: El problema se restringe a entradas $x$ que tienen baja peso de Hamming (específicamente, $x$ seguido de muchos ceros). Esto asegura que el "ruido" en el problema de decodificación cuántica sea manejable para el código dual, permitiendo que el algoritmo cuántico (QMA) funcione, mientras que la estructura sesgada no ayuda al verificador clásico a adivinar las soluciones.

D. Argumento de Muestreo (Sampling Argument)

Para separar QCMA de QMA, el argumento central es el siguiente:

1. Si existiera un verificador QCMA exitoso, se podría construir un algoritmo "adivínador" (Guesser) que, sin hacer consultas al oráculo, genera pares $(x, v)$ válidos (donde $v \in C$ y $H(v)=x$) con alta probabilidad.
2. Este algoritmo funcionaría simplemente simulando al verificador, midiendo una consulta aleatoria y añadiendo el resultado a un conjunto de soluciones conocidas.
3. Debido a las propiedades de recuperación de listas de los códigos multiplicidad, para generar $\ell$ soluciones distintas, el algoritmo debe acertar $\Omega(\ell \cdot n)$ símbolos específicos.
4. Dado el sesgo del oráculo, la probabilidad de adivinar correctamente todos estos símbolos es exponencialmente pequeña, contradiciendo la existencia del verificador QCMA.

3. Contribuciones Clave

1. Separación Incondicional QMA vs QCMA: Demuestran que existe un oráculo clásico $\mathcal{O}$ tal que $QMA^\mathcal{O} \not\subseteq QCMA^\mathcal{O}$. Su prueba es más simple que la de trabajos recientes que utilizaban "Forrelation espectral" y técnicas de física matemática.
2. Primera Separación Incondicional BQP/qpoly vs BQP/poly: Extienden su resultado para mostrar $BQP^\mathcal{O}/qpoly \not\subseteq BQP^\mathcal{O}/poly$. Esto es significativo porque, a diferencia de la separación de pruebas, la separación de consejos no es trivialmente equivalente y requiere manejar la naturaleza "confiada" del consejo.
3. Simplificación Técnica: Reemplazan la complejidad de los oráculos basados en transformadas de Fourier (Forrelation) por un problema de búsqueda en TFNP (Total Function NP) basado en códigos, lo que facilita la extensión al modelo de consejos.
4. Uso de Códigos Multiplicidad: Introducen el uso de códigos multiplicidad y oráculos sesgados para superar las limitaciones de distancia de los códigos duales, una innovación técnica crucial para hacer viable el algoritmo cuántico.

4. Resultados Principales

• Teorema 1.1: Existe un oráculo clásico $\mathcal{O}$ tal que $QMA^\mathcal{O} \not\subseteq QCMA^\mathcal{O}$.
• Teorema 1.2: Existe un oráculo clásico $\mathcal{O}$ tal que $BQP^\mathcal{O}/qpoly \not\subseteq BQP^\mathcal{O}/poly$.
• Mejora Estructural: La separación no solo distingue las clases, sino que separa $NP^\mathcal{O} \cap coNP^\mathcal{O} \cap BQP^\mathcal{O}/qpoly$ de $BQP^\mathcal{O}/poly$, indicando una diferencia estructural profunda con oráculos anteriores basados en problemas QMA-completos.

5. Significado e Impacto

• Resolución de Problemas Abiertos: Cierra una brecha importante en la teoría de la complejidad cuántica al proporcionar la primera separación clásica para el problema de los consejos cuánticos vs clásicos.
• Simplicidad Conceptual: La prueba evita el uso de técnicas pesadas de física cuántica (como el aprendizaje de Hamiltonianos) y se basa en principios de teoría de códigos y probabilidad, lo que la hace más accesible y potencialmente generalizable.
• Implicaciones Criptográficas: La separación entre QMA y QCMA está relacionada con primitivas criptográficas como el dinero cuántico (quantum money) y el software protegido contra copias. Un oráculo que separa estas clases sugiere que existen estados cuánticos que son verificables pero no clonables (o no generables clásicamente), lo cual es fundamental para la seguridad de estos esquemas.
• Nuevas Direcciones: El trabajo sugiere que la "estructura" en los oráculos (como la recuperación de listas) puede ser una herramienta más potente que el "azar" puro (como en Forrelation) para separar clases de complejidad cuántica.

En resumen, este artículo demuestra que, en un mundo relativizado, la información contenida en un estado cuántico (ya sea como prueba o como consejo) es intrínsecamente más poderosa que cualquier información clásica de tamaño polinomial, utilizando una construcción elegante basada en la teoría de códigos avanzados y oráculos sesgados.