Finalmente, hubo un problema que solo las computadoras cuánticas pueden resolver

Durante años, los informáticos han estado buscando tareas de cierto tipo que solo una computadora cuántica podría resolver, pero no una computadora clásica, incluso de generaciones futuras. Y así encontraron uno de ellos.

En las primeras etapas del estudio de las computadoras cuánticas, los informáticos hicieron una pregunta, la respuesta a la cual, en su opinión, se suponía que revelaría una verdad profunda sobre las capacidades de estas máquinas futuristas. 25 años después, se encontró una respuesta. En un artículo publicado en mayo de 2018, los científicos informáticos Ren Rez y Avishai Tal ofrecieron pruebas convincentes de que la potencia informática de las computadoras cuánticas supera cualquier cosa que las computadoras clásicas puedan lograr.

Rez, profesor de la Universidad de Princeton y el Instituto de Ciencias Wiseman, así como Tal, un postdoctorado de la Universidad de Stanford, identificaron un tipo particular de problema computacional. Probaron, con una advertencia, que las computadoras cuánticas podían resolver el problema de manera efectiva, y las computadoras tradicionales estarían atascadas para siempre, intentando hacerlo. Los informáticos han estado buscando este problema desde 1993, cuando identificaron por primera vez la clase de tarea BQP , que incluye todas las tareas que una computadora cuántica puede resolver.

Desde entonces, esperaban contrastar la clase de tareas BQP conocida como PH, que incluye todas las tareas que se pueden realizar en cualquier computadora clásica, incluso la increíblemente avanzada desarrollada por alguna civilización del futuro. La posibilidad de tal contraste dependía de encontrar un problema que perteneciera a la clase BQP, pero no a la clase PH. Y ahora Rez y Tal lo han hecho.

Este resultado no hace que las computadoras cuánticas sean mejores que las clásicas desde un punto de vista práctico. Primero, los informáticos teóricos ya saben que las computadoras cuánticas son capaces de resolver cualquier tarea de la que son capaces las clásicas. Y los ingenieros están luchando para resolver el problema de crear una máquina cuántica útil. Pero el trabajo de Reza y Tal demuestra la diferencia en las categorías en las que se ubican las computadoras cuánticas y clásicas, y que incluso en un mundo en el que las computadoras clásicas han excedido los límites de cualquier sueño, las computadoras cuánticas aún pueden adelantarse a ellas.

Clases cuánticas

La tarea básica de la informática teórica es dividir las tareas en clases de complejidad. La clase de complejidad contiene todas las tareas que se pueden resolver con un recurso específico, como el tiempo o la memoria.

Los científicos, por ejemplo, han descubierto un algoritmo efectivo que verifica si un número es primo. Sin embargo, no pudieron encontrar un algoritmo efectivo para encontrar factores primos de grandes números. Por lo tanto, creen (aunque no pudieron probarlo) que estos dos problemas pertenecen a diferentes clases de complejidad.

Dos clases de dificultad famosas son P y NP. P es todas las tareas que una computadora clásica puede resolver rápidamente. (El problema "¿es el número primo?" Pertenece a P). NP incluye todas las tareas que una computadora clásica no necesariamente resuelve rápidamente, sino la exactitud de la solución existente, cualquiera de las cuales puede verificar rápidamente. ("¿Cuáles son los factores primos de un número?" Pertenece a NP). Los científicos creen que las clases P y NP son diferentes, pero la tarea de demostrar esta diferencia es el más difícil y el más importante de los problemas abiertos en esta área.


Un PH contiene un NP que contiene P. ¿Es el BQP una clase separada del PH?

En 1993, los informáticos Ethan Bernstein y Umesh Wazirani definieron una nueva clase de complejidad, que llamaron BQP, o "tiempo cuántico-polinómico con limitación de probabilidad de error". Definieron la clase como la que contiene todas las tareas de toma de decisiones (tareas con la respuesta "sí" o "no") que las computadoras cuánticas pueden resolver de manera efectiva. Casi al mismo tiempo, demostraron que las computadoras cuánticas son capaces de resolver todas las tareas que las clásicas son capaces de hacer. Es decir, BQP contiene todas las tareas contenidas en P.

Otro ejemplo de clases de tareas individuales. El problema del vendedor pregunta si un camino que pasa por ciertas ciudades es más corto que una distancia dada. Tal tarea está en NP. Una tarea más difícil pregunta si esta distancia es el camino más corto a través de estas ciudades. Tal tarea está en PH.

Sin embargo, no pudieron determinar si el BQP contiene tareas que no están en otra clase importante de tareas, conocida como PH o "jerarquía polinómica". PH es una generalización de NP. Contiene todas las tareas que se pueden obtener comenzando con una tarea de NP y complicandola, agregando declaraciones aclaratorias como "si" y "para todos". Las computadoras clásicas aún no pueden resolver la mayoría de los problemas de PH, pero esta clase puede considerarse una clase de problemas que las computadoras clásicas podrían resolver si resulta que P es equivalente a NP. En otras palabras, para comparar BQP y PH, es necesario determinar si las computadoras cuánticas tienen una ventaja sobre las computadoras clásicas, lo que permanecerá incluso si las computadoras clásicas de repente aprenden a resolver muchos más problemas de los que pueden resolver hoy.

"El PH es una de las clases de complejidad más simples que existen", dijo Scott Aaronson , especialista en TI de la Universidad de Texas en Austin. "Así que queremos saber el lugar de la computación cuántica en un mundo de complejidad clásica".

La mejor manera de separar las dos clases de dificultad es encontrar un problema que se pueda incluir en una de ellas y que no se incluya en la otra. Sin embargo, debido a una combinación de obstáculos fundamentales y técnicos, tal tarea fue muy difícil de encontrar.

Para encontrar una tarea que pertenezca a BQP, pero no a PH, debe definir algo a lo que "una computadora clásica, por definición, ni siquiera puede verificar efectivamente la respuesta, por no mencionar encontrarla", dijo Aaronson. "Esto elimina las muchas tareas con las que trabajamos en informática".

Preguntar oráculo

Desafío Supongamos que tenemos dos generadores de números aleatorios, cada uno de los cuales produce una secuencia de dígitos. Pregunta para la computadora: ¿son estas dos secuencias completamente independientes entre sí, o están de alguna manera imperceptiblemente conectadas (por ejemplo, ¿una secuencia se obtiene mediante la transformada de Fourier de la otra)? Aaronson introdujo esta tarea de "furrelación" en 2009 y demostró que pertenece a BQP. El segundo paso más difícil sigue siendo demostrar que la furrelación no está incluida en el PH.


Ran rez

En cierto sentido, esto es exactamente lo que hicieron Resu y Talu. Su trabajo separa BQP y PH con la ayuda de los llamados " oráculo " o "caja negra". Este es un resultado común en informática, al que los investigadores han recurrido cuando lo que quieren probar no se les da de ninguna manera.

La mejor manera de separar las clases de complejidad BQP y PH es medir el tiempo computacional requerido para resolver problemas de cada clase. Pero la informática no tiene "una comprensión profunda del tiempo real de computación o la capacidad de medirlo", dijo Henry Youn, un científico informático de la Universidad de Toronto.

En cambio, se está midiendo algo más en informática, que se cree que proporciona una comprensión del tiempo computacional que no se puede medir directamente. Los científicos calculan la cantidad de llamadas de computadora al "oráculo" para dar una respuesta a la pregunta. El oráculo parece dar pistas. No sabemos cómo los recibe, pero sabemos que son confiables.

Si su tarea es averiguar si hay una conexión secreta entre dos generadores de números aleatorios, puede hacer preguntas al oráculo como "¿cuál será el sexto número de cada generador?" Luego, debe comparar la potencia informática en función de la cantidad de indicaciones que necesita cada computadora para resolver el problema. Una computadora que necesita más pistas funciona más lentamente.

“En cierto sentido, entendemos este modelo mucho mejor. Ella habla más sobre información que sobre informática ”, dijo Tal.


Avishai Tal

El nuevo trabajo de Reza y Tal demuestra que una computadora cuántica necesitará muchas menos pistas para resolver un problema de furrelación que una clásica. Además, una computadora cuántica necesita solo una pista, a pesar de que PH no tiene un algoritmo para resolver este problema, incluso con un número ilimitado de pistas. "Esto significa que hay un algoritmo cuántico extremadamente eficiente que resuelve este problema", dijo Rez. "Pero si consideramos solo los algoritmos clásicos, incluso si llegamos a las clases más altas de algoritmos clásicos, no podrán hacer frente a ellos". Esto prueba que con el oráculo, la furrelación se refiere a tareas que pertenecen a BQP, pero no a PH.

Rez y Tal casi alcanzaron este resultado hace unos cuatro años, pero no pudieron dar un paso en la prueba futura. Y luego, solo un mes antes de la publicación, Tal escuchó sobre un nuevo trabajo sobre generadores de números pseudoaleatorios, y se dio cuenta de que las tecnologías de ese artículo solo dan lo que él y Rez necesitaban para terminar el suyo. "Era una pieza faltante", dijo Tal.

Las noticias sobre la separación de las clases BQP y PH se difundieron rápidamente. "El mundo de la complejidad cuántica está zumbando", escribió Lance Fortnau, un especialista en TI de la Universidad Tecnológica de Georgia el día después de la publicación del trabajo.

El trabajo da la confianza de que las computadoras cuánticas existen en un mundo informático separado de las clásicas (al menos por definición con el oráculo). Incluso en un mundo donde P es equivalente a NP, donde resolver el problema del vendedor ambulante es tan simple como encontrar la línea más adecuada en la hoja de cálculo, la prueba de Reza y Tal muestra que hay problemas que solo una computadora cuántica puede resolver.

"Incluso si P fuera equivalente a NP, incluso con una suposición tan fuerte", dijo Fortnau, "las computadoras cuánticas aún no se pondrán al día".