Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA requires computationally intensive parameter optimization. The challenge of parameter optimization is particularly acute in the case of weighted problems, for which the eigenvalues of the phase operator are non-integer and the QAOA energy landscape is not periodic. In this work, we develop parameter setting heuristics for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth p=1 applied to the weighted MaxCut problem under different assumptions on the weights. In particular, we rigorously prove the conventional wisdom that in the average case the first local optimum near zero gives globally-optimal QAOA parameters. Second, for p≥1 we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Therefore, we can use parameters previously obtained for unweighted MaxCut for weighted problems. Finally, we prove that for p=1 the QAOA objective sharply concentrates around its expectation, which means that our parameter setting rules hold with high probability for a random weighted instance. We numerically validate this approach on general weighted graphs and show that on average the QAOA energy with the proposed fixed parameters is only 1.1 percentage points away from that with optimized parameters. Third, we propose a general heuristic rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness using QAOA with the XY Hamming-weight-preserving mixer applied to the portfolio optimization problem. Our heuristic improves the convergence of local optimizers, reducing the number of iterations by 7.4x on average.
Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA requires computationally intensive parameter optimization. The challenge of parameter optimization is particularly acute in the case of weighted problems, for which the eigenvalues of the phase operator are non-integer and the QAOA energy landscape is not periodic. In this work, we develop parameter setting heuristics for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth p=1 applied to the weighted MaxCut problem under different assumptions on the weights. In particular, we rigorously prove the conventional wisdom that in the average case the first local optimum near zero gives globally-optimal QAOA parameters. Second, for p≥1 we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Therefore, we can use parameters previously obtained for unweighted MaxCut for weighted problems. Finally, we prove that for p=1 the QAOA objective sharply concentrates around its expectation, which means that our parameter setting rules hold with high probability for a random weighted instance. We numerically validate this approach on general weighted graphs and show that on average the QAOA energy with the proposed fixed parameters is only 1.1 percentage points away from that with optimized parameters. Third, we propose a general heuristic rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness using QAOA with the XY Hamming-weight-preserving mixer applied to the portfolio optimization problem. Our heuristic improves the convergence of local optimizers, reducing the number of iterations by 7.4x on average.
Finding high-quality parameters is a central obstacle to using the quantum approximate optimization algorithm (QAOA). Previous work partially addresses this issue for QAOA on unweighted MaxCut problems by leveraging similarities in the objective landscape among different problem instances. However, we show that the more general weighted MaxCut problem has significantly modified objective landscapes, with a proliferation of poor local optima. Our main contribution is a simple rescaling scheme that overcomes these deleterious effects of weights. We show that for a given QAOA depth, a single “typical” vector of QAOA parameters can be successfully transferred to weighted MaxCut instances. This transfer leads to a median decrease in the approximation ratio of only 2.0 percentage points relative to a considerably more expensive direct optimization on a dataset of 34,701 instances with up to 20 nodes and multiple weight distributions. This decrease can be reduced to 1.2 percentage points at the cost of only 10 additional QAOA circuit evaluations with parameters sampled from a pretrained metadistribution, or the transferred parameters can be used as a starting point for a single local optimization run to obtain approximation ratios equivalent to those achieved by exhaustive optimization in 96.35% of our cases.
The quantum alternating operator ansatz (QAOA) is a generalized approach for solving challenging optimization problems that builds on the alternating structure of the quantum approximate optimization algorithm. Finding high-quality parameters efficiently for QAOA remains a major challenge in practice. In this work, we introduce a classical strategy for parameter setting, suitable for cases in which the number of distinct cost values grows only polynomially with the problem size, such as is common for constraint-satisfaction problems. The crux of our strategy is that we replace the cost function expectation value step of QAOA with a classical model that can be efficiently evaluated classically and has parameters which play an analogous role to the QAOA parameters. This model is based on empirical observations that, in some QAOA states, variable configurations with the same cost have the same amplitudes from step to step. We define this class of states as homogeneous states. For problems with particular symmetries, QAOA states are guaranteed to be homogeneous. More generally, high overlaps between QAOA states and homogeneous states have been empirically observed in a number of settings. Building on this idea, we define a classical homogeneous proxy for QAOA in which this property holds exactly and which yields information describing both states and expectation values. We then classically determine high-quality parameters for this proxy and then use these parameters in QAOA, an approach we label the homogeneous heuristic for parameter setting. We numerically examine this heuristic for MaxCut on unweighted Erdős-Rényi random graphs. For up to three QAOA levels we demonstrate that the heuristic is easily able to find parameters that match approximation ratios corresponding to previously found globally optimized approaches. For levels up to 20 we obtain parameters using our heuristic with approximation ratios monotonically increasing with depth, while a strategy that uses parameter transfer instead fails to converge with comparable classical resources. These results suggest that our heuristic may find good parameters in regimes that are intractable with noisy intermediate-scale quantum devices. Finally, we outline how our heuristic may be applied to wider classes of problems. Published by the American Physical Society 2024
The Quantum Approximate Optimization Algorithm (QAOA) is one of the promising near-term algorithms designed to find approximate solutions for combinatorial optimization problems. The algorithm prepares a parametrized state that is aimed to maximize the expectation value of the objective function of the problem. The circuit for QAOA consists of p layers, and it depends on 2p parameters, the determination of which can be carried out using a variational quantum eigensolver (VQE) subroutine. This is a variational approach for finding optimal parameters, where the quantum state is prepared with a quantum computer, and a classical computer is used for calculating the corresponding objective function value and performing an outer loop optimization routine in order to find optimal parameters. Earlier work on the algorithm has shown that QAOA is closely related to the Quantum Adiabatic Algorithm, which results in noticeable patterns in the optimal parameters. To this purpose, two methods, INTERP and FOURIER, were proposed to exploit this structure by Zhou et al. (2018). In this thesis, I extend upon these results by examining the effectiveness of one of their methods, the INTERP method, on the Max-Cut problem from graph theory. The performance of QAOA using this method was studied on several classes of graphs and benchmarked against the currently best-known classical algorithm Goemans-Williamson, which achieves an approximation ratio of ρ ≈ 0.878 on arbitrary graphs. The classes of graphs examined include cyclic, weighted and unweighted 3-regular, and Erdős–Rényi graphs with edge probabilities of 0.5 and 0.75 and graph sizes ranging from 4 to 16. Moreover, it was investigated if the INTERP method offers an advantage compared to random initialization of parameters and whether or not the method is polynomial in p. It was found that different graph classes lead to similar but different parameter patterns. Furthermore, the performance of QAOA using the INTERP method was dependent on the graph class considered. For the small graphs investigated it was found that QAOA outperforms Goemans-Williamson on ER-0.50, ER-0.75 and weighted 3-regular graphs from p=7 and beyond with respect to how well the expectation of the objective function approximates the optimal value, while for unweighted 3-regular graphs p=6 suffices. However, the calculation of the parameters is costly and requires a number of function evaluations that is on the order of the number of possible bipartitions of small graph with sizes n ≤ 16. Moreover, the numerical results suggested that indeed the method is polynomial in p advocating that the algorithm might be a strong alternative to Goemans-Williamson for large graph sizes, once hardware allows it.
Farhi et al. recently proposed a class of quantum algorithms, the quantum approximate optimization algorithm (QAOA), for approximately solving combinatorial optimization problems (E. Farhi et al., arXiv:1411.4028; arXiv:1412.6062; arXiv:1602.07674). A level-p QAOA circuit consists of p steps; in each step a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The 2p times for which these two Hamiltonians are applied are the parameters of the algorithm, which are to be optimized classically for the best performance. As p increases, parameter optimization becomes inefficient due to the curse of dimensionality. The success of the QAOA approach will depend, in part, on finding effective parameter-setting strategies. Here we analytically and numerically study parameter setting for the QAOA applied to MaxCut. For the level-1 QAOA, we derive an analytical expression for a general graph. In principle, expressions for higher p could be derived, but the number of terms quickly becomes prohibitive. For a special case of MaxCut, the ``ring of disagrees,'' or the one-dimensional antiferromagnetic ring, we provide an analysis for an arbitrarily high level. Using a fermionic representation, the evolution of the system under the QAOA translates into quantum control of an ensemble of independent spins. This treatment enables us to obtain analytical expressions for the performance of the QAOA for any p. It also greatly simplifies the numerical search for the optimal values of the parameters. By exploring symmetries, we identify a lower-dimensional submanifold of interest; the search effort can be accordingly reduced. This analysis also explains an observed symmetry in the optimal parameter values. Further, we numerically investigate the parameter landscape and show that it is a simple one in the sense of having no local optima.
The main object of study of this work is the Quantum Approximate Optimization Algorithm (QAOA) —the best-known heuristic quantum algorithm for addressing combinatorial optimization problems. Despite its popularity, QAOA poses major challenges. Namely, its performance remains poorly understood, especially in the low depth regime most relevant to near-term quantum computing. Besides, the algorithm is of variational nature, relying on several hyperparameters to be classically trained. In this work, we contribute to addressing these issues by developing techniques to understand the performance of QAOA at low depth, and deducing from these pretrained hyperparameters, thereby eliminating or considerably reducing the need for a classical optimization loop. We first consider applying QAOA to constraint satisfaction problems with the goal of maximizing the algorithm’s approximation ratio (fraction of satisfied constraints). As a particular example, we consider QAOA applied to MAXCUT on non-regular graphs, showing how analytic techniques provide good guess hyperparameters in this setting. Next, we analyze the performance of QAOA on a well-studied constraint satisfaction problem: random k-SAT. In this case, the performance is measured by the probability of finding an assignment satisfying all constraints (“success probability”). To estimate this quantity, we develop new techniques, mapping quantum expectation values of the QAOA circuits to classical spin models. We further show how these techniques can be generalized to a larger family of random constraint satisfaction problems. We conclude the work by two feasibility studies inspired by real-world use cases encountered in collaborations with industrial partners: peptide sampling, and solving flow problems. These problems are naturally phrased by encoding combinatorial variables in qudits, a relatively unexplored setting in the existing literature. We present partial analytic and numerical results for optimal QAOA hyperparameters and the scaling of its success probability in this framework, underlining potential specific difficulties when using QAOA with qudits.
The quantum approximate optimization algorithm (QAOA) has numerous promising applications in solving the combinatorial optimization problems on near-term Noisy Intermediate Scalable Quantum (NISQ) devices. QAOA has a quantum-classical hybrid structure. Its quantum part consists of a parameterized alternating operator ansatz, and its classical part comprises an optimization algorithm, which optimizes the parameters to maximize the expectation value of the problem Hamiltonian. This expectation value depends highly on the parameters, this implies that a set of good parameters leads to an accurate solution. However, at large circuit depth of QAOA, it is difficult to achieve global optimization due to the multiple occurrences of local minima or maxima. In this paper, we propose a parameters fixing strategy which gives high approximation ratio on average, even at large circuit depths, by initializing QAOA with the optimal parameters obtained from the previous depths. We test our strategy on the Max-cut problem of certain classes of graphs such as the 3-regular graphs and the Erdös-Rényi graphs.