Yuvin Tan, de 18 años, demostró que las computadoras clásicas pueden resolver el "problema de recomendación" casi tan rápido como las computadoras cuánticas. Este resultado invalida uno de los mejores ejemplos de aceleración cuántica de cálculos.
Un adolescente de Texas asedió el desarrollo de la computación cuántica. En un artículo publicado este mes en Internet
, Yuvin Tan
, de 18 años, demostró que las computadoras comunes pueden resolver un problema computacional importante a una velocidad
potencialmente comparable a las computadoras cuánticas.
En su forma más práctica, el problema de la recomendación está relacionado con la forma en que servicios como Amazon y Netflix determinan qué productos pueden gustarle. Los informáticos lo consideraron
uno de los mejores ejemplos de tareas que se resolverían exponencialmente más rápido en las computadoras cuánticas, lo que enfatizó las
capacidades potenciales
de estas máquinas futuristas. Y ahora Tan refutó esta opinión.
"Fue uno de los ejemplos definitorios de la aceleración cuántica, y ahora ha desaparecido", dice Tang, quien se graduó de la Universidad de Texas en Austin en la primavera y comienza sus estudios de doctorado en otoño en la Universidad de Washington.
En 2014, a la edad de 14 años, Tang saltó a los grados 4, 5 y 6, e ingresó a la Universidad de Texas, donde se graduó en matemáticas y ciencias de la computación. En la primavera de 2017, Tan tomó un curso de información cuántica, impartido por
Scott Aaronson , un conocido investigador en el campo de la computación cuántica. Aaronson reconoció a un estudiante excepcionalmente talentoso en Tan y lo invitó a convertirse en su asesor en un proyecto de investigación independiente. Aaronson le dio a Tan varias tareas para elegir, incluido el tema de las recomendaciones. Tan la eligió un tanto a regañadientes.
"Dudé porque parecía bastante complicado, pero era la más simple de todas las tareas que me propuso", dijo Tan.
El objetivo de las recomendaciones es proporcionar recomendaciones sobre productos que puedan gustarle al usuario. Considera Netflix. Él sabe qué películas viste. Él sabe lo que vieron millones de sus usuarios. Con esta información, ¿es posible averiguar qué desea buscar más?
Estos datos se pueden representar en forma de una cuadrícula o matriz enorme, en la parte superior de la cual se enumeran todas las películas, en el lado están todos los usuarios, y dentro hay valores que miden cuánto le gustó a cada uno de los usuarios cada película. Un buen algoritmo producirá una lista de recomendaciones, detectando de manera rápida y precisa las similitudes entre películas y usuarios, y completando las celdas vacías de la matriz.
En 2016, los científicos informáticos
Iordanis Kerenidis y
Anupam Prakash publicaron un
algoritmo cuántico que resolvió el problema de recomendación exponencialmente más rápido que cualquiera de los algoritmos clásicos conocidos. Recibieron tal aceleración cuántica, en particular, debido a la simplificación del problema. En lugar de completar toda la matriz y determinar el único mejor producto para recomendar, se les ocurrió una manera de dividir a los usuarios en un pequeño número de categorías: ¿les gustan los éxitos de taquilla o el cine independiente? - y procesar los datos existentes de tal manera que dé una recomendación que simplemente sería bastante buena.
Cuando apareció el trabajo de Kerenidis y Prakash, había muy pocos ejemplos de problemas que las computadoras cuánticas debían resolver exponencialmente más rápido que las clásicas. En su mayor parte, estas tareas estaban especializadas: problemas estrechos diseñados específicamente para aprovechar las fortalezas de las computadoras cuánticas (incluido el problema de "
correlación " sobre el que ya escribimos). El trabajo de Kerenidis y Prakash fue interesante porque resaltó un problema real, importante para las personas, en el que las computadoras cuánticas superaron a las clásicas.
"Desde mi punto de vista, este fue uno de los primeros ejemplos de aprendizaje automático y procesamiento de big data, en el que demostramos que las computadoras cuánticas pueden hacer algo que aún no sabemos cómo hacer con los métodos clásicos", dijo Kerenidis, especialista en Informática del Instituto de París para la Investigación en Informática.
Kerenidis y Prakash demostraron que una computadora cuántica puede resolver el problema de las recomendaciones exponencialmente más rápido que cualquiera de los algoritmos conocidos, pero no han demostrado que no haya un algoritmo clásico rápido. Por lo tanto, cuando Aaronson comenzó a trabajar con Tan en 2017, planteó exactamente esa tarea: demostrar la ausencia de un algoritmo clásico rápido, confirmando la aceleración cuántica de Kerenidis y Prakash.
"Me pareció que este sería un punto importante que estableceremos para completar esta historia", dijo Aaronson, quien en ese momento creía que no existe un algoritmo clásico rápido.
Tang comenzó a trabajar en este otoño de 2017, con la esperanza de que la tarea de las recomendaciones sería el tema de su disertación. Durante varios meses, Tan intentó demostrar la imposibilidad de la existencia de un algoritmo clásico. Pasó el tiempo, y Tan comenzó a pensar que quizás existía tal algoritmo.
"Comencé a creer en la existencia del algoritmo clásico, pero no podía convencerme de esto, porque Scott pensaba que no existía y que era una autoridad para mí", dijo Tan.
Finalmente, cuando la fecha límite para la disertación ya se estaba acabando, Tan escribió una carta a Aaronson, donde confesó sus crecientes sospechas. "Tan esencialmente me escribió lo siguiente: creo que existe un algoritmo clásico rápido", dijo Aaronson.
A lo largo de la primavera, Tang escribió los resultados y trabajó con Aaronson para aclarar algunos pasos de la prueba. Descubierto por Tan, el algoritmo clásico rápido se inspiró en el algoritmo cuántico rápido encontrado por Kerenidis y Prakash dos años antes. Tan demostró que el muestreo cuántico utilizado en su algoritmo puede reproducirse en condiciones clásicas. El algoritmo de Tan, como el algoritmo de Kerenidis y Prakash, se ejecutó en tiempo pollogarítmico, es decir, el tiempo de cálculo se estimó por el logaritmo de parámetros tales como el número de usuarios y productos, y fue exponencialmente más rápido que cualquier otro de los algoritmos clásicos conocidos previamente.
Después de que Tan completó el algoritmo, Aaronson quería asegurarse de que fuera correcto antes de publicarlo. "Todavía estaba nervioso por el hecho de que si después de la publicación del trabajo de Tan resulta ser incorrecto, entonces el primer gran trabajo en la carrera de Tan resultará ser nada fácil", dijo Aaronson.
Aaronson planeó asistir a un taller de computación cuántica en la Universidad de California en Berkeley en junio. Las luminarias de esta área debían reunirse allí, incluidos Kerenidis y Prakash. Aaronson invitó a Than con él a Berkeley para presentar informalmente su algoritmo después de la parte oficial de la conferencia.
En la mañana del 18 y la mañana del 19 de junio, Tan dio dos conferencias, respondiendo preguntas de la audiencia. Después de cuatro horas, se llegó a un consenso: el algoritmo clásico de Tan se parece al correcto. Lo que muchos de los presentes no entendieron fue cómo Tan era joven. "No sabía que Yuvin tenía 18 años, y ciertamente no me lo parecía por los resultados de las conversaciones. Me pareció que Juvin estaba teniendo una conversación como un hombre adulto ", dijo Kerenidis. Ahora el algoritmo tendrá una revisión por pares formal antes de ser publicado.
Para la computación cuántica, el resultado de Tan es un paso atrás. O no Tang eliminó uno de los ejemplos más comprensibles y mejores de ventaja cuántica. Al mismo tiempo, el trabajo de Tan es otra evidencia de la existencia de una
interacción fructífera entre los estudios de algoritmos clásicos y cuánticos.
“Tang elimina la aceleración cuántica de Kerenidis y Prakash, pero en otro sentido, Tang contribuye a una gran mejora y se basa en su trabajo. Tang nunca habría ideado su algoritmo clásico si no hubieran publicado su cuanto ”, dijo Aaronson.