Quantum approximate optimization algorithm (QAOA) for the max-cut problem using bell and GHZ states

Abstract

El objetivo de esta tesis fue resolver el problema del corte máximo de un grafo (Max-Cut problem) a través del algoritmo cuántico variacional Quantum Approximate Optimization Algorithm (QAOA), utilizando distintos tipos de estados iniciales del grafo: entrelazando pares de nodos a través de estados de Bell, entrelazando todos los nodos del grafo por medio de un estado Greenberger-Horne-Zeilinger (GHZ), y por último, considerando la inicialización estándar del algoritmo, en que cada nodo del grafo se inicializa como superposición balanceada de los estados 0 y 1. Se estudió el desempeño del algoritmo en grafos de orden ˜ N = 6, 10 y 16, con numero de aristas K = 2, N/2 y N − 1, considerando grafos balanceados (todas las aristas de igual peso) y grafos con aristas de distinto peso. Cada grafo fue resuelto empleando profundidades del circuito cuántico iguales a 1, 2 y 3. Las soluciones obtenidas fueron comparadas con la solución óptima encontrada a través de una búsqueda exhaustiva. El algoritmo fue implementado en Pennylane, el lenguaje de computación cuántica de la empresa Xanadú. En circuitos de mínima profundidad [1], en el 44% de los grafos (7 grafos), los estados de Bell mejoraron el desempeño del algoritmo, reduciendo la distancia entre la solución encontrada y solución óptima en un 38% en promedio. A medida que se aumentó la profundidad del circuito, el estado de Bell comenzó a ser más deficiente, siendo mejor solo en un 25% de los casos (4 grafos) con respecto al algoritmo estándar. En dichos casos, sin embargo, el algoritmo con estado inicial de Bell fue más lento en encontrar la solución final. Por otra parte, el estado GHZ mostro mejoras considerables para circuitos de profundidad igual a 3. Al compararlo consigo mismo, al cambiar de un circuito de profundidad 1 a un circuito de profundidad 3, se redujo en promedio la distancia entre la solución encontrada y la solución óptima en un 55%. Al cambiar de un circuito de profundidad 2 a uno de profundidad 3, dicha reducción fue de un 57%, mostrando que en circuitos de profundidad igual a 3 la inicialización en estado GHZ mejora a más de la mitad, con respecto a un circuito de menor profundidad. La inicialización convencional resultó mejor en un 56% de los casos, en términos de la distancia entre la solución encontrada y la solución óptima. A partir de esto, se concluyó que la inicialización estándar del algoritmo QAOA en el problema Max-Cut sigue siendo mejor para este tipo de problemas, pero en grafos con aristas de distinto peso se podría considerar inicializar en estados de Bell para grafos de ciertas condiciones específicas.

The objective of this thesis was to solve the Max-Cut problem of a graph using the variational quantum algorithm known as the Quantum Approximate Optimization Algorithm (QAOA). Different types of initial states for the graph were used: entangling pairs of nodes through Bell states, entangling all the nodes of the graph using a Greenberger-Horne-Zeilinger (GHZ) state, and finally, considering the standard initialization of the algorithm, where each node of the graph is initialized in a balanced superposition of states 0 and 1. The performance of the algorithm was studied on graphs of order N = 6, 10, and 16, with the number of edges K = 2, N/2, and N − 1, considering balanced graphs (all edges having the same weight) and graphs with edges of different weights. Each graph was solved using quantum circuit depths of 1, 2, and 3. The solutions obtained were compared with the optimal solution found through exhaustive search. The algorithm was implemented in Pennylane, the quantum computing framework developed by Xanadu. In circuits with minimal depth (1), Bell states improved the algorithm’s performance in 44 % of the graphs (7 graphs), reducing the gap between the obtained solution and the optimal solution by 38 % on average. As the circuit depth increased, Bell state initialization became less effective, outperforming the standard algorithm in only 25 % of the cases (4 graphs). However, in these cases, the algorithm with Bell state initialization was slower in finding the final solution. On the other hand, the GHZ state showed significant improvements for circuits with a depth of 3. When compared to itself, changing from a circuit of depth 1 to a circuit of depth 3 reduced the average gap between the obtained solution and the optimal solution by 55 %. When changing from a circuit of depth 2 to one of depth 3, this reduction was 57 %, showing that for circuits with a depth of 3, GHZ state initialization improves by more than half compared to circuits with lower depths. The conventional initialization proved to be better in 56 % of the cases in terms of reducing the gap between the obtained solution and the optimal solution. Based on this, it was concluded that the standard initialization of the QAOA algorithm in the Max-Cut problem remains the best choice for this type of problem. However, for graphs with edges of different weights, initializing with Bell states could be considered for graphs with specific conditions.