Equivalence of Quantum Approximate Optimization Algorithm and Linear-Time Quantum Annealing for the Sherrington-Kirkpatrick Model

• URL: http://arxiv.org/abs/2503.09563v1
• Date: Wed, 12 Mar 2025 17:27:40 GMT
• Title: Equivalence of Quantum Approximate Optimization Algorithm and Linear-Time Quantum Annealing for the Sherrington-Kirkpatrick Model
• Authors: Sami Boulebnane, James Sud, Ruslan Shaydulin, Marco Pistoia,
• Abstract summary: We show that QAOA energy approximates that of quantum annealing under two conditions, namely that angles vary smoothly from one layer to the next and that the sum is bounded by a constant.<n>Our results are enabled by novel formulae for QAOA energy with constant sum of angles and arbitrary depth and the series expansion of energy in sum of angles.
• Score: 2.0174252910776556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum approximate optimization algorithm (QAOA) and quantum annealing are two of the most popular quantum optimization heuristics. While QAOA is known to be able to approximate quantum annealing, the approximation requires QAOA angles to vanish with the problem size $n$, whereas optimized QAOA angles are observed to be size-independent for small $n$ and constant in the infinite-size limit. This fact led to a folklore belief that QAOA has a mechanism that is fundamentally different from quantum annealing. In this work, we provide evidence against this by analytically showing that QAOA energy approximates that of quantum annealing under two conditions, namely that angles vary smoothly from one layer to the next and that the sum is bounded by a constant. These conditions are known to hold for near-optimal QAOA angles empirically. Our results are enabled by novel formulae for QAOA energy with constant sum of angles and arbitrary depth and the series expansion of energy in sum of angles, which we obtain using the saddle-point method, which may be of independent interest. While our results are limited to the Sherrington-Kirkpatrick (SK) model, we show numerically that the expansion holds for random 2SAT and expect our main results to generalize to other constraint satisfaction problems. A corollary of our results is a quadratic improvement for the bound on depth required to compile Trotterized quantum annealing of the SK model.

Related papers

• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  We show that VarQITE achieves significantly lower mean optimality gaps compared to other conventional methods. We demonstrate that scaling the Hamiltonian can further reduce optimization costs and accelerate convergence.
  arXiv  Detail & Related papers  (2025-04-17T03:09:37Z)
• Weighted Approximate Quantum Natural Gradient for Variational Quantum Eigensolver [5.873113584103881]
  Variational quantum eigensolver (VQE) is one of the most prominent algorithms using near-term quantum devices. We propose a weighted Approximate Quantum Natural Gradient (WA-QNG) method tailored for $k$ of local Hamiltonians.
  arXiv  Detail & Related papers  (2025-04-07T11:18:09Z)
• A quantum algorithm for Khovanov homology [42.6618666851542]
  Khovanov homology is a knot that categorifies the Jones topological invariant, recognizes the unknot, and is conjectured to appear as an observable in $4D$ supersymmetric Yang-Mills theory. Despite its rich mathematical and physical significance, the computational complexity of Khovanov homology remains largely unknown.
  arXiv  Detail & Related papers  (2025-01-21T18:54:59Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• Variational-quantum-eigensolver-inspired optimization for spin-chain work extraction [39.58317527488534]
  Energy extraction from quantum sources is a key task to develop new quantum devices such as quantum batteries. One of the main issues to fully extract energy from the quantum source is the assumption that any unitary operation can be done on the system. We propose an approach to optimize the extractable energy inspired by the variational quantum eigensolver (VQE) algorithm.
  arXiv  Detail & Related papers  (2023-10-11T15:59:54Z)
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters [0.0]
  We show that higher order CD corrections allow for a quicker convergence to the exact solution of the problem at hand. Remarkably, however, the total number of free parameters needed to achieve this result is independent of the particular QAOA variant analyzed.
  arXiv  Detail & Related papers  (2023-07-26T10:02:47Z)
• Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate [0.6445605125467572]
  Variational Quantum Algorithms (VQAs) have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the emphdepth' of the variational ansatz'' used. We show that approximating the optimal depth for a given VQA ansatz is intractable.
  arXiv  Detail & Related papers  (2022-11-22T19:00:01Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry [10.967081346848687]
  We study the performance of the quantum approximate optimization algorithm (QAOA) for preparing ground states of target Hamiltonians. We propose a generalized QAOA assisted by the parameterized resource Hamiltonian to achieve a better performance. Our work paves the way for performing QAOA on programmable quantum processors without translational symmetry.
  arXiv  Detail & Related papers  (2022-06-06T14:17:58Z)
• Quantum Davidson Algorithm for Excited States [42.666709382892265]
  We introduce the quantum Krylov subspace (QKS) method to address both ground and excited states. By using the residues of eigenstates to expand the Krylov subspace, we formulate a compact subspace that aligns closely with the exact solutions. Using quantum simulators, we employ the novel QDavidson algorithm to delve into the excited state properties of various systems.
  arXiv  Detail & Related papers  (2022-04-22T15:03:03Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Shortcuts to Quantum Approximate Optimization Algorithm [2.150418646956503]
  We propose a new ansatz dubbed as "Shortcuts to QAOA" (S-QAOA) S-QAOA provides shortcuts to the ground state of target Hamiltonian by including more two-body interactions and releasing the parameter freedoms. Considering the MaxCut problem and Sherrington-Kirkpatrick (SK) model, numerically shows the YY interaction has the best performance.
  arXiv  Detail & Related papers  (2021-12-21T02:24:19Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz [0.4881924950569191]
  We study a family of quantum circuits called the Hamiltonian Variational Ansatz (HVA) HVA exhibits favorable structural properties such as mild or entirely absent barren plateaus and a restricted state space. HVA can find accurate approximations to the ground states of a modified Haldane-Shastry Hamiltonian on a ring.
  arXiv  Detail & Related papers  (2020-08-07T01:28:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.