Exploring the Quantum Approximate Optimization Algorithm and Its Generalizations

Overview

We are in the midst of a second quantum revolution, where computers and algorithms are being transformed by harnessing the power of quantum phenomena. In this paper, I investigate and propose extensions of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical algorithm designed to obtain approximate solutions to combinatorial optimization problems. While the algorithm applies to a wide variety of problems, I focus on the Maximum Cut problem (MaxCut) in graph theory. This problem has applications across a broad range of fields, including statistical physics, machine learning, and biology. Moreover, MaxCut stands out for being NP-hard, among the most challenging classes of problems in computational complexity, making it an ideal testbed for quantum algorithms. In this project, I implement a computer simulation of the QAOA and use it to explore various aspects of the algorithm. I carry out a large-scale study of the QAOA on random graphs as a function of vertex number and graph density. Leveraging the large volume of data, I determine that the times during which the Mixing and Cost Hamiltonians act decay exponentially with graph density, and study how their relative dominance and the accuracy of the QAOA vary with it. I study weighted graphs, exploring the effects of graph density and graph connectivity on the accuracy of the QAOA. I investigate the convergence and computational cost of the QAOA as a function of quantum depth, i.e. number of steps. To overcome the high computational cost of the QAOA at large quantum depth, I introduce and analyze the Multi-Step, Lower Dimensional QAOA (LD QAOA), a generalization of the standard algorithm that replaces the optimization over a large dimensional parameter space for several steps of optimization over a low dimensional parameter space. I develop a detailed understanding of how the LD QAOA approaches the final solution and demonstrate that it achieves comparable accuracy with significantly greater computational efficiency. Finally, I introduce and investigate another generalization of the QAOA, the Multi-Mix QAOA, aimed at improving its ability to explore the space of solutions by employing multiple Mixing Hamiltonians at each step. My findings provide new insights into the structure, limitations, and potential improvements of the QAOA.

Competition history

• AJAS 2026 Category not listed

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• AJAS None projects
• Every AJAS 2026 project