Un estudio que demuestra la dificultad de simular circuitos cuánticos aleatorios para ordenadores clásicos

Las computadoras cuánticas, tecnologías que realizan cálculos que aprovechan los fenómenos de la mecánica cuántica, podrían eventualmente superar a las computadoras clásicas en muchos problemas computacionales y de optimización complejos. Si bien algunas computadoras cuánticas han logrado resultados notables en algunas tareas, su superioridad sobre las computadoras clásicas aún no se ha demostrado de manera concluyente y consistente.

Ramis Movassagh, investigador de Google Quantum AI, que anteriormente trabajó en IBM Quantum, realizó recientemente un estudio teórico destinado a demostrar matemáticamente las notables ventajas de las computadoras cuánticas. Su artículo publicado en Física de la naturalezamuestra matemáticamente que simular circuitos cuánticos aleatorios y estimar sus resultados se llama #P-hard para las computadoras clásicas (es decir, extremadamente difícil).

«Una pregunta clave en el campo de la computación cuántica es: ¿Son las computadoras cuánticas significativamente más poderosas que las clásicas?» Ramis Movassagh, quien realizó el estudio, dijo a Phys.org. «La conjetura de la supremacía cuántica (que rebautizamos como conjetura de la supremacía cuántica) dice que sí. Sin embargo, matemáticamente, era un gran problema abierto que tenía que ser probado rigurosamente».

Recientemente, los investigadores han intentado demostrar las ventajas de los ordenadores cuánticos sobre los clásicos de diversas formas, tanto mediante estudios teóricos como experimentales. La clave para demostrar esto matemáticamente es demostrar que a las computadoras clásicas les resulta difícil lograr los resultados de las computadoras cuánticas con alta precisión y un pequeño margen de error.

“En 2018, un colega dio una conferencia en el MIT en ese momento sobre un resultado reciente que intentaba proporcionar evidencia de la solidez del muestreo de circuitos aleatorios (RCS)”, explicó Movasagh. «RCS es una tarea que toma muestras de las salidas de un circuito cuántico arbitrario y Google acaba de sugerirla como un candidato principal para demostrar la primacía cuántica. Yo estaba entre la audiencia y nunca antes había trabajado en complejidad cuántica; de hecho, recuerdo que Como estudiante de posgrado, ¡juré que nunca trabajaría en esta área!»

La prueba matemática presentada por el colega de Movasag en el MIT en 2018 no resolvió de manera concluyente el antiguo problema de demostrar la prioridad cuántica, pero aun así representó un progreso significativo hacia ese objetivo. La prueba se logra mediante una serie de aproximaciones y el llamado truncamiento de series; Por tanto, fue algo indirecto e introdujo errores innecesarios.

«Me gusta conectar las matemáticas para resolver problemas grandes y abiertos, especialmente si las matemáticas son sencillas, menos conocidas por los expertos en el campo y hermosas», dijo Movasagh. «En este caso, sentí que tal vez podría encontrar una pista mejor, e ingenuamente pensé que si resolvía el problema de la manera correcta, podría ser capaz de resolver el gran problema abierto. Así que me puse a trabajar en ello. »

La prueba matemática presentada por Movasagh difiere significativamente de la presentada hasta ahora. Se basa en un nuevo conjunto de técnicas matemáticas que en conjunto muestran que las probabilidades de salida de un caso promedio (es decir, un circuito cuántico aleatorio) son tan difíciles como el peor de los casos (es decir, el más artificial).

«La idea es que se puede utilizar la ruta de Cayley propuesta en el artículo para interpolar entre dos circuitos arbitrarios cualesquiera, que en este caso está entre el peor de los casos y el caso promedio», dijo Movasagh. «Un camino de Cayley es una función algebraica de bajo orden. Dado que se sabe que el peor de los casos es #P difícil (es decir, un problema muy difícil), utilizando un camino de Cayley se puede interpolar el caso promedio y demostrar que los circuitos estocásticos son esencialmente tan difíciles como el peor de los casos con alta probabilidad».

A diferencia de otras demostraciones matemáticas obtenidas en el pasado, la demostración de Movasagh no implica aproximaciones y es bastante sencilla. Esto significa que permite a los investigadores relacionar explícitamente los errores en cuestión y medir su solidez (es decir, qué tan tolerantes a fallas son).

Desde que Movassagh encontró la evidencia por primera vez, su grupo de investigación y otros equipos la han estado probando y mejorando su solidez. Pronto podría proporcionar información adicional para estudios destinados a mejorar la evidencia o utilizarla para resaltar el potencial de las computadoras cuánticas.

«Hemos obtenido evidencia directa de la dificultad de estimar las probabilidades de salida de los circuitos cuánticos», dijo Movassagh. «Estos proporcionan barreras computacionales a las simulaciones clásicas de los circuitos cuánticos». Nuevas técnicas como la ruta de Cayley y la versión de función racional de Berlekemp-Gales «son de interés independiente para la criptografía cuántica, la computación, la complejidad y la teoría criptográfica». Actualmente, este es el camino más prometedor para refutar la Tesis de Turing de la Iglesia Ampliada, que es un objetivo inevitable de la teoría de la complejidad cuántica”.

El trabajo reciente de Movasagh es en gran medida una contribución importante a los esfuerzos de investigación en curso para explorar las ventajas de las computadoras cuánticas sobre las clásicas. En sus estudios futuros, planea aprovechar las pruebas existentes para demostrar matemáticamente el enorme potencial de las computadoras cuánticas para abordar problemas específicos.

«En mi próximo estudio, espero conectar este trabajo con la dificultad de otras tareas para mapear mejor la manejabilidad de los sistemas cuánticos», añadió Movasagh. «Estoy investigando aplicaciones de este trabajo, entre otras cosas, en criptografía cuántica. Y por último, pero no menos importante, espero demostrar la conjetura de la primacía cuántica y demostrar que la tesis extendida de Church-Turing es falsa».