Testing the Quantum Approximate Optimization Algorithm using QUBO Formulations of Max-Cut and Knapsack Problems on Noisy and Noiseless Quantum Simulators

Abstract

Combinatorial optimization problems find application in almost every field of science and engineering. With growing problem sizes, the number of possible solutions grows exponentially, making finding the optimal solution using a classical computer impractical. Using a hybrid of quantum and classical processing, the Quantum Approximate Opti- mization Algorithm has shown promise in solving combinatorial optimization problems faster than classical algorithms. In this thesis, we investigate the performance of the Quantum Approximate Optimization Algorithm ( QAOA ) on the Max-Cut and Knapsack problems. We develop a testing suite to evaluate the algorithm’s performance on different problem instances. We run over 10000 hours of simulations on a university cluster to test the QAOA on various problem sizes, circuit depths, optimization configurations, and on both noiseless and noisy quantum environments. We analyze the results to understand the strengths and limitations of the QAOA and provide insights into its performance. Our experiments show that the QAOA is significantly affected by noise for small problem instances. As the problem size increases, the impact of noise becomes less pronounced. The quality of the solution is dependent on the circuit depth and the maximum number of iterations but not so much on the tolerance of the optimization algorithm. While a higher number of layers and iterations had a big impact on the quality of the solutions for small and medium problem sizes, this trend was less visible for larger problem instances. We hope that our work will contribute to the understanding of the QAOA and its performance on combinatorial optimization problems. We believe that the insights gained from our experiments can help guide future research in this area. Our simulation system will be made available as open-source software to enable further research in quantum optimization.