LfD Logo

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

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm for producing approximations to combinatorial optimization problems. In theory the quality of this approximate solution converges to 1.0, which corresponds to an exact solution, as the circuit depth p goes towards infinity. This circuit depth corresponds directly to the number of QAOA layers, which are each parameterized by two a variational parameters α, β. In practice the quality of the approximation produced on QAOA critically depends on finding good variational parameters for the resulting Ansatz (the parameterized trial state). For this reason, a great amount of research regarding QAOA deals with approaches for finding good variational parameters. This thesis examines two such strategies, FOURIER and INTERP, given some optimal parameters at a certain depth, exploit patterns in the distribution of these parameters to heuristically determine good initial parameters for higher depths. In order to assess the feasibility of using these strategies to improve the basic QAOA, a comparison between heuristically optimized and randomly initialized QAOA was conducted: First, a detailed summary of the currently available research, which is relevant to this work, is given. Second, the heuristic parameter selection strategies were implemented and numerically simulated on random, non-regular instances of MAXCUT, a NP-hard problem, in order benchmark their performance and compare them to the basic QAOA variant. This comparison showed that for the instances that were examined, the FOURIER strategy produced good results with a considerably greater consistency than INTERP and the basic (random initialization) QAOA method, both of which performed similarly. Moreover, the results indicate that all variants are less sensitive to changes in the problem graph order than to changes in the problem graph size, which leads to a noticeable decrease in solution quality consistency as it increases; further experiments showed that this decrease in consistency may not only be due to the graph size, but instead is affected to a greater extent by other factors, such as high node connectivity, which becomes more probable as the graph size grows. In Summary, the results substantiate the speculation that the FOURIER strategy is a feasible augmentation to the standard QAOA protocol and may be especially advantageous for realistic near term implementations. Conversely, the results do not support such a supposition for the INTERP strategy.