Variational Quantum Algorithms, including the Quantum Approximate Optimization Algorithm (QAOA), have shown promise in solving optimization problems but rely on costly variational loops that can themselves be hard optimization problems. Many methods have been proposed to mitigate this variational cost, with one of the most common being parameter transfer and concentration where variational parameters for one problem instance or for an average over problem instances can be used as a good set of parameters for another instance. Methods exist for reweighting these parameters based off graph degree and edge weights, but there has been little work on how to do this reweighting to handle higher locality problems where the graph structure turns into a hypergraph structure. In this paper, we analytically derive parameter reweighting rules to transfer parameters between different locality hypergraphs, resulting in a reweighting for the mixing terms in the Hamiltonian which have previously not been considered. These analytics rely on three cycle-free and low-circuit-depth assumptions, but numerics indicate that the results can be used even when these assumptions are not satisfied. The numerics obtain high quality results across a diverse set of hypergraphs with locality less than or equal to five, improving on previous relations that do not reweight the mixing terms.
Variational Quantum Algorithms, including the Quantum Approximate Optimization Algorithm (QAOA), have shown promise in solving optimization problems but rely on costly variational loops that can themselves be hard optimization problems. Many methods have been proposed to mitigate this variational cost, with one of the most common being parameter transfer and concentration where variational parameters for one problem instance or for an average over problem instances can be used as a good set of parameters for another instance. Methods exist for reweighting these parameters based off graph degree and edge weights, but there has been little work on how to do this reweighting to handle higher locality problems where the graph structure turns into a hypergraph structure. In this paper, we analytically derive parameter reweighting rules to transfer parameters between different locality hypergraphs, resulting in a reweighting for the mixing terms in the Hamiltonian which have previously not been considered. These analytics rely on three cycle-free and low-circuit-depth assumptions, but numerics indicate that the results can be used even when these assumptions are not satisfied. The numerics obtain high quality results across a diverse set of hypergraphs with locality less than or equal to five, improving on previous relations that do not reweight the mixing terms.
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 .
Quantum Approximate Optimization Algorithm (QAOA) provides a way to solve combinatorial optimization problems using quantum computers. QAOA circuits consist of time evolution operators by the cost Hamiltonian and of state mixing operators, and embedded variational parameter for each operator is tuned so that the expectation value of the cost function is minimized. The optimization of the variational parameters is taken place on classical devices while the cost function is measured in the sense of quantum. To facilitate the classical optimization, there are several previous works on making decision strategies for optimal/initial parameters and on extracting similarities among instances. In our current work, we consider simplified QAOA parameters that take linear forms along with the depth in the circuit. Such a simplification, which would be suggested from an analogy to quantum annealing, leads to a drastic reduction of the parameter space from 2p to 4 dimensions with the any number of QAOA layers p. In addition, cost landscapes in the reduced parameter space have some stability on differing instances. This fact suggests that an optimal parameter set for a given instance can be transferred to other instances. In this paper we present some numerical results that are obtained for instances of the random Ising model and of the max-cut problem. The transferability of linearized parameters is demonstrated for randomly generated source and destination instances, and its dependence on features of the instances are investigated.
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 quantum approximate optimization algorithm (QAOA) is a near-term quantum algorithm aimed at solving combinatorial optimization problems. Since its introduction, various generalizations have emerged, spanning modifications to the initial state, phase unitaries, and mixer unitaries. In this work, we present an analytical study of broad families of QAOA variants. We begin by examining a family of QAOA with product mixers, which includes single-body mixers parametrized by multiple variational angles, and derive exact analytical expressions for the cost expectation on weighted problem graphs in the single-layer ansatz setting. We then analyze a family of QAOA that employs many-body Grover-type mixers, deriving analogous analytical expressions for weighted problem hypergraphs in the setting of arbitrarily many circuit ansatz layers. For both families, we allow individual phase angles for each node and edge (hyperedge) in the problem graph (hypergraph). Our results reveal that, in contrast to product mixers, the Grover mixer is sensitive to contributions from cycles of all lengths in the problem graph, exhibiting a form of non-locality. Our study advances the understanding of QAOA's behavior in general scenarios, providing a foundation for further theoretical exploration.
The quantum approximate optimization algorithm (QAOA) is one of the most promising candidates for achieving quantum advantage through quantum-enhanced combinatorial optimization. A near-optimal solution to the combinatorial optimization problem is achieved by preparing a quantum state through the optimization of quantum circuit parameters. Optimal QAOA parameter concentration effects for special MaxCut problem instances have been observed, but a rigorous study of the subject is still lacking. In this work we show clustering of optimal QAOA parameters around specific values; consequently, successful transferability of parameters between different QAOA instances can be explained and predicted based on local properties of the graphs, including the type of subgraphs (lightcones) from which graphs are composed as well as the overall degree of nodes in the graph (parity). We apply this approach to several instances of random graphs with a varying number of nodes as well as parity and show that one can use optimal donor graph QAOA parameters as near-optimal parameters for larger acceptor graphs with comparable approximation ratios. This work presents a pathway to identifying classes of combinatorial optimization instances for which variational quantum algorithms such as QAOA can be substantially accelerated.
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.