Algoritmos cuánticos conquistando un nuevo tipo de problema

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 dividir 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 actual en Internet.

Siguió una ola de optimismo. Tal vez, pensaron los investigadores, podríamos inventar algoritmos cuánticos capaces de resolver una amplia gama de problemas diferentes.

Pero el progreso se ha estancado. "Ha sido una trayectoria un poco decepcionante", dijo Ryan O'Donnell de la Universidad Carnegie Mellon. "La gente decía: 'Eso es increíble, estoy seguro de que vamos a tener todo tipo de otros algoritmos increíbles'. " No. Los científicos encontraron aceleraciones dramáticas solo para una clase única y limitada de problemas de un conjunto estándar llamado NP, lo que significa que tenían soluciones comprobables de manera eficiente, como la factorización.

Ese fue el caso durante casi tres décadas. Luego, en abril, los investigadores idearon un tipo de problema fundamentalmente nuevo que una computadora cuántica debería poder resolver exponencialmente más rápido que una computadora clásica. Implica calcular las entradas de un proceso matemático complicado, basado únicamente en sus salidas codificadas. Queda por determinar si el problema es aislado o si es el primero de una nueva frontera entre muchos otros.

"Hay una sensación de emoción", dijo Vinod Vaikuntanathan, científico informático del Instituto de Tecnología de Massachusetts. "Mucha gente piensa en qué más hay".

Los científicos informáticos tratan de comprender qué hacen mejor las computadoras cuánticas mediante el estudio de los 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, toman una entrada y escupen una salida predeterminada. Pueden comportarse aleatoriamente, mostrando "sí" si la entrada está dentro de un cierto rango aleatorio (digamos, 12 a 67) y "no" si no lo está. O pueden ser periódicas, de modo que una entrada entre 1 y 10 devuelva "sí", 11 a 20 devuelva "no", 21 a 30 devuelva "sí" nuevamente, y así sucesivamente.

Suponga que tiene uno de estos oráculos periódicos y no sabe el período. Todo lo que puede hacer es darle algunos números y ver qué produce. Con estas 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 una de las primeras pistas sobre la espectacular superioridad de las computadoras cuánticas. Pero cuando envió su trabajo a una importante conferencia, fue rechazado. El artículo, sin embargo, interesó a un miembro joven del comité del programa de la conferencia: Peter Shor, quien estaba en Bell Laboratories en Nueva Jersey en ese momento. Shor luego descubrió que podía adaptar el algoritmo de Simon para calcular el período de un oráculo, si tuviera uno. 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 es histórico. El algoritmo cuántico que descubrió podía reducir rápidamente números gigantes a sus factores primos constituyentes, lo 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 ninguno pudo demostrar una ventaja cuántica dramática sobre un problema NP que no era periódico.

Esta falta de progreso llevó a dos informáticos, Scott Aaronson de la Universidad de Texas, Austin, y Andris Ambainis de la Universidad de Letonia, a hacer una observación. La evidencia de la ventaja cuántica siempre pareció depender de los oráculos que tenían algún tipo de estructura no aleatoria, como la periodicidad. En 2009, asumieron que no podría haber aceleraciones dramáticas en problemas de NP aleatorios o no estructurados. Nadie pudo encontrar una excepción.

Su conjetura limita los poderes de las computadoras cuánticas. Pero solo estaba diciendo que no hubo aceleraciones dramáticas para un tipo específico de problema de NP no estructurado: aquellos con sí ...