Analyzing Complexity in Variational Quantum Algorithms
By Taohan Lin
Variational quantum algorithms are a class of algorithms which make use of both classical and quantum techniques to solve a problem. The quantum approximation optimization algorithm (QAOA) is one such algorithm which focuses on solving combinatorial optimization problems. In this study, we numerically approximate the computational complexity of the QAOA for the Ising model and calculate complexity bounds. We create a simulator to calculate the ground state and ground state energy of the TFIM for arbitrary system size and coupling coefficient. At the phase transition, we observe the existence of a critical layer count for QAOA after which error in the calculated ground state energy drops drastically. We also observe that this critical layer count increases roughly linearly with system size. When the system size is held constant, We find that error in the ground state energy is maximized near the phase transition prior to achieving the critical layer count, and minimized after achieving the critical layer count. The greatest deviation in error before and after the critical layer count is at the phase transition. While the study is limited by the small system sizes we studied, the results could still be quite useful for understanding and optimizing the QAOA algorithm in the future.