QAOA a escala industrial

Vea el vídeo sobre QAOA a escala comercial de Olivia Lanes, o ábralo en una ventana aparte en YouTube.

---

Resumen de la lección:

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

En esta lección, nos pondremos manos a la obra con un ejemplo a gran escala del problema del corte máximo, un famoso problema de la teoría de grafos que trata de cómo dividir un grafo en dos de la mejor manera posible. Empezaremos con un gráfico sencillo de cinco nodos para hacernos una idea de cómo un ordenador cuántico puede ayudarnos a resolver el problema; después, aplicaremos esto a una versión del problema a escala industrial.

Esta lección servirá para ofrecer una visión general del enfoque que seguimos para resolver este problema. Esto no va a ser un repaso del código. Sin embargo, junto con esta lección hay un tutorial con código real que puedes ejecutar para resolver el problema del corte máximo en un ordenador cuántico.

---

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 los ordenadores clásicos ya son perfectamente buenos resolviéndolos.

Los tres casos de uso que exploramos con más optimismo son:

1. simular la naturaleza
2. tratamiento de 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 mayor o el menor valor posible para una función dada. La dificultad de encontrar estos extremos con los métodos clásicos puede aumentar exponencialmente a medida que crece el tamaño del problema.

El problema de optimización que nos ocupa hoy se denomina «corte máximo», y lo vamos a resolver mediante un algoritmo conocido como «algoritmo cuántico de optimización aproximada» (QAOA).

¿Qué es Max-Cut?

Empezamos con un grafo, que consiste en un conjunto de vértices (o nodos), algunos de los cuales están conectados por aristas. En el problema, se nos pide que dividamos los nodos del grafo en dos subconjuntos «cortando» los arcos que los conectan. Queremos encontrar la partición que maximice el número de aristas que se cortan de esta manera; de ahí el nombre de «corte máximo»

Por ejemplo, la figura anterior muestra un grafo de cinco nodos con una solución de corte máximo a la derecha. Corta a través de cinco aristas, que es lo mejor que se puede hacer con este grafo.

Dado que un grafo de cinco nodos es tan pequeño, no resulta demasiado difícil calcular el corte máximo de cabeza o probando algunos cortes en un papel. Pero, como puedes imaginar, el problema se vuelve cada vez más difícil a medida que aumenta el número de vértices, en parte porque el número de cortes posibles que hay que considerar crece exponencialmente con el número de nodos. Y llega un momento en que esto resulta difícil incluso para los superordenadores con los algoritmos clásicos conocidos.

Nos gustaría encontrar una forma de resolver el problema del corte máximo en estos grafos más grandes y complejos, ya que este problema tiene numerosas aplicaciones prácticas, entre las que se incluyen la detección de fraudes en el sector financiero, la agrupación de grafos, el diseño de redes y el análisis de redes sociales. El problema «Max-cut» suele aparecer como un subproblema dentro de un enfoque concreto de un problema más amplio. Así pues, es mucho más habitual de lo que podríamos pensar ingenuamente.

---

La solución

Ahora vamos a explicar el método que utilizamos para resolver el problema del corte máximo en un ordenador cuántico. Lo haremos con un gráfico sencillo de cinco nodos. Puedes seguir el tutorial utilizando el cuaderno de Python. Tras este sencillo ejemplo, el tutorial te guiará a través de un ejemplo a gran escala del problema.

El primer paso es crear nuestro grafo definiendo el número de nodos y las aristas que conectan dos nodos. Puede hacerlo importando un paquete llamado rustworkx, como se muestra en el tutorial. El resultado será un gráfico con el siguiente aspecto:

Utilizaremos el marco de patrones Qiskit para hallar las soluciones de corte máximo para este grafo en nuestro ordenador cuántico.

Correlación

Necesitamos mapear el problema en nuestro ordenador cuántico. Para ello, observemos primero que la maximización del número de cortes en un grafo puede escribirse 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 del grafo, y $x_i$ y $x_j$ son 0 o 1, dependiendo de en qué lado de la partición se encuentre cada nodo (un grupo está etiquetado 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 de la suma es igual a cero. Cuando están en lados opuestos, por lo que 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 darle la vuelta y buscar el mínimo multiplicando cada uno de los valores por uno negativo.

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

Ahora, estamos listos para mapear. Puede ser un poco desalentador pensar en cómo pasar de un gráfico como el que acabamos de dibujar a un circuito cuántico. Pero iremos paso a paso.

Recuerda que vamos a intentar resolver el problema del corte máximo utilizando QAOA. En la metodología QAOA, nuestro objetivo final es disponer de un operador (o, en otras palabras, un hamiltoniano) que sirva para representar la función de coste de nuestro algoritmo híbrido, así como de un circuito parametrizado (el ansatz) que utilicemos para representar las posibles soluciones al problema.

QUBO

Podemos tomar una muestra de estas soluciones candidatas y luego evaluarlas utilizando la función de coste. Para ello, utilizamos una serie de reformulaciones matemáticas, incluida la notación de optimización binaria cuadrática no restringida (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 $n\times n$ de números reales, $n$ corresponde al número de nodos de nuestro grafo, aquí, cinco.

Para aplicar el QAOA, tenemos que formular nuestro problema como un Hamiltoniano, que es una función o matriz que representa la energía total de un sistema. En concreto, queremos crear una función de coste hamiltoniana que tenga la propiedad de que el estado base corresponda al valor mínimo de la función. Así pues, para resolver nuestro problema de optimización, intentaremos preparar el estado fundamental de $H$ en un ordenador cuántico. Entonces, el muestreo de este estado dará la solución a $\min 𝑓(𝑥)$ con una alta probabilidad.

Mapeo a una función de coste hamiltoniano

Resulta que estamos de suerte, porque el problema QUBO está estrechamente relacionado, 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 tenemos que hacer es un simple cambio de variables:

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

No vamos a repasar aquí todos los pasos, pero están explicados en el cuaderno 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 y tenemos nuestra función de coste Hamiltoniano, donde el mínimo de la expresión representa el estado básico, Z es el operador Z de Pauli, 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 ZZ Pauli 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 de una cadena representa una operación sobre un nodo: la identidad si el nodo no está conectado a esa arista concreta, y el operador Z de Pauli si lo está. En Qiskit, las cadenas de bits que representan qubits se indexan hacia atrá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.

Construye 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 muestrear buenas soluciones utilizando un ordenador cuántico:

El algoritmo QAOA se inspira en el Teorema Adiabático, que afirma que si empezamos en el estado fundamental de un hamiltoniano dependiente del tiempo, si el hamiltoniano evoluciona con suficiente lentitud, y dado el tiempo suficiente, el estado final será el estado fundamental del hamiltoniano final. QAOA puede considerarse como la versión discreta, trotterizada de este Algoritmo Adiabático Cuántico, donde cada paso trotter representa una capa del algoritmo QAOA. Así que en lugar de evolucionar de un estado a otro, en cada capa, vamos a cambiar hacia adelante y hacia atrás entre nuestra función de coste Hamiltonian y un llamado "mezclador" Hamiltonian, que vamos a cubrir más adelante en esta lección.

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

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

Así pues, las tres partes principales del circuito QAOA son:

1. el estado inicial de prueba, en gris, que es el estado de tierra del mezclador, creado aplicando una puerta Hadamard a cada qubit
2. la evolución de la función de coste, de la que ya hemos hablado, en morado oscuro
3. la evolución bajo el Hamiltoniano mezclador, que aún no hemos tratado, en color morado claro.

Nuestro Hamiltoniano inicial se llama Mezclador porque su estado base es la superposición de todas las posibles cadenas de bits de interés: por lo tanto, impone una mezcla de todas las soluciones posibles al principio.

El Hamiltoniano del mezclador es la simple suma de las operaciones Pauli-X en cada nodo del grafo. Qiskit le permite utilizar un operador mezclador diferente, personalizado si lo desea, pero vamos a utilizar el estándar aquí. Así que, de nuevo, se puede ver que con Qiskit, gran parte del trabajo se elimina para nosotros, haciendo que llegar con el Hamiltoniano mezclador y el estado inicial sea trivial. El único trabajo que tuvimos que hacer fue encontrar la función de coste.

Cada iteración de estos operadores se denomina capa. Estas capas pueden considerarse una discretización de la evolución temporal del sistema, como se ha descrito anteriormente. El patrón alterno procede de la descomposición 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 en tiempo continuo, como en QAA, por lo que, en teoría, más preciso será el resultado. Pero para este ejemplo, empezaremos por muestrear con una sola capa. Recuerde que tanto la función de costes Hamiltonian como el mezclador están parametrizados, pero aún tenemos que encontrar los valores óptimos para $\gamma$ y $\beta.$

Optimizar

Aunque el circuito que acabamos de crear parece bastante sencillo y es útil para construir una comprensión intuitiva, recuerda que el chip cuántico no entiende qué es la puerta QAOA. Tenemos que convertir esto en una serie de puertas "nativas" de uno y dos qubits que puedan ejecutarse directamente en el hardware. Las puertas nativas son las que se pueden realizar directamente en los qubits. Se dice que estos circuitos están escritos en la Arquitectura de Conjuntos de Instrucciones (ISA) del backend.

La biblioteca Qiskit ofrece una serie de pases de transpilación que se adaptan a una amplia gama de transformaciones de circuitos. Queremos asegurarnos de que el circuito está optimizado para nuestro propósito.

Recordemos que el proceso de transpilación consta de varias etapas:

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

Y como siempre, encontrará más detalles al respecto en la documentación.

Antes de transpilar, sin embargo, tenemos que elegir en qué backend vamos a ejecutar nuestro circuito, ya que el transpilador optimiza de manera diferente para diferentes procesadores. Esta es otra razón por la que es importante utilizar un transpilador automático: no querrás pasar por el largo proceso de optimizar tu circuito a mano, sólo para darte cuenta de que en realidad quieres ejecutar tu circuito en un procesador diferente con propiedades diferentes.

Pase el backend de su elección a través de la función de transpilador y especifique su nivel de optimización. En el tutorial, seleccionarás el nivel 3, que es el más alto y completo.

Y con eso, ¡tenemos un circuito transpilado que está listo para ser ejecutado en hardware!

Ejecutar

Hasta ahora, hemos transpilado el circuito sin especificar los parámetros gamma y beta, pero no podemos ejecutar el circuito sin especificar estos parámetros. En el flujo de trabajo de QAOA, los parámetros óptimos de QAOA se encuentran en un bucle de optimización iterativo, en el que ejecutamos una serie de evaluaciones de circuitos y luego utilizamos un optimizador clásico para encontrar los parámetros 𝛽 y 𝛾 óptimos. Sin embargo, tenemos que empezar por algún sitio, así que hacemos una estimación inicial de $\gamma=\pi/2$ y $\beta=\pi.$

modalidades de ejecución

Ahora, estamos casi listos para correr el circuito - ¡lo prometo! Pero antes, es importante tener en cuenta que puedes enviar tu trabajo de varias formas distintas, que se denominan modos de ejecución.

• Modo de ejecución: se realiza una única llamada a la primitiva Estimator o Sampler sin un gestor de contexto. Los circuitos y las entradas se agrupan en bloques primitivos unificados (PUB) y se envían al ordenador cuántico como una tarea de ejecución.

• Modo por lotes: Un gestor multitrabajo para ejecutar eficientemente un experimento compuesto por un paquete de trabajos independientes. Utilice el modo por lotes para enviar varios trabajos primitivos simultáneamente

• Modo sesión: Una ventana dedicada para ejecutar una carga de trabajo multijob. Esto permite a los usuarios experimentar con algoritmos variacionales de forma más predecible, e incluso ejecutar múltiples experimentos simultáneamente, aprovechando el paralelismo de la pila. Utilice sesiones para cargas de trabajo iterativas o experimentos que requieran un acceso dedicado. Consulte 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 muestrear nuestro circuito muchas veces con diferentes valores de parámetros para encontrar el óptimo.

Volvamos al problema de optimización. Tenemos que encontrar mejores valores de gamma y beta que nuestras primeras suposiciones aproximadas. Para ello, introduciremos nuestra función de costes y estas conjeturas iniciales en un optimizador de scipy COBYLA.

Aquí puede ver el valor de la función de coste a lo largo de las iteraciones. Empieza un poco inestable y sube y baja, pero luego se estabiliza en un valor bajo. Utilizaremos los valores que scipy encontró que corresponden a la evaluación más baja de la función de coste.

Ahora que hemos logrado reducir nuestra función de coste al encontrar mejores valores para nuestros parámetros, ejecutaremos nuestro circuito utilizando los nuevos valores que hemos hallado para gamma y beta. He indicado aquí los valores concretos que estoy utilizando, pero recuerda que, cuando lo pruebes tú mismo o incluso si simplemente vuelves a ejecutar el mismo cuaderno de tutoriales, estos valores podrían variar ligeramente. Ahora ejecutaremos nuestro circuito optimizado con estos valores y hallaremos la solución candidata a nuestro problema de corte máximo.

En la fase de posprocesamiento, analizaremos los datos y mostraremos los resultados para comprobar si nuestro algoritmo cuántico ha encontrado las soluciones correctas.

Postprocesamiento

Ahora vamos a trazar 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. Debe haber cuatro soluciones que den todas el valor máximo de bordes cortados. Estos cuatro se muestran en color morado. Se ve enseguida que 4 soluciones son mucho más probables que cualquiera de las otras. La solución de cadena de bits más alta, y por tanto la más probable, es 0,1,0,1,1. (Recuerda: el orden de los qubits se invierte en las cadenas de bits de la trama)

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

Así pues, se trata efectivamente de una solución de corte máximo. ¡Pero no es el único! Debido a la simetría de este gráfico, hay varias soluciones correctas. En lugar de que los nodos 0 y 3 queden dentro del corte, podríamos incluir los nodos 2 y 4. Como puedes ver, lo único que tuve que hacer fue girar mi corte para incluir estos nuevos puntos. El número de aristas cortadas sigue siendo cinco. Resulta que hay un máximo de cuatro soluciones de corte, ya que cada una de las dos soluciones que hemos señalado tiene también una «contraparte», en la que los nodos morados son grises y los nodos grises son morados; así, el corte sigue siendo el mismo, pero cada nodo pasa, en la práctica, al lado opuesto de la partición.

Echemos un vistazo de nuevo al histograma y a las cuatro soluciones más probables durante un momento. Lo ideal sería que fueran las cuatro soluciones de corte máximo verdaderas. El problema es que, en realidad, el algoritmo no identificó la cuarta y última solución como una de las cuatro respuestas más probables. Era la quinta opción 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: se trata de un algoritmo aproximado. No es infalible y no acierta el 100% de las veces. Tienes que emplear parte de tu propio conocimiento y comprensión para comprobar la sensatez de las soluciones.

Este error puede surgir de varios sitios:

1. Podría deberse a la naturaleza aproximada del propio algoritmo y al reducido número de capas que empleé.
2. Podría tratarse de un error de muestreo finito, que podría reducirse si aumento el número de disparos en mi experimento.
3. También podría tratarse de un error de lectura, ya que la cuarta solución real sólo está desviada en un bit.

Este tipo de análisis de errores es lo que se necesita para convertirse en un profesional de la computación cuántica. Hay que entender el rendimiento del hardware y cómo puede contribuir a determinados 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 se encontraban entre las cinco mejores candidatas. Y solo hemos utilizado dos capas para llegar a esta conclusión. En general, si quisiéramos aumentar nuestras posibilidades de encontrar el mejor corte máximo en cada ocasión, podríamos aumentar la profundidad de la capa. Hay algunos matices al respecto, pero eso lo veremos en una lección posterior.

---

A escala industrial

Ahora que ya has tenido una pequeña muestra del proceso de resolución de un problema de corte máximo a pequeña escala en un ordenador cuántico, te reto a que lo hagas a gran escala. Sigue el tutorial del enlace para ver cuántos cortes se pueden obtener en un grafo de 125 nodos.