QAOA a escala utilitaria

Mira el video sobre QAOA a escala utilitaria de Olivia Lanes, o ábrelo en una ventana separada en YouTube.

Resumen de la lección:

Hasta ahora en este curso, esperamos haberte dado una base sólida del marco de trabajo y las herramientas necesarias para resolver problemas a escala utilitaria en una computadora cuántica. Ahora, por fin vamos a ver estas herramientas en acción.

En esta lección, vamos a ensuciarnos las manos con un ejemplo a escala utilitaria del problema Max-Cut, que es un famoso problema de teoría de grafos que consiste en encontrar la mejor manera de dividir un grafo en dos partes. Comenzaremos con un grafo simple de cinco nodos para desarrollar nuestra intuición sobre cómo una computadora cuántica puede ayudarnos a resolver el problema, y luego lo aplicaremos a una versión a escala utilitaria del problema.

Esta lección servirá como una visión general del enfoque que usamos para resolver este problema. No será una guía de código paso a paso. Sin embargo, junto con esta lección hay un tutorial con código real que puedes ejecutar para resolver el problema Max-Cut en una computadora cuántica.

El problema

Como recordatorio, no todos los problemas computacionales son adecuados para la computación cuántica. Los "problemas fáciles" no obtendrán ninguna ventaja de esta tecnología, porque las computadoras clásicas ya son perfectamente capaces de resolverlos.

Los tres casos de uso sobre los que somos más optimistas son:

1. simular la naturaleza
2. procesar datos con estructura compleja
3. optimización

Hoy nos centraremos en el tercer caso de uso: la optimización. En un problema de optimización, generalmente buscamos el valor más grande o más pequeño posible para una función dada. La dificultad de encontrar estos extremos con métodos clásicos puede crecer exponencialmente a medida que el tamaño del problema aumenta.

El problema de optimización que nos ocupa hoy se llama Max-Cut, y lo vamos a resolver usando un algoritmo llamado Quantum Approximate Optimization Algorithm (QAOA).

¿Qué es Max-Cut?

Comenzamos con un grafo, que consiste en una colección de vértices (o nodos), algunos de los cuales están conectados por aristas. En el problema, se nos pide dividir los nodos del grafo en dos subconjuntos "cortando" las aristas que los conectan. Queremos encontrar la partición que maximice el número de aristas cortadas de esta manera — de ahí el nombre, "Max-Cut".

Por ejemplo, la figura anterior muestra un grafo de cinco nodos con una solución Max-Cut a la derecha. Corta cinco aristas, que es lo mejor que se puede lograr con este grafo.

Dado que un grafo de cinco nodos es tan pequeño, no es muy difícil deducir el Max-Cut mentalmente o probando algunos cortes en un papel. Pero como puedes imaginar, el problema se vuelve cada vez más difícil a medida que crece el número de vértices — en parte porque el número de cortes posibles a considerar crece exponencialmente con el número de nodos. Y en cierto punto, esto se vuelve difícil incluso para las supercomputadoras con cualquier algoritmo clásico conocido.

Nos gustaría encontrar una manera de resolver el problema Max-Cut para estos grafos más grandes y complicados, porque el problema tiene muchas aplicaciones prácticas, como la detección de fraudes en finanzas, la agrupación de grafos, el diseño de redes y el análisis de redes sociales. Max-Cut suele aparecer como un subproblema dentro de un enfoque particular a un problema mayor. Por lo tanto, es mucho más común de lo que podríamos pensar ingenuamente.

La solución

Ahora vamos a explicar el enfoque que usamos para resolver el problema Max-Cut en una computadora cuántica. Lo haremos con un grafo simple de cinco nodos. Puedes seguir el tutorial del notebook de Python. Después de ese ejemplo simple, el tutorial te guiará a través de un ejemplo a escala utilitaria del problema.

El primer paso es crear nuestro grafo definiendo el número de nodos y las aristas que conectan dos nodos. Puedes hacerlo importando un paquete llamado rustworkx, como se muestra en el tutorial. El resultado será un grafo que se verá así:

Usaremos el marco de trabajo de patrones de Qiskit para encontrar las soluciones Max-Cut de este grafo en nuestra computadora cuántica.

Mapear

Necesitamos mapear el problema en nuestra computadora cuántica. Para hacer esto, observemos primero que maximizar el número de cortes en un grafo se puede escribir matemáticamente como:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

Donde $i$ y $j$ son nodos en el grafo, y $x_i$ y $x_j$ son 0 o 1, dependiendo de qué lado de la partición se encuentre cada nodo (un grupo se etiqueta como "0" y el otro como "1"). Cuando $x_i$ y $x_j$ están en el mismo lado de la partición, la expresión en la suma es igual a cero. Cuando están en lados opuestos, es decir, hay un corte entre ellos, la expresión es igual a uno. Por lo tanto, maximizar el número de cortes maximizará la suma.

También podemos invertir esto y buscar el mínimo multiplicando cada uno de los valores por menos uno.

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

Ahora estamos listos para mapear. Puede resultar intimidante pensar en cómo pasar de un grafo como el que acabamos de dibujar a un circuito cuántico. Pero lo haremos paso a paso.

Recuerda que vamos a intentar resolver Max-Cut usando QAOA. En la metodología QAOA, en última instancia queremos tener un operador (o, en otras palabras, un Hamiltoniano) que se usará para representar la función de costo de nuestro algoritmo híbrido, así como un circuito parametrizado (el ansatz) que usamos para representar las posibles soluciones al problema.

QUBO

Podemos tomar muestras de estas soluciones candidatas y luego evaluarlas usando la función de costo. Para hacer esto, aprovechamos una serie de reformulaciones matemáticas, incluida la notación de Optimización Binaria Cuadrática Sin Restricciones — o QUBO por sus siglas en inglés — que es una forma útil de codificar problemas de optimización combinatoria. En QUBO, queremos encontrar:

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

donde $Q$ es una matriz de $n\times n$ de números reales, y $n$ corresponde al número de nodos en nuestro grafo, que aquí es cinco.

Para aplicar QAOA, necesitamos formular nuestro problema como un Hamiltoniano — que es una función o matriz que representa la energía total de un sistema. Específicamente, queremos crear un Hamiltoniano de función de costo que tenga la propiedad de que el estado base corresponda al valor mínimo de la función. Entonces, para resolver nuestro problema de optimización, intentaremos preparar el estado base de $H$ en una computadora cuántica. Luego, tomar muestras de este estado producirá la solución a $\min 𝑓(𝑥)$ con alta probabilidad.

Mapeo a un Hamiltoniano de función de costo

Resulta que tenemos suerte, porque el problema QUBO está muy relacionado con, y de hecho es computacionalmente equivalente a, uno de los Hamiltonianos más famosos y ubicuos de la física: el Hamiltoniano de Ising.

Para escribir el problema QUBO como el Hamiltoniano de Ising, todo lo que necesitamos hacer es un simple cambio de variables:

$$x_i = \frac{1-z_i}{2}.$$

No vamos a recorrer todos los pasos aquí, pero están explicados en el notebook adjunto. Al final, la minimización de la expresión QUBO es la misma que la minimización de esta expresión:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

Reescribiendo de nuevo ligeramente, tenemos nuestro Hamiltoniano de función de costo, donde el mínimo de la expresión representa el estado base, Z es el operador de Pauli Z, y $b$ es un coeficiente escalar real:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

Ahora que tenemos nuestro Hamiltoniano, necesitamos reescribirlo en términos de operadores de Pauli ZZ de dos localidades, que podemos convertir fácilmente en puertas de dos qubits en nuestro circuito cuántico. Terminaremos con seis objetos — o cadenas de Pauli — donde cada uno corresponde a cada una de las seis aristas del grafo. Cada uno de los cinco elementos en una cadena representa una operación en un nodo — la identidad si el nodo no está conectado a esa arista en particular, y el operador de Pauli Z si lo está. En Qiskit, las cadenas de bits que representan qubits están indexadas al revés. Por ejemplo, una arista entre los nodos 0 y 1 se codifica como IIIZZ, y una arista entre 2 y 4 se codifica como ZIZII.

Construir el circuito cuántico

Con nuestro Hamiltoniano escrito en términos de operadores de Pauli, estamos listos para construir nuestro circuito cuántico, que nos permite tomar muestras de buenas soluciones usando una computadora cuántica:

El algoritmo QAOA se inspira en el Teorema Adiabático, que establece que si comenzamos en el estado base de un Hamiltoniano dependiente del tiempo, si el Hamiltoniano evoluciona lo suficientemente despacio y dado suficiente tiempo, el estado final será el estado base del Hamiltoniano final. El QAOA puede considerarse como la versión discreta y trotterizada de este Algoritmo Cuántico Adiabático, donde cada paso de Trotter representa una capa del algoritmo QAOA. Entonces, en lugar de evolucionar de un estado a otro, en cada capa alternaremos entre nuestro Hamiltoniano de función de costo y el llamado Hamiltoniano "mezclador", que cubriremos más adelante en esta lección.

La ventaja del QAOA es que es más rápido que el algoritmo cuántico adiabático, pero devuelve soluciones aproximadas en lugar de las óptimas. En el límite donde el número de capas tiende a infinito, el QAOA converge al caso QAA, pero por supuesto esto es computacionalmente muy costoso.

Para crear nuestro circuito cuántico, aplicaremos operadores alternantes, parametrizados por $\gamma$ y $\beta$, que representarán la discretización de la evolución temporal.

Entonces, las tres partes principales del circuito QAOA son:

1. el estado de prueba inicial, en gris, que es el estado base del mezclador, creado aplicando una puerta Hadamard a cada qubit
2. la evolución de la función de costo, que ya hemos discutido, en púrpura oscuro
3. la evolución bajo el Hamiltoniano mezclador, que aún no hemos cubierto, en púrpura claro.

Nuestro Hamiltoniano de partida se llama Mezclador porque su estado base es la superposición de todas las cadenas de bits posibles de interés: lo que impone una mezcla de todas las soluciones posibles al inicio.

El Hamiltoniano mezclador es la suma simple de operaciones de Pauli-X en cada nodo del grafo. Qiskit te permite usar un operador mezclador diferente y personalizado si lo deseas, pero aquí vamos a usar el estándar. Así que, de nuevo, puedes ver que con Qiskit se elimina mucho del trabajo, lo que hace que encontrar el Hamiltoniano mezclador y el estado inicial sea trivial. El único trabajo que tuvimos que hacer fue encontrar la función de costo.

Cada iteración de estos operadores se llama una capa. Estas capas pueden verse como una discretización de la evolución temporal del sistema, como se describió anteriormente. El patrón alternante proviene de la descomposición de Trotter y aproxima las funciones exponenciales de matrices no conmutativas. En general, cuantas más capas o pasos incluyamos, más cerca estaremos de la evolución temporal continua, como en el QAA, por lo que en teoría el resultado será más preciso. Pero para este ejemplo, comenzaremos tomando muestras con una sola capa. Recuerda que tanto el Hamiltoniano de función de costo como el mezclador están parametrizados; aún necesitamos encontrar los valores óptimos para $\gamma$ y $\beta.$

Optimizar

Si bien el circuito que acabamos de crear parece bastante simple y es útil para desarrollar una comprensión intuitiva, recuerda que el chip cuántico no entiende qué es la puerta QAOA. Necesitamos convertirlo en una serie de puertas "nativas" de uno y dos qubits que se puedan ejecutar directamente en el hardware. Las puertas nativas son aquellas que se pueden ejecutar directamente en los qubits. Se dice que esos circuitos están escritos en la Arquitectura del Conjunto de Instrucciones (ISA) del backend.

La librería de Qiskit ofrece una serie de pasadas de transpilación que se adaptan a una amplia variedad de transformaciones de circuitos. Queremos asegurarnos de que el circuito esté optimizado para nuestro propósito.

Recuerda de nuestra lección anterior que el proceso de transpilación implica varios pasos:

• Mapeo inicial de los qubits en el circuito (es decir, las variables de decisión) a qubits físicos en el dispositivo.
• Desenrollado de las instrucciones en el circuito cuántico a las instrucciones nativas del hardware que el backend entiende.
• Enrutamiento de cualquier qubit en el circuito que interactúe con qubits físicos que sean adyacentes entre sí.

Y como siempre, más detalles sobre esto se pueden encontrar en la documentación.

Sin embargo, antes de transpilar, necesitamos elegir en qué backend ejecutaremos nuestro circuito, ya que el transpilador optimiza de manera diferente para distintos procesadores. Esta es otra razón más por la que es importante usar un transpilador automatizado — no querrías pasar por el proceso laborioso de optimizar tu circuito a mano, solo para darte cuenta de que en realidad quieres ejecutarlo en un procesador diferente con propiedades distintas.

Pasa el backend de tu elección a través de la función del transpilador y especifica tu nivel de optimización. En el tutorial, seleccionarás el nivel 3, que es el más alto y exhaustivo.

¡Y con eso, tenemos un circuito transpilado listo para ejecutarse en hardware!

Ejecutar

Hasta ahora, transpilamos el circuito dejando los parámetros gamma y beta sin modificar — pero en realidad no podemos ejecutar el circuito sin especificar estos parámetros. En el flujo de trabajo de QAOA, los parámetros óptimos se encuentran en un bucle de optimización iterativo, donde ejecutamos una serie de evaluaciones del circuito y luego usamos un optimizador clásico para encontrar los parámetros óptimos 𝛽 y 𝛾. Sin embargo, necesitamos empezar desde algún punto, así que hacemos una estimación inicial de $\gamma=\pi/2$ y $\beta=\pi.$

Modos de ejecución

Ahora, casi estamos listos para ejecutar el circuito — ¡lo prometo! Pero primero, es importante señalar que puedes enviar tu trabajo de varias maneras diferentes, llamadas modos de ejecución.

• Modo Job: Se realiza una sola solicitud primitiva del estimador o del sampler sin un gestor de contexto. Los circuitos y entradas se empaquetan como bloques unificados de primitivas (PUBs) y se envían como una tarea de ejecución en la computadora cuántica.

• Modo Batch: Un gestor de múltiples trabajos para ejecutar eficientemente un experimento compuesto por un conjunto de trabajos independientes. Usa el modo batch para enviar múltiples trabajos primitivos simultáneamente.

• Modo Session: Una ventana dedicada para ejecutar una carga de trabajo de múltiples trabajos. Esto permite a los usuarios experimentar con algoritmos variacionales de una manera más predecible, e incluso ejecutar múltiples experimentos simultáneamente, aprovechando el paralelismo en la pila. Usa sesiones para cargas de trabajo iterativas o experimentos que requieran acceso dedicado. Consulta Ejecutar trabajos en una sesión para ver ejemplos.

Para un experimento QAOA, una sesión sería una buena opción si tienes acceso a ella, ya que necesitamos tomar muestras de nuestro circuito muchas veces con diferentes valores de parámetros para encontrar el óptimo.

Volviendo al problema de optimización. Necesitamos encontrar mejores valores de gamma y beta que nuestras primeras estimaciones aproximadas. Lo haremos introduciendo nuestra función de costo y estas estimaciones iniciales en un optimizador de scipy COBYLA.

Aquí puedes ver el valor de la función de costo a lo largo de las iteraciones. Comienza un poco errático, sube y baja, pero luego se estabiliza en un valor bajo. Usaremos los valores que scipy encontró que corresponden a la evaluación más baja de la función de costo.

Ahora que pudimos reducir nuestra función de costo encontrando mejores valores para nuestros parámetros, ejecutaremos nuestro circuito con los nuevos valores que encontramos para gamma y beta. Aquí he listado los valores específicos que estoy usando, pero recuerda que cuando tú lo intentes o simplemente vuelvas a ejecutar el mismo notebook del tutorial, estos valores podrían cambiar ligeramente. Ahora ejecutaremos nuestro circuito optimizado con estos valores y encontraremos nuestra solución candidata al problema Max-Cut.

En la etapa de post-procesamiento, analizaremos los datos y mostraremos estos resultados para ver si nuestro algoritmo cuántico encontró las soluciones correctas.

Post-procesar

Ahora grafiquemos un histograma de los datos para ver la solución final:

Las cadenas de bits representan cómo cada uno de los nodos fue dividido en dos grupos (etiquetados como "0" y "1") por el corte. Deberían existir cuatro soluciones que todas den el valor máximo de aristas cortadas. Estas cuatro se muestran en púrpura. Puedes ver de inmediato que 4 soluciones son mucho más probables que cualquiera de las otras. La cadena de bits de solución más alta, y por lo tanto más probable, es 0,1,0,1,1. (¡Recuerda — el orden de los qubits está invertido en las cadenas de bits del gráfico!)

A partir de este gráfico, podemos tomar la cadena de bits más probable y representarla como un grafo particionado, con el corte pasando por cinco aristas:

Entonces, esta es de hecho una solución Max-Cut. ¡Pero no es la única! Debido a la simetría de este grafo, existen múltiples soluciones correctas. En lugar de que los nodos 0 y 3 estén dentro del corte, podríamos incluir los nodos 2 y 4. Puedes ver que todo lo que tuve que hacer fue rotar mi corte para incluir estos nuevos puntos. El número de aristas cortadas sigue siendo cinco. Resulta que hay cuatro soluciones Max-Cut, ya que cada una de las dos soluciones que señalamos también tiene una solución "opuesta", donde los nodos púrpura son grises y los grises son púrpura — el corte sigue siendo el mismo, pero cada nodo efectivamente cambia al lado opuesto de la partición.

Miremos de nuevo el histograma y las cuatro soluciones más probables por un momento. Idealmente, serían cada una de las cuatro soluciones verdaderas de Max-Cut. El problema es que el algoritmo en realidad no identificó la cuarta y última solución como una de las 4 respuestas más probables. Fue la quinta más probable. La cuarta solución que identificó el algoritmo es incorrecta — si la dibujaras, verías que la solución solo tiene cuatro cortes.

Pero recuerda: este es un algoritmo aproximado. No es infalible y no es correcto el 100% de las veces. Tienes que emplear tu propio conocimiento y comprensión para verificar la coherencia de las soluciones.

Este error puede surgir de varios lugares:

1. Podría ser la naturaleza aproximada del propio algoritmo y el pequeño número de capas que empleé.
2. Podría ser un error de muestreo finito; esto podría reducirse si aumento el número de shots en mi experimento.
3. También podría ser un error de lectura, ya que la cuarta solución real difiere solo en un bit.

Este tipo de análisis de errores es lo que se necesita para convertirse en un practicante de la computación cuántica. Necesitas entender el rendimiento del hardware y cómo puede contribuir a ciertos tipos de errores y cómo corregirlos.

Sin embargo, no olvidemos que había 32 cadenas de bits posibles y que las cuatro soluciones reales estaban incluidas entre los cinco mejores candidatos. Y solo usamos dos capas para encontrar esto. En general, si quisiéramos aumentar nuestras posibilidades de encontrar el mejor Max-Cut cada vez, podríamos aumentar la profundidad de las capas. Hay algunas sutilezas en esto, pero eso es para una lección posterior.

A escala utilitaria

Ahora que has tenido un primer contacto con el proceso de resolver un pequeño problema Max-Cut en una computadora cuántica, te invito a hacerlo a escala. Sigue el tutorial enlazado para ver cuántos cortes puedes obtener en un grafo de 125 nodos.