The Quantum Approximate Optimization Algorithm, QAOA, uses a shallow depth quantum circuit to produce a parameter dependent state. For a given combinatorial optimization problem instance, the quantum expectation of the associated cost function is the parameter dependent objective function of the QAOA. We demonstrate that if the parameters are fixed and the instance comes from a reasonable distribution then the objective function value is concentrated in the sense that typical instances have (nearly) the same value of the objective function. This applies not just for optimal parameters as the whole landscape is instance independent. We can prove this is true for low depth quantum circuits for instances of MaxCut on large 3-regular graphs. Our results generalize beyond this example. We support the arguments with numerical examples that show remarkable concentration. For higher depth circuits the numerics also show concentration and we argue for this using the Law of Large Numbers. We also observe by simulation that if we find parameters which result in good performance at say 10 bits these same parameters result in good performance at say 24 bits. These findings suggest ways to run the QAOA that reduce or eliminate the use of the outer loop optimization and may allow us to find good solutions with fewer calls to the quantum computer.
The Quantum Approximate Optimization Algorithm, QAOA, uses a shallow depth quantum circuit to produce a parameter dependent state. For a given combinatorial optimization problem instance, the quantum expectation of the associated cost function is the parameter dependent objective function of the QAOA. We demonstrate that if the parameters are fixed and the instance comes from a reasonable distribution then the objective function value is concentrated in the sense that typical instances have (nearly) the same value of the objective function. This applies not just for optimal parameters as the whole landscape is instance independent. We can prove this is true for low depth quantum circuits for instances of MaxCut on large 3-regular graphs. Our results generalize beyond this example. We support the arguments with numerical examples that show remarkable concentration. For higher depth circuits the numerics also show concentration and we argue for this using the Law of Large Numbers. We also observe by simulation that if we find parameters which result in good performance at say 10 bits these same parameters result in good performance at say 24 bits. These findings suggest ways to run the QAOA that reduce or eliminate the use of the outer loop optimization and may allow us to find good solutions with fewer calls to the quantum computer.
The Quantum approximate optimization algorithm (QAOA) is one of the most promising candidates for achieving quantum advantage through quantum-enhanced combinatorial optimization. In a typical QAOA setup, a set of quantum circuit parameters is optimized to prepare a quantum state used to find the optimal solution of a combinatorial optimization problem. Several empirical observations about optimal parameter concentration effects for special QAOA MaxCut problem instances have been made in recent literature, however, a rigorous study of the subject is still lacking. We show that convergence of the optimal QAOA parameters around specific values and, consequently, successful transferability of parameters between different QAOA instances can be explained and predicted based on the local properties of the graphs, specifically the types of subgraphs (lightcones) from which the graphs are composed. We apply this approach to random regular and general random graphs. For example, we demonstrate how optimized parameters calculated for a 6-node random graph can be successfully used without modification as nearly optimal parameters for a 64-node random graph, with less than 1% reduction in approximation ratio as a result. This work presents a pathway to identifying classes of combinatorial optimization instances for which such variational quantum algorithms as QAOA can be substantially accelerated.
The emergent practical applicability of the Quantum Approximate Optimization Algorithm (QAOA) for approximate combinatorial optimization is a subject of considerable interest. One of the primary limitations of QAOA is the task of finding a set of good parameters, which is usually done using a variational optimization loop. Parameter transfer, or parameter concentration, is a phenomenon where QAOA angles trained on problem instances that are self-similar tend to perform well for other problem instances from that similar class. This suggests a potentially highly efficient and scalable nonvariational learning method for QAOA angle finding. In this work, we systematically study QAOA parameter transferability from small problem sizes (16 and 27 decision variables) onto large problem instances (up to 156 qubits) for heavy-hex graph Ising models with geometrically local higher-order terms using the Julia based QAOA simulation tool to perform classical angle finding for up to 49 QAOA layers ( p ) . Parameter transfer of the fixed angles is validated using a combination of full state vector, projected entangled pair states, matrix product state, and LOWESA numerical simulations. We find that the QAOA parameter transfer from single instances applied to other (unseen) problem instances does not in general provide monotonically improving performance as a function of p —there are many cases where the performance temporarily decreases as a function of p —but despite this the transferred angles have a general trend of improved expectation value as the QAOA depth increases, in many cases converging close to the true ground-state energy of the 100 + qubit instances. We also sample the hardware-compatible Ising models using the ensemble of transfer-learned QAOA parameters on several superconducting qubit IBM quantum processors with 127, 133, and 156 qubits. We find continuous solution quality improvement of the hardware-compatible QAOA circuits run on the IBM noisy intermediate-scale quantum processors up to p = 5 on , up to p = 9 on , and up to p = 10 on .
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) 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.
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.
Abstract As combinatorial optimization is one of the main quantum computing applications, many methods based on parameterized quantum circuits are being developed. In general, a set of parameters are being tweaked to optimize a cost function out of the quantum circuit output. One of these algorithms, the Quantum Approximate Optimization Algorithm stands out as a promising approach to tackling combinatorial problems. However, finding the appropriate parameters is a difficult task. Although QAOA exhibits concentration properties, they can depend on instances characteristics that may not be easy to identify, but may nonetheless offer useful information to find good parameters. In this work, we study unsupervised Machine Learning approaches for setting these parameters without optimization. We perform clustering with the angle values but also instances encodings (using instance features or the output of a variational graph autoencoder), and compare different approaches. These angle-finding strategies can be used to reduce calls to quantum circuits when leveraging QAOA as a subroutine. We showcase them within Recursive-QAOA up to depth 3 where the number of QAOA parameters used per iteration is limited to 3, achieving a median approximation ratio of 0.94 for MaxCut over 200 Erdős-Rényi graphs. We obtain similar performances to the case where we extensively optimize the angles, hence saving numerous circuit calls.