En 1994, un matemático descubrió cómo hacer que una computadora cuántica hiciera algo que ninguna computadora clásica ordinaria podría hacer. El trabajo reveló que, en principio, una máquina basada en las reglas de la mecánica cuántica podría descomponer eficientemente un gran número en sus factores primos, una tarea tan difícil para una computadora clásica que constituye la base de gran parte de la seguridad de Internet actual.
Siguió una oleada de optimismo. Tal vez, pensaron los investigadores, podamos inventar algoritmos cuánticos que puedan resolver una gran variedad de problemas diferentes.
Pero el progreso se estancó. “Ha sido una trayectoria un poco fastidiosa”, dijo Ryan O´Donnell de la Universidad Carnegie Mellon. “La gente decía: 'Esto es increíble, estoy seguro de que obtendremos todo tipo de otros algoritmos increíbles'. No." Los científicos descubrieron aceleraciones dramáticas solo para una clase única y limitada de problemas dentro de un conjunto estándar llamado NP, lo que significa que tenían soluciones eficientemente verificables, como el factoring.
Así fue durante casi tres décadas. Luego, en abril, los investigadores inventado un tipo de problema fundamentalmente nuevo que una computadora cuántica debería poder resolver exponencialmente más rápido que una clásica. Implica calcular las entradas de un proceso matemático complicado, basado únicamente en sus salidas desordenadas. Aún no se ha determinado si el problema es único o es el primero en una nueva frontera de muchos otros.
“Hay una sensación de emoción”, dijo Vinod Vaikuntanathan, científico informático del Instituto Tecnológico de Massachusetts. “Mucha gente está pensando en qué más hay ahí fuera”.
Los científicos informáticos intentan comprender qué hacen mejor las computadoras cuánticas mediante el estudio de modelos matemáticos que las representan. A menudo, imaginan un modelo de una computadora cuántica o clásica emparejada con una máquina calculadora idealizada llamada oráculo. Los oráculos son como funciones matemáticas simples o programas de computadora, tomando una entrada y escupiendo una salida predeterminada. Pueden tener un comportamiento aleatorio, generando "sí" si la entrada cae dentro de un cierto rango aleatorio (digamos, 12 a 67) y "no" si no es así. O pueden ser periódicas, de modo que una entrada entre 1 y 10 devuelve "sí", 11 a 20 produce "no", 21 a 30 produce "sí" nuevamente, y así sucesivamente.
Digamos que tienes uno de estos oráculos periódicos y no sabes el período. Todo lo que puede hacer es alimentarlo con números y ver qué produce. Con esas restricciones, ¿qué tan rápido podría una computadora encontrar el punto? En 1993, Daniel Simon, entonces en la Universidad de Montreal, descubrió que un algoritmo cuántico podía calcular la respuesta a un problema estrechamente relacionado exponencialmente más rápido que cualquier algoritmo clásico.
El resultado permitió a Simon determinar uno de los primeros indicios de dónde se podía esperar una superioridad dramática para las computadoras cuánticas. Pero cuando envió su trabajo a una importante conferencia, fue rechazado. Sin embargo, el documento interesó a un miembro joven del comité del programa de la conferencia: Pedro Shor, quien en ese momento estaba en Bell Laboratories en Nueva Jersey. Shor descubrió que podía adaptar el algoritmo de Simon para calcular el período de un oráculo, si lo tenía. Luego se dio cuenta de que podía adaptar el algoritmo una vez más para resolver una ecuación que se comporta de manera similar a un oráculo periódico: la ecuación que describe la factorización, que es periódica.
El resultado de Shor fue histórico. El algoritmo cuántico que descubrió podía reducir rápidamente números gigantes a sus factores primos constituyentes, algo que ningún algoritmo clásico conocido puede hacer. En los años siguientes, los investigadores descubrieron otros algoritmos cuánticos eficientes. Algunos de ellos, como el algoritmo de Shor, incluso proporcionaron una ventaja exponencial, pero nadie pudo demostrar una ventaja cuántica dramática en ningún problema NP que no fuera periódico.
Esta escasez de progreso llevó a dos informáticos, De Scott Aaronson de la Universidad de Texas, Austin, y Andris Ambainis de la Universidad de Letonia, para hacer una observación. Las pruebas de la ventaja cuántica siempre parecían depender de oráculos que tenían algún tipo de estructura no aleatoria, como la periodicidad. En 2009, ellos conjeturado que no podía haber aceleraciones dramáticas en problemas NP que fueran aleatorios o no estructurados. Nadie pudo encontrar una excepción.
Su conjetura puso un límite a los poderes de las computadoras cuánticas. Pero solo decía que no hubo aceleraciones dramáticas para un tipo específico de problema NP no estructurado, aquellos con respuestas de sí o no. Si un problema implicaba encontrar respuestas cuantitativas más específicas, lo que se conoce como problema de búsqueda, la conjetura no se aplicaba.
Con eso en mente, los investigadores takashi yamakawa de los Laboratorios de Informática Social de NTT y marca zhandry de NTT Research y la Universidad de Princeton decidieron experimentar con un problema de búsqueda específico, introducido en 2005 por Oded Regev.
Imagina un conjunto de veletas que apuntan todas en la misma dirección. Dale a cada uno de ellos un empujón medido, luego deja que una ráfaga de viento influya en su dirección. Regev quería determinar, en función de sus direcciones finales, hacia dónde apuntaban todos inicialmente. Problemas como este llegaron a llamarse "aprendizaje con errores", porque el empuje y el viento actúan como una fuente de error aleatorio en la dirección original. Existe evidencia de que es difícil de resolver tanto para algoritmos clásicos como cuánticos.
Yamakawa y Zhandry modificaron la configuración. Modificaron la fuerza de esos empujones iniciales, haciéndolos más predecibles. También hicieron que el viento fuera determinado por un oráculo aleatorio, de modo que en ciertos casos era aún más aleatorio pero en otros estaba completamente inactivo.
Con estas modificaciones, los investigadores descubrieron que un algoritmo cuántico podría encontrar de manera eficiente la dirección inicial. También demostraron que cualquier algoritmo clásico debe ser más lento por un factor exponencial. Al igual que Shor, adaptaron su algoritmo para resolver una versión real del problema, que reemplaza el oráculo con una ecuación matemática real.
Los informáticos todavía están trabajando para comprender y desarrollar el problema. Vaikuntanathan lo compara con uno diferente que surge cuando se realiza la compresión de datos: cuando se comprime la información, dos bits pueden comprimirse accidentalmente en el mismo lugar, sobrescribiéndolos. El problema de predecir esas colisiones de antemano, para poder evitarlas, tiene cierta semejanza. “Esa es una clase de problemas que básicamente se ven así”, dijo. "Tal vez estos problemas se puedan resolver cuánticamente".
Había esperanzas de que un problema no estructurado como el nuevo pudiera resolverse incluso en las versiones incipientes de las computadoras cuánticas actuales, proporcionando así un medio para probarlas. La idea era que los problemas no estructurados podrían necesitar menos recursos para programarse o ser menos sensibles al ruido, dado que ya son aleatorios. Pero hasta ahora, el nuevo problema todavía parece demasiado avanzado para que lo resuelvan las computadoras cuánticas existentes. “Es un problema extraño. No había pensado en definirlo”, dijo Aaronson. “Pero en retrospectiva, tiene algunas características muy buenas”.
El resultado proporciona el primer ejemplo de una ventaja cuántica dramática en un problema NP no estructurado. ¿Podría haber muchos otros problemas que el mundo cuántico cambie de prácticamente irresolubles a solucionables? Ahora hay más razones para pensar así.
“De alguna manera anuló nuestras creencias sobre en qué tipo de problemas podrían ser buenas las computadoras cuánticas”, dijo O'Donnell.
