Un nuevo resultado de complejidad computacional muestra que un verificador clásico de tiempo polinomial puede validar computaciones cuánticas arbitrarias de tiempo polinomial, con un probador honesto eficiente y sin suposiciones criptográficas, siempre que se trabaje en presencia de un oráculo clásico. El protocolo construido es de moneda pública, con completitud perfecta y un error de solidez de como mucho 1/4, y se aplica a un lenguaje que queda fuera de la jerarquía polinomial pero que se decide exactamente en tiempo polinomial cuántico. Según los autores, es la primera vez que se demuestra que un lenguaje con un sistema de pruebas de estas características queda fuera de AM respecto de un oráculo.

El trabajo aborda una pregunta abierta en la frontera entre computación cuántica y verificación clásica: si un verificador puramente clásico puede certificar el resultado de un cálculo cuántico sin confiar en suposiciones computacionales. El lenguaje construido es una variante del muestreo de Fourier recursivo, en la que tablas de código codifican secretos que direccionan tablas de datos. Las tablas se evalúan de forma recursiva y el oráculo almacena únicamente las hojas. El algoritmo cuántico recupera cada secreto exactamente, mientras que el verificador comprueba de forma recursiva los secretos del probador contra entradas aleatorias de la tabla de código.

La recursión restringe la entrada de manera correlacionada: un mismo secreto fija los bits de código y elige la coordenada libre, lo que impide aplicar el lema de conmutación de Håstad. Para salvar este obstáculo, los autores demuestran un teorema de conmutación propio para estas restricciones, que podría tener interés independiente. Como consecuencia, para instancias de altura suficiente, ningún circuito de profundidad constante y tamaño 2^poly(n) cambia su salida con probabilidad superior a 2^(-Ω(n)) cuando la respuesta de una instancia aleatoria se altera modificando una sola hoja.

El protocolo es además eficiente en un sentido cuantitativo: para cualquier función computable en tiempo polinomial no acotada, puede elegirse el oráculo de modo que el número de mensajes y de consultas al oráculo del algoritmo cuántico, del verificador y del probador honesto queden acotados por esa función del tamaño de la entrada. El número de mensajes es óptimo salvo un factor constante, ya que para un oráculo adecuado todo sistema de pruebas interactivas del lenguaje necesita al menos una fracción constante de los mensajes del protocolo en infinitos tamaños de entrada.