Local Hamiltonian Problems (LHPs) are important problems that are computationally QMA-complete and physically relevant for many-body quantum systems. Quantum MaxCut (QMC), which equates to finding ground states of the quantum Heisenberg model, is the canonical LHP for which various algorithms have been proposed, including semidefinite programs and variational quantum algorithms. We propose and analyze a quantum approximation algorithm which we call the Hamiltonian Quantum Approximate Optimization Algorithm (HamQAOA), which builds on the well-known scheme for combinatorial optimization and is suitable for implementations on near-term hardware. We establish rigorous performance guarantees of the HamQAOA for QMC on high-girth regular graphs, and our result provides bounds on the ground energy density for quantum Heisenberg spin glasses in the infinite size limit that improve with depth. Furthermore, we develop heuristic strategies with which to efficiently obtain good HamQAOA parameters. Through numerical simulations, we show that the HamQAOA empirically outperforms prior algorithms on a wide variety of QMC instances. In particular, our results indicate that the linear-depth HamQAOA can deterministically prepare exact ground states of 1-dimensional antiferromagnetic Heisenberg spin chains described by the Bethe ansatz, in contrast to the exponential depths required in previous protocols for preparing Bethe states.
Local Hamiltonian Problems (LHPs) are important problems that are computationally QMA-complete and physically relevant for many-body quantum systems. Quantum MaxCut (QMC), which equates to finding ground states of the quantum Heisenberg model, is the canonical LHP for which various algorithms have been proposed, including semidefinite programs and variational quantum algorithms. We propose and analyze a quantum approximation algorithm which we call the Hamiltonian Quantum Approximate Optimization Algorithm (HamQAOA), which builds on the well-known scheme for combinatorial optimization and is suitable for implementations on near-term hardware. We establish rigorous performance guarantees of the HamQAOA for QMC on high-girth regular graphs, and our result provides bounds on the ground energy density for quantum Heisenberg spin glasses in the infinite size limit that improve with depth. Furthermore, we develop heuristic strategies with which to efficiently obtain good HamQAOA parameters. Through numerical simulations, we show that the HamQAOA empirically outperforms prior algorithms on a wide variety of QMC instances. In particular, our results indicate that the linear-depth HamQAOA can deterministically prepare exact ground states of 1-dimensional antiferromagnetic Heisenberg spin chains described by the Bethe ansatz, in contrast to the exponential depths required in previous protocols for preparing Bethe states.
We design two variational algorithms to optimize specific 2-local Hamiltonians defined on graphs. Our algorithms are inspired by the Quantum Approximate Optimization Algorithm. We develop formulae to analyze the energy achieved by these algorithms with high probability over random regular graphs in the infinite-size limit, using techniques from [arXiv:2110.14206]. The complexity of evaluating these formulae scales exponentially with the number of layers of the algorithms, so our numerical evaluation is limited to a small constant number of layers. We compare these algorithms to simple classical approaches and a state-of-the-art worst-case algorithm. We find that the symmetry inherent to these specific variational algorithms presents a major \emph{obstacle} to successfully optimizing the Quantum MaxCut (QMC) Hamiltonian on general graphs. Nonetheless, the algorithms outperform known methods to optimize the EPR Hamiltonian of [arXiv:2209.02589] on random regular graphs, and the QMC Hamiltonian when the graphs are also bipartite. As a special case, we show that with just five layers of our algorithm, we can already prepare states within 1.62% error of the ground state energy for QMC on an infinite 1D ring, corresponding to the antiferromagnetic Heisenberg spin chain.
It is well-known in physics that the limit of large quantum spin S should be understood as a semiclassical limit. This raises the question of whether such emergent classicality facilitates the approximation of computationally hard quantum optimization problems, such as the local Hamiltonian problem. We demonstrate this explicitly for spin-S generalizations of Quantum Max-Cut (QMaxCutS), equivalent to the problem of finding the ground state energy of an arbitrary spin-S quantum Heisenberg antiferromagnet (QHAS). We prove that approximating the value of QHAS to inverse polynomial accuracy is QMA-complete for all S, extending previous results for S=1/2. We also present two distinct families of classical approximation algorithms for QMaxCutS based on rounding the output of a semidefinite program to a product of Bloch coherent states. The approximation ratios for both our proposed algorithms strictly increase with S and converge to the Briët-Oliveira-Vallentin approximation ratio αBOV≈0.956 from below as S→∞.
Combinatorial optimization is regarded as a potentially promising application of near and long-term quantum computers. The best-known heuristic quantum algorithm for combinatorial optimization on gate-based devices, the Quantum Approximate Optimization Algorithm (QAOA), has been the subject of many theoretical and empirical studies. Unfortunately, its application to specific combinatorial optimization problems poses several difficulties: among these, few performance guarantees are known, and the variational nature of the algorithm makes it necessary to classically optimize a number of parameters. In this work, we partially address these issues for a specific combinatorial optimization problem: diluted spin models, with MAX-CUT as a notable special case. Specifically, generalizing the analysis of the Sherrington-Kirkpatrick model by Farhi et al., we establish an explicit algorithm to evaluate the performance of QAOA on MAX-CUT applied to random Erdos-Renyi graphs of expected degree d for an arbitrary constant number of layers p and as the problem size tends to infinity. This analysis yields an explicit mapping between QAOA parameters for MAX-CUT on Erdos-Renyi graphs of expected degree d, in the limit d→∞, and the Sherrington-Kirkpatrick model, and gives good QAOA variational parameters for MAX-CUT applied to Erdos-Renyi graphs. We then partially generalize the latter analysis to graphs with a degree distribution rather than a single degree d, and finally to diluted spin-models with D-body interactions (D≥3). We validate our results with numerical experiments suggesting they may have a larger reach than rigorously established; among other things, our algorithms provided good initial, if not nearly optimal, variational parameters for very small problem instances where the infinite-size limit assumption is clearly violated.
Abstract The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum–classical algorithm used to approximately solve combinatorial optimisation problems. It involves multiple iterations of a parameterised ansatz that consists of a problem and mixer Hamiltonian, with the parameters being classically optimised. While QAOA can be implemented on near-term quantum hardware, physical limitations such as gate noise, restricted qubit connectivity, and state-preparation-and-measurement (SPAM) errors can limit circuit depth and decrease performance. To address these limitations, this work introduces the eXpressive QAOA (XQAOA), an overparameterised variant of QAOA that assigns more classical parameters to the ansatz to improve its performance at low depths. XQAOA also introduces an additional Pauli-Y component in the mixer Hamiltonian, allowing the mixer to implement arbitrary unitary transformations on each qubit. To benchmark the performance of XQAOA at unit depth, we derive its closed-form expression for the MaxCut problem and compare it to QAOA, Multi-Angle QAOA (MA-QAOA) (Herrman et al 2022 Sci. Rep. 12 6781), a classical-relaxed algorithm, and the state-of-the-art Goemans–Williamson algorithm on a set of unweighted regular graphs with 128 and 256 nodes for degrees ranging from 3 to 10. Our results indicate that at unit depth, XQAOA has benign loss landscapes with local minima concentrated near the global optimum, allowing it to consistently outperform QAOA, MA-QAOA, and the classical-relaxed algorithm on all graph instances and the Goemans–Williamson algorithm on graph instances with degrees greater than 4. Small-scale simulations also reveal that unit-depth XQAOA invariably surpasses both QAOA and MA-QAOA on all tested depths up to five. Additionally, we find an infinite family of graphs for which XQAOA solves MaxCut exactly and analytically show that for some graphs in this family, special cases of XQAOA are capable of achieving a much larger approximation ratio than QAOA. Overall, XQAOA is a more viable choice for variational quantum optimisation on near-term quantum devices, offering competitive performance at low depths.
The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to combinatorial optimization problems. Its performance monotonically improves with its depth p. We apply the QAOA to MaxCut on large-girth D-regular graphs. We give an iterative formula to evaluate performance for any D at any depth p. Looking at random D-regular graphs, at optimal parameters and as D goes to infinity, we find that the p=11 QAOA beats all classical algorithms (known to the authors) that are free of unproven conjectures. While the iterative formula for these D-regular graphs is derived by looking at a single tree subgraph, we prove that it also gives the ensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick (SK) model defined on the complete graph. We also generalize our formula to Max-q-XORSAT on large-girth regular hypergraphs. Our iteration is a compact procedure, but its computational complexity grows as O(p24p). This iteration is more efficient than the previous procedure for analyzing QAOA performance on the SK model, and we are able to numerically go to p=20. Encouraged by our findings, we make the optimistic conjecture that the QAOA, as p goes to infinity, will achieve the Parisi value. We analyze the performance of the quantum algorithm, but one needs to run it on a quantum computer to produce a string with the guaranteed performance.
The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm that can be used to approximately solve combinatorial optimization problems. However, a major limitation of QAOA is that it is a "local" algorithm for finite circuit depths, meaning it can only optimize over local properties of the graph. In this paper, we present Phantom-Qaoa, a new QAOA ansatz that introduces only one additional parameter to the standard ansatz—regardless of system size—allowing QAOA to "see" more of the graph at a given depth p. We achieve this by modifying the target graph to include additional α-weighted edges, with α serving as a tunable parameter. This modified graph is then used to construct the phase operator and allows QAOA to explore a wider range of the graph’s features. We derive a general formula for our new ansatz at p = 1 and analytically show an improvement in the approximation ratio for cycle graphs. We also provide numerical experiments that demonstrate significant improvements in the approximation ratio for the Max-Cut problem over the standard QAOA ansatz for p = 1 and p = 2 on random regular graphs up to 16 nodes.