LfD Logo

Comparative Analysis of Parameter Selection Heuristics for the Quantum Approximate Optimisation Algorithm

The Quantum Approximate Optimization Algorithm (QAOA) is a variational algorithm that produces approximate solutions for combinatorial optimization problems. The quality of this approximation improves as the circuit depth increases. This search for an approximation instead of an exact solution is what makes this algorithm viable on near-term (NISQ Era) devices (i.e. instead of having to perform adiabatic evolution to determine the exact solution, we can take a "shortcut to adiabaticity", allowing quicker evolution to the target states of otherwise slow adiabatic dynamics). However for a high circuit-depth, the performance of the algorithm depends on choosing good starting parameters for the variational circuit. Finding optimal parameters is NP-Hard; For this reason there has been a lot of research regarding strategies for finding parameters which can serve as a good starting-point for optimization of a QAOA circuit of arbitrary depth.

This thesis focuses on a comparative analysis of two such strategies, INTERP and FOURIER, which take a heuristic approach to selecting good initial parameters for the QAOA Ansatz, by utilizing existing patterns in the distribution of optimal parameters to make an educated guess of variational parameters for QAOA of level p. The thesis provides a general overview over these strategies and benchmarks the performance using numerical simulations with varying problem sizes and difficulty; a comparison to the standard QAOA variant is conducted in order to assess the feasibility of running these parameter selection strategies on near-term devices.