Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs
Kunal Marwaha, Adrian She, James Sud · 2024
Read Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs by Kunal Marwaha, Adrian She, James Sud (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15147.txt.
Introduction
Kunal Marwaha, Adrian She, and James Sud analyze how well quantum variational algorithms do on random networks, in a 2024 paper. The algorithms, cousins of the popular QAOA method, aim to find low-energy states of two-body Hamiltonians defined on graphs. The team derives formulas for the energy reached, averaged over random regular graphs of endless size.
Evaluating the formulas grows costly with depth, so tests stay shallow. A symmetry inside the method blocks progress on the Quantum MaxCut problem in general, yet the algorithms beat known rivals on a related Hamiltonian and on bipartite graphs. Five layers already land within 1.62 percent of the best energy on a ring.
Catalog record
| CREATOR | Kunal Marwaha, Adrian She, James Sud |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 135 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-15147
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs Kunal Marwaha, Adrian She, James Sud Abstract 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 [ Bas+22 ] . 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 obstacle to successfully optimizing the Quantum MaxCut (QMC) Hamiltonian on general graphs. Nonetheless, the algorithms outperform known methods to optimize the EPR Hamiltonian of [ Kin23 ] 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 % 1.62\% error of the ground state energy for QMC on an infinite 1D ring, corresponding to the antiferromagnetic Heisenberg spin chain. 1 Introduction The natural quantum analogue of combinatorial optimization is the {\mathsf{QMA}} -complete local Hamiltonian problem [ KKR05 ] . Although we do not expect quantum algorithms to exactly solve every instance of this problem, we may instead design good quantum approximation algorithms. So far, we do not know which efficient quantum algorithm will achieve the best performance on this problem. This contrasts with the classical case [ Rag08 ] , and is connected to the possibility of quantum PCPs [ AAV13 , Hwa+22 ] . One compelling formulation of the local Hamiltonian problem is inspired by the {\mathsf{NP}} -hard problem Maximum Cut. In Maximum Cut, one must 2-color the vertices of a graph G in a way that maximizes the number of edges connecting different colors. In \emph{QuantumMaxCut} (QMC), one aims to find a global quantum state that maximizes the energy of a 2 -local Hamiltonian, where a single local term projects each edge of a graph G into the antisymmetric singlet state. This problem was previously studied as the spin-1/2 antiferromagnetic quantum Heisenberg model in statistical mechanics [ Hei28 ] , but has seen a resurgence in the quantum information literature [ GP19 , AGM20 , PT21 , PT22 , Lee22 , Tak+23 , Kin23 , LP24 , Wat+24 , KKZ24 ] . Although most work on this topic considers worst-case approximation algorithms, it is natural to wonder whether there exist good average-case approximation algorithms for these problems. Unlike the worst-case, random instances of classical combinatorial optimization problems can often be solved in polynomial time [ DMS17 , AMS21 , AMS23 , JSS24 ] . Some random local Hamiltonians have near-optimal product states [ BH14 , Ber23 ] , but it is unclear if better performance can be achieved with a quantum algorithm. In this work, we consider a family of variational algorithms for Quantum MaxCut and related problems. These algorithms are inspired by the Quantum Approximate Optimization Algorithm (QAOA) [ FGG14 , Hog00 ] , itself inspired by quantum annealing [ Far+00 ] . We leverage previous studies of the QAOA [ Bas+22 , Bas+22a ] to analyze the expected performance of our algorithms on random regular graphs. Our results show that we can outperform previously-studied classical algorithms for some random Hamiltonians in the infinite size limit, including the EPR Hamiltonian of [ Kin23 ] on random regular graphs and QMC on random regular bipartite graphs. Despite this, our algorithms are not universally successful. For QMC on more general graphs, we do not outperform even simple classical algorithms. This may be because the framework we use to analyze performance requires that our algorithms start with a symmetric (i.e. permutation-invariant) product state. We find that this symmetry creates a barrier to outperforming classical methods. However, since it is an artifact of our analysis, it is possible that similar variational algorithms may perform well on QMC when initialized with better product states. Finally, in the large-degree limit, we find that our algorithms do not outperform classical approaches for any of Hamiltonians we consider, potentially due to the phenomenon known as monogamy of entanglement . 1.1 Our contributions We consider local Hamiltonian problems defined on graphs. An instance H is specified by a 2-local Hamiltonian term H_{uv} and a graph G , where \displaystyle H\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\sum_{(u,v)\in E(G)}H_{uv} We consider three model Hamiltonians, each using a different 2-local term: QMC (Quantum MaxCut), EPR , and XY . We define these models in Section 2 . We then introduce two variational algorithms to prepare high-energy states for these Hamiltonians. For each Hamiltonian, we derive the expected energy achieved by these algorithms on high-girth regular graphs as the number of qubits goes to infinity ( Section 3 ). We also find the limit of this value as the degree tends to infinity. These variational algorithms and analyses can be extended to arbitrary k -local Hamiltonian problems on (hyper)graphs; we do this in Appendix D . At this point, the expected energy is a function only of each algorithm’s variational parameters. We numerically optimize these parameters for each Hamiltonian for degree 2\leq d\leq 5 and algorithm depth (number of variational layers) up to 5 . In Section 4 , we compare these values with simple classical algorithms described in Section 2.3 . On the EPR Hamiltonian, the variational algorithms outperform other algorithms at any depth. Moreover, when the graphs are also bipartite, the variational algorithms outperform other algorithms on the QMC Hamiltonian. When the graphs are further restricted to be edge-transitive , we can compare to the state-of-the-art algorithms which use global solutions obtained by SDP solvers. We find that our algorithms match the energy of [ Kin23 ] ’s algorithm at just depth 1 , and can only improve at higher layers ( Section 4.1 ). As an example, QMC on infinite bipartite 2 -regular graphs corresponds to the exactly-solvable Heisenberg XXX model on a 1D ring. For this case, our algorithm prepares a state within 1.62% error of the true ground state, outperforming [ Kin23 ] ’s algorithm. Finally, we provide an explicit calculation the energy obtained by one of our algorithms at depth one for QMC, EPR, and XY on arbitrary unweighted graphs in Appendix A . An interactive notebook with all relevant code is available online [ Sud24 ] . 1.2 Related work In the computer science literature, the first algorithms specifically for Quantum MaxCut (QMC) used semidefinite programs to prepare product states [ GP19 , PT21 , PT22 ] . It was then discovered that a short variational circuit [ AGM20 , Kin23 , Lee22 ] or an algorithm based on maximum weight matchings [ AGM20 , LP24 ] could improve on this product state. [ Kin23 ] introduced the EPR Hamiltonian, which is sign-problem free and thus not known to be {\mathsf{QMA}} -hard. As of the first version of this paper, the best worst-case approximation ratio is 0.584 for QMC [ LP24 ] and 0.707 for EPR