¿Para qué problemas son adecuados los computadores cuánticos?

Mira el video sobre aplicaciones de la computación cuántica de Olivia Lanes, o ábrelo en una ventana separada en YouTube.

Introducción

En la lección anterior, nos sumergimos en profundidad en un único problema -- resolver el problema de optimización Max-Cut utilizando la formulación QUBO. Hoy tomaremos un camino diferente y discutiremos aplicaciones a corto plazo en un marco más amplio. Comenzaremos dándote una idea de cómo decidimos qué tipos de problemas podrían beneficiarse de una solución cuántica. Luego veremos algunos trabajos recientes de nuestra comunidad. Esto debería ayudarte a desarrollar una intuición para los diferentes tipos de problemas de computación cuántica y a comprender cómo los abordamos.

Dificultad clásica vs. cuántica

Antes de entrar en los ejemplos, hablemos primero de cómo examinamos y clasificamos la dificultad de diferentes problemas. Algunos problemas se resuelven fácilmente en un computador clásico, y no necesitamos un computador cuántico para ellos. Por otro lado, hay problemas muy difíciles para los cuales los computadores cuánticos son necesarios. Un ejemplo conocido es la factorización de números enteros enormes. El cifrado RSA se basa en la dificultad de este problema, y el algoritmo de Shor fue diseñado para resolverlo en un computador cuántico. Otro ejemplo es la búsqueda de una solución en un conjunto de datos no ordenado -- esto puede resolverse teóricamente mediante el algoritmo cuántico conocido como algoritmo de Grover. Sin embargo, la mayoría de los expertos coinciden en que estos tipos de algoritmos requieren la implementación de corrección de errores y la tecnología aún no está lista para ello.

Así que buscamos problemas que podamos abordar en algún punto intermedio entre muy fácil y muy difícil -- aquellos que los computadores cuánticos de hoy pueden manejar, pero que representan dificultades para los computadores clásicos.

Clases de complejidad

La dificultad de estos problemas se categoriza y analiza en un subcampo de la informática llamado teoría de la complejidad computacional. Hay una variedad de clases de complejidad diferentes en la computación clásica, pero algunas de las más fundamentales son:

• P: Problemas que son solubles en tiempo polinomial a medida que aumenta el tamaño del problema. Son fáciles de resolver.
• NP: Esto significa polinomial no determinista. Estos problemas no pueden resolverse necesariamente en tiempo polinomial, pero sus respuestas pueden verificarse en tiempo polinomial.
• NP-completo son los problemas más difíciles en NP y no tienen una solución polinomial conocida. Aquí viven problemas famosos como el problema del viajante y el juego Sudoku.
• BPP, o Problemas Polinomiales con Error Acotado, que pueden ser resueltos por un computador clásico probabilístico en tiempo polinomial dentro de un cierto margen de error.

Cuando se inventó el concepto de computación cuántica, muchos investigadores realizaron esfuerzos considerables para determinar qué clase de problemas estos nuevos tipos de computadores podrían resolver eficientemente. Se introdujo una nueva clase de problemas:

• BQP, o Problemas Polinomiales Cuánticos con Error Acotado. Este es el equivalente cuántico de BPP: es la clase de problemas de decisión que son solubles por un computador cuántico en tiempo polinomial con una pequeña probabilidad de error.

Todas estas clases viven dentro de una clase mayor que llamamos PSPACE. Arriba hay un diagrama de las relaciones supuestas entre algunas clases de complejidad, pero esto es matemáticamente muy difícil de demostrar definitivamente. Notarás que BQP no necesariamente se superpone con NP-completo. Sin embargo, existen enfoques de computación cuántica que intentan resolver problemas en NP-completo.

Un malentendido común es que no tiene sentido explorar soluciones cuánticas para problemas para los cuales no se ha encontrado una prueba matemática de aceleración cuántica. Pero encontrar una prueba matemática de que un algoritmo cuántico es más rápido que su contraparte clásica es difícil. Shor y Grover son dos de los pocos ejemplos hasta ahora donde esto se ha logrado. De hecho, la demostración rigurosa de que P y NP son diferentes es una de las preguntas abiertas más conocidas en toda la matemática, aunque toda la intuición sugiere que debe ser así.

Sin embargo, la forma en que un algoritmo escala con el crecimiento del tamaño del problema -- lo que se refleja en la clase de complejidad -- no es siempre la característica más relevante de un algoritmo. Esta escalabilidad es a menudo el escenario del peor caso. Es perfectamente posible que en la práctica no encontremos el escenario del peor caso con mayor frecuencia.

Solo porque las demostraciones de dificultad son complicadas no significa que no podamos progresar. Introducimos la idea de soluciones heurísticas. Si eres experimentalista, probablemente conoces y amas este tipo de soluciones. Una heurística es cualquier enfoque para resolver un problema que es pragmático pero no necesariamente óptimo, ya que las soluciones no necesitan ser óptimas para ser útiles. Piensa, por ejemplo, en aplicaciones financieras. Aún no hemos encontrado una aceleración exponencial para la mayoría de los algoritmos financieros donde se podría usar lo cuántico, pero no necesitamos una solución óptima. En finanzas, incluso una solución que sea solo un 0,1% más eficiente podría significar miles de millones de dólares de ganancia.

Los computadores cuánticos de hoy y sus límites

Entonces, ¿cómo sabemos qué casos de uso y problemas podrían ser adecuados actualmente para la computación cuántica? ¿Hay buenas razones para creer que la utilidad cuántica o incluso la ventaja cuántica pueden encontrarse ahora o en un futuro cercano?

Quizás es más fácil empezar nombrando las cosas que el problema definitivamente no debería tener. No puede requerir una cantidad enorme de qubits. Todavía no tenemos procesadores con miles o millones de qubits disponibles. Esa es una de las principales razones por las que el algoritmo de Shor y similares están todavía tan lejos de la realización. Los circuitos tampoco pueden ser demasiado profundos. El límite de profundidad del circuito depende de muchos factores, pero en general, si tu experimento requiere una profundidad que aún no has visto en la literatura, probablemente no funcionará. Y finalmente, aún no pueden implementarse algoritmos que sabemos que requieren corrección de errores.

Todas estas limitaciones se abordan en la hoja de ruta de IBM Quantum®, y esperamos alcanzar la corrección de errores a principios de la década de 2030. Por ahora, sin embargo, debemos buscar experimentos que utilicen la mayoría de los qubits actualmente disponibles en un QPU. También enfatizamos la importancia de la mitigación de errores y la supresión de errores. Y finalmente, debería haber una extensión obvia a futuras aplicaciones que serían importantes para la sociedad y que en última instancia podrían llevarnos a una ventaja cuántica.

Áreas de aplicación y casos de uso

Hablemos ahora sobre algunos ejemplos de casos de uso que caen en tres categorías principales que hemos identificado como las más probables para resultados favorables a corto y mediano plazo:

1. Simulaciones de la naturaleza. Los métodos clásicos actuales de simulaciones atómicas y moleculares están limitados por descripciones matemáticas ineficientes de la estructura atómica. Almacenar y manipular un estado cuántico requiere exponencialmente muchos recursos en un computador clásico, pero puede hacerse eficientemente en un computador cuántico. Esto podría conducir a desarrollos en secuestro de CO₂, baterías alternativas o la invención de nuevos medicamentos. Algunos algoritmos particularmente relevantes en esta área son: el Variational Quantum Eigensolver (VQE), que se utiliza para estimar ciertas propiedades de un material como los estados de equilibrio o de energía mínima; el algoritmo de Time Dynamics Simulation (TDS), que se utiliza para estimar funciones de respuesta o propiedades espectrales de materiales; y un recién llegado, Sample-based Quantum Diagonalization (SQD), del cual creemos que escucharemos mucho más en un futuro cercano.

2. Optimización. Esta área es ubicua en la computación, por lo que los casos de uso son numerosos y variados. Algunos ejemplos que escuchamos frecuentemente son la optimización de carteras en finanzas, el diseño industrial y la distribución y cadena de suministro. El algoritmo más común que probablemente escucharás en el contexto de las finanzas es el que ya hemos tratado extensamente: el Quantum Approximate Optimization Algorithm o QAOA.

3. Quantum Machine Learning. Esta área ha generado mucho entusiasmo en los últimos años, pero es probable que QML no sea tan útil tan pronto como la simulación. Sin embargo, hay algunos algoritmos impresionantes en desarrollo para abordar algunos casos de uso muy importantes. Algunos de estos posibles casos de uso son el procesamiento de lenguaje natural, el análisis de tráfico de red e incluso la detección de fraude en transacciones financieras. Los algoritmos relevantes en esta área son la Quantum Support Vector Machine (QSVM), las Quantum Neural Networks (QNN) y las Quantum Generative Adversarial Networks.

Dentro de estas amplias áreas de aplicación, la comunidad ve el beneficio de que grupos colaboren centrándose en un tema más específico. IBM® ha lanzado una iniciativa llamada Working Groups para ayudar a los colaboradores a encontrarse mutuamente y crear sinergias productivas en cuatro áreas específicas: salud y ciencias de la vida, materiales y computación de alto rendimiento (HPC), física de altas energías y optimización. Recientemente también se creó un quinto Working Group sobre sostenibilidad.

Ahora vamos a examinar más de cerca algunos problemas que han sido trabajados recientemente por algunos de estos Working Groups. El objetivo principal aquí no es entender cada detalle de un experimento -- eso puede ser difícil incluso para expertos cuando el artículo queda ligeramente fuera de su área de especialización. El objetivo es simplemente desarrollar una intuición para los tipos de problemas para los que los computadores cuánticos son adecuados y cómo los abordamos. Y si te interesa, te animamos a leer los artículos completos.

Caso de uso 1: Simulación de la dinámica de hadrones

Primero, profundizaremos en un artículo del grupo de Martin Savage en la Universidad de Washington, titulado Quantum Simulations of Hadron Dynamics in the Schwinger Model Using 112 Qubits.

Aunque no seas físico de altas energías, quizás estés familiarizado con el término "hadrón", como en el Gran Colisionador de Hadrones (LHC), el enorme acelerador de partículas con una circunferencia de 27 km que finalmente permitió observar el bosón de Higgs. Un hadrón es una partícula subatómica compuesta formada por otras partículas pequeñas llamadas quarks. Algunos ejemplos de hadrones son los neutrones y los protones.

Para contexto: el LHC fue construido para permitir el estudio de la física fundamental haciendo colisionar partículas a energías extremadamente altas. Con el LHC, los científicos esperan aprender más sobre el universo temprano y las leyes fundamentales de la naturaleza. En principio, las interacciones de estas partículas podrían simularse de principio a fin con un computador cuántico suficientemente potente. Aún no estamos del todo ahí, pero estamos progresando.

El modelo de Schwinger es un modelo popular y sencillo utilizado para simular algunas de estas dinámicas. Es un modelo que describe el comportamiento de electrones y positrones interactuando en 1+1D a través de fotones, es decir, en tiempo y una dimensión espacial. El modelo tiene muchas similitudes con la cromodinámica cuántica (QCD), que describe cómo interactúan los quarks y hadrones, pero la QCD es extremadamente difícil de simular. Por lo tanto, el modelo de Schwinger se usa a menudo como modelo de juguete para investigar algunos fenómenos que comparten ambos.

Para entender por qué abordaron este problema, planteémonos una serie de preguntas.

Primero, ¿por qué tenían razones para creer que la simulación de esto en un computador cuántico funcionaría en absoluto? En este caso, los electrones y positrones en el modelo de Schwinger tienen un efecto de apantallamiento que hace que las correlaciones entre fermiones distantes disminuyan exponencialmente con la distancia. Esto significa que no hay tantas interacciones de largo alcance necesarias de un qubit en un lado del chip al otro, lo cual se sabe que es muy propenso a errores. Así que esto es ideal para el hardware que tenemos hoy.

A continuación: ¿Por qué es de interés este tema? La física de altas energías es generalmente de gran interés. La gente ha estado dispuesta a gastar miles de millones de dólares para construir el LHC, y muchos miles de científicos y técnicos en todo el mundo han dedicado sus carreras a este campo. Aunque el modelo de Schwinger es simplista y no está diseñado para tres dimensiones espaciales, sigue siendo una simplificación útil de la teoría completa.

Finalmente: ¿Cómo se realizó este trabajo, o cómo abordaríamos el problema si quisiéramos continuar este trabajo? En los experimentos de simulación, VQE es uno de los enfoques más comunes, y el primer paso es casi siempre el mismo: preparar el estado fundamental. En este caso, se trata de un estado de vacío. En este experimento utilizan una nueva versión de VQE llamada SC-ADAPT-VQE (que significa Scalable Circuits - Adaptive Derivative-Assembled Pseudo-Trotter ansatz-VQE), para preparar tanto el estado fundamental como el paquete de ondas del hadrón sobre ese vacío. El siguiente paso consiste en dejar que los hadrones evolucionen en el tiempo. Finalmente, se identifican y miden los observables de interés.

Si estos pasos -- aparte de la parte del paquete de ondas del hadrón -- suenan algo familiares, es porque son muy similares a lo que cubrimos en el ejemplo de QAOA en la lección anterior. Comenzamos en un estado conocido (aquí el estado de vacío) y luego lo dejamos evolucionar en el tiempo con una serie de hamiltonianos exponenciados. Muchos algoritmos variacionales siguen este enfoque general. Una gran diferencia aquí, sin embargo, es que creamos el paquete de ondas del hadrón centrado en nuestro circuito antes de dejarlo evolucionar.

Entonces, ¿cómo creamos el paquete de ondas? Sobre el vacío, un hadrón puede excitarse creando un par fermión-antifermión en sitios de red adyacentes. Al preparar una superposición de tales hadrones en diferentes posiciones, se puede preparar un paquete de ondas arbitrario. Los autores centraron su paquete de ondas en el medio del circuito para observar la evolución sin alcanzar un límite.

Pero recuerda: el juego al trabajar con QPUs ruidosos es mantener la profundidad del circuito manejable. Para ello, el protocolo SC-ADAPT-VQE utiliza simetrías y jerarquías en escalas de longitud para determinar circuitos cuánticos de baja profundidad para la preparación de estados. Esto produce un ansatz con un número menor de parámetros y por lo tanto una menor profundidad.

El experimento se realizó en un dispositivo IBM Quantum Heron e incluyó varios tipos de mitigación y supresión de errores: Dynamical Decoupling, Zero Noise Extrapolation, Pauli Twirling y una técnica recientemente desarrollada llamada Operator Decoherence Renormalization.

Arriba hay una figura del artículo que muestra el observable de interés, el condensado quiral, que es esencialmente una fase superfluida de los hadrones. Podemos ver el paquete de ondas en el centro de los sitios de red designados para este experimento. Las líneas negras son los resultados libres de errores de la simulación clásica (computacionalmente costosa), mientras que los puntos con barras de error son los resultados del computador cuántico IBM de 133 qubits Torino.

Vemos dos pasos de tiempo diferentes en la evolución del paquete de ondas. En el tiempo $t=1$, el condensado quiral es estrecho y localizado, y también concuerda bien con la simulación clásica. En $t=14$, está mucho más extendido. La comparación con el simulador ya no es tan perfecta, pero aún se puede reconocer una muy buena concordancia entre teoría y datos, lo cual es alentador.

En resumen, este es un ejemplo muy interesante del tipo de trabajo de simulación que quizás no pensarías inicialmente en aplicar la computación cuántica, pero que muestra un verdadero potencial. No es perfecto, pero no necesitas ser un experto en física de partículas para ver que el computador cuántico predice con precisión la propagación hacia el exterior del paquete de ondas, que es exactamente lo que esperaríamos. Con suerte, el trabajo futuro en esta área continuará, y los físicos de altas energías seguirán encontrando formas de incorporar la computación cuántica en sus flujos de trabajo. El objetivo es resolver problemas teóricos difíciles con mayor precisión y usar experimentos para confirmar o descartar teorías, con la esperanza de descubrir nueva física, construir detectores mejorados y llegar a una mejor comprensión de la naturaleza en su nivel más fundamental.

Caso de uso 2: Optimización de un vidrio de espín de Ising

Nuestro siguiente ejemplo se centra en la optimización y será un análisis profundo de un artículo llamado Bias-Field Digitized Counterdiabatic Quantum Optimization, realizado por miembros del equipo de Kipu Quantum y la Universidad del País Vasco en España.

En el artículo, los autores desarrollaron un nuevo método de optimización y lo aplicaron para encontrar el estado fundamental de un vidrio de espín de Ising. Como ya se discutió, muchos problemas de optimización combinatoria pueden reformularse como la resolución de estados de baja energía de hamiltonianos de Ising. El modelo de Ising describe la interacción de una disposición de espines microscópicos. En algunos regímenes, el modelo predice que los espines se comportan como un vidrio, donde los momentos magnéticos están desordenados por encima de una llamada "temperatura de congelación".

Comenzamos como antes con una serie de definiciones. La primera es contradiabático (counterdiabatic), que es un tipo de evolución que suprime los efectos no adiabáticos de un sistema, independientemente de lo rápido que ocurran estos procesos. Recuerda el teorema adiabático del episodio anterior -- normalmente necesitas evolucionar un sistema muy lentamente si quieres que permanezca en el estado fundamental. Eso es un gran problema, porque cuanto más lento necesitamos evolucionar las cosas, más tiempo tenemos para errores. El Counterdiabatic Driving (CD) tiene como objetivo combatir esto añadiendo términos que contrarrestan estas excitaciones no deseadas. La idea básica es acelerar todo el experimento y reducir la profundidad del circuito suprimiendo excitaciones que podrían causar transiciones no deseadas.

Ahora pasamos al otro término técnico del título: el campo de sesgo (bias field). Otros algoritmos iterativos, como VQE, introducen parámetros clásicos en los estados y usan optimizadores clásicos para buscar en el espacio de parámetros de alta dimensión el conjunto de parámetros que produce un valor esperado mínimo para un hamiltoniano fijo. En este caso, en lugar de eso, varían el hamiltoniano cada vez y se mueven adiabáticamente desde un caso conocido al caso de interés. Para cambiar el hamiltoniano, simplemente aplican el valor esperado de Pauli-Z de una iteración directamente como campo de sesgo en el hamiltoniano para la siguiente iteración. De esta manera, dirigen la dinámica hacia la solución real sin necesidad de optimizadores clásicos.

Entonces, ¿por qué es interesante este experimento? Los vidrios de espín de Ising son de interés fundamental en la física, pero este nuevo enfoque es aún más general. Podría aplicarse a muchos problemas de optimización, por lo que el artículo es de amplio interés.

¿Y por qué pensamos que funcionaría? El algoritmo que propusieron acelera la evolución para reducir la profundidad del circuito mientras suprime las transiciones no adiabáticas. Además, no depende de subrutinas de optimización clásica, lo que puede llevar a un problema que conduce a mesetas áridas y al estancamiento en mínimos locales. Finalmente, los autores también se aseguran de alinear las interacciones en el hamiltoniano del problema con la conectividad del hardware en los QPUs reales, lo cual es siempre muy importante.

¿Cómo funciona este método entonces? De nuevo, no usa optimizadores clásicos, a diferencia de la mayoría de los otros algoritmos cuánticos iterativos. En su lugar, el algoritmo Bias-Field Digitized Quantum Optimization refina incrementalmente el estado fundamental y lo acerca cada vez más al estado finalmente evolucionado, alimentando la solución de cada iteración como entrada para la siguiente. Combinado con los protocolos contradiabáticos, podemos hacer esto incluso con circuitos cuánticos de poca profundidad, que deberían funcionar sin problemas en hardware ruidoso.

Cuando se realizó el experimento, los autores decidieron ejecutar el algoritmo en el computador cuántico IBM de 127 qubits Brisbane. A continuación hay una figura que muestra la 8.ª iteración del algoritmo de optimización para una instancia de vidrio de espín de vecinos más cercanos generada aleatoriamente en 100 qubits. Comparan los resultados idealizados de simulación clásica de DCQO y BF-DCQO, así como el resultado experimental ejecutado en el computador cuántico. También muestran el resultado de un solucionador clásico llamado Gurobi como referencia. Con solo 10 iteraciones, BF-DCQO proporciona una mejora drástica en comparación con DCQO. Aunque el resultado experimental es algo diferente del resultado ideal debido al ruido, el rendimiento sigue siendo mejor que el DCQO ideal. Esto demuestra que se siguen logrando avances significativos en la optimización cuántica y que por primera vez se reportan buenos resultados para más de 100 qubits.

Caso de uso 3: Predicción de la estructura secundaria del ARNm

Finalmente, discutiremos un artículo de Moderna Pharmaceuticals titulado mRNA Secondary Structure Prediction Using Utility-Scale Quantum Computers.

Primero, un breve repaso sobre el ARNm. El ARN mensajero es un tipo de ARN involucrado en la síntesis de proteínas. Esencialmente, lee las instrucciones dadas por el ADN. La estructura secundaria del ARNm es cómo se pliega la cadena, como se muestra en el diagrama de abajo. Y el problema de predicción de la estructura secundaria del ARNm es el problema de encontrar el plegamiento más estable de la secuencia de bases o nucleótidos que componen el ARN: adenina (A), citosina (C), uracilo (U) y guanina (G). La imagen de abajo muestra algunas estructuras de plegamiento comunes que se encuentran en el ARNm; cada color representa un tipo diferente de estructura secundaria. Lo que hace que una estructura sea más favorable que las otras no se comprende bien; solo podemos calcular qué estructura produce la menor energía libre en comparación con el estado desplegado. Y aquí es exactamente donde entran los computadores cuánticos.

Entonces, ¿por qué son importantes las estructuras secundarias del ARNm? Una predicción precisa de estas no solo es crucial para comprender el ADN y nuestros genes, sino también para el diseño de terapias basadas en ARN, como la vacuna contra el COVID-19.

Se sabe desde hace mucho tiempo que este es un enorme problema de optimización para los computadores clásicos, debido a la gran cantidad de configuraciones posibles. Para algunas configuraciones, se sabe que es un problema NP-completo. Sin embargo, en un computador cuántico podemos formular la predicción de la estructura secundaria como un problema de optimización binaria -- algo que sabemos cómo manejar. Además, ya había evidencia en la literatura de predicciones precisas de ARN en pequeños dispositivos cuánticos y simuladores cuánticos. Pero, ¿funcionaría también en hardware más grande?

Este experimento se realizó con el llamado Conditional Value at Risk Variational Quantum Eigensolver, que es una modificación de un algoritmo VQE tradicional y pretende lograr una mejor convergencia.

El gráfico de arriba muestra la distribución de las probabilidades de medición de las cadenas de bits muestreadas con las energías correspondientes para una instancia de 42 nucleótidos y 80 qubits. Aquí las cadenas de bits simbolizan emparejamientos de nucleótidos. Muestra que la cadena de bits de menor energía que encontró el computador cuántico coincide con la del solucionador clásico de comparación -- esto es excelente. También se muestra la estructura de plegamiento óptima de esta cadena de nucleótidos basada en la cadena de bits de menor energía encontrada por el computador cuántico.

Conclusión

Esperamos que estos tres casos de uso te hayan dado suficiente contexto para entender cómo se ve el trabajo de vanguardia en este campo actualmente, y la confianza para probar nuevos experimentos cuánticos que quizás no habrías intentado antes.

Recuerda: la computación cuántica no es adecuada para todos los problemas. Y eso es en realidad solo un testimonio de lo buenos que nos hemos vuelto en la computación clásica. Solo porque creas que puedes aplicar la computación cuántica a un problema no significa que producirá resultados interesantes; debes considerar la escalabilidad.

La profundidad del circuito es un arma de doble filo. La necesitamos para hacer un trabajo interesante que los computadores clásicos no pueden hacer, pero por ahora no podemos aumentar demasiado la profundidad porque el ruido del hardware reducirá la fidelidad. Se trata de encontrar ese punto óptimo y saber que es un objetivo en movimiento. Así que tómate un tiempo hasta la próxima lección para pensar en un problema que hayas encontrado en tu investigación y cómo podrías abordarlo con lo que hemos aprendido hasta ahora. Y oye, tu solución no tiene por qué funcionar, y eso está bien. Para eso hacemos investigación.