The Overlap Gap Property limits limit swapping in the QAOA

• URL: http://arxiv.org/abs/2404.06087v6
• Date: Sat, 02 Aug 2025 11:45:49 GMT
• Title: The Overlap Gap Property limits limit swapping in the QAOA
• Authors: Mark Goh,
• Abstract summary: The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP)<n>We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erd"os--R'enyi hypergraph, then a random regular hypergraph is similarly limited in as well.
• Score: 5.578103948136372
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP). We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erd\"os--R\'enyi hypergraph, then a random regular hypergraph is similarly limited in performance as well. As such, we re-derived the fact that the average-case value obtained by the QAOA for even $q\ge 4$, Max-$q$-XORSAT is bounded away from optimality when optimised using asymptotic analysis due to the Overlap Gap Property (OGP). While this result was proven before, the proof is rather technical compared to ours. In addition, we show that the earlier result implicitly also implies limitation at logarithmic depth $p \le \epsilon \log n$ providing an improvement over limitation at constant depth. Furthermore, the extension to logarithmic depth leads to a tightening of the upper bound that the QAOA outputs at logarithmic depth for MaxCUT and Max-$q$-XORSAT problems. We also provide some numerical evidence the limitation should be extended to odd $q$ by showing that the OGP exists for the Max-$3$-XORSAT on random regular graphs.

Related papers

• On Speedups for Convex Optimization via Quantum Dynamics [2.5094874597551913]
  We explore the potential for quantum speed in convex optimization using discrete simulations of the Quantum Hamiltonian Descent framework. In continuous time, we demonstrate that QHD, with suitable parameters, can achieve arbitrarily fast convergence rates. We show that QHD offers a super-quadratic query advantage over all known classical algorithms tolerating this level of evaluation noise.
  arXiv  Detail & Related papers  (2025-03-31T17:21:12Z)
• Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA [0.027042267806481293]
  We study MaxCut on 3-regular graphs of minimum girth $g$ for various $g$'s.<n>For $g geq 16$, at depth $p geq 7$, the QAOA improves on previously known lower bounds.
  arXiv  Detail & Related papers  (2025-03-17T03:58:43Z)
• Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems [0.0]
  The ability of the Quantum Approximate Optimization Algorithm to deliver a quantum advantage on optimization problems is still unclear. We analyze the QAOA's performance on random Max-$k$XOR as a function of $k$ and the clause-to-variable ratio. We find that reaching high levels of satisfaction would require extremely large $p$, which must be considered rather difficult both in the variational context and on near-term devices.
  arXiv  Detail & Related papers  (2024-11-28T21:39:58Z)
• Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
  Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid algorithm proposed with the goal of approximately solving optimization problems such as the MAX-CUT problem. We first analytically prove the performance limitations of level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. Second, we demonstrate that Recursive QAOA (RQAOA), which reduces graph size using QAOA as a subroutine, outperforms the level-1 QAOA. Finally, we show that RQAOA with a restricted parameter regime can fully address these limitations.
  arXiv  Detail & Related papers  (2024-08-23T16:35:47Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Extending relax-and-round combinatorial optimization solvers with quantum correlations [0.0]
  We introduce a relax-and-round approach embedding the quantum approximate optimization algorithm (QAOA) with $pgeq 1$ layers. We show for many problems, including Sherrington-Kirk glasses, that at $p=1$, it is as accurate as its classical counterpart. We pave the way for an overarching quantum relax-and-round framework with performance on par with some of the best classical algorithms.
  arXiv  Detail & Related papers  (2023-07-11T22:02:01Z)
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm [0.05076419064097732]
  We study the ability of QAOA to solve hard constraint satisfaction problems, as opposed to quantum computing problems. We develop analytic bounds on the average success probability of QAOA over random formulae at the satisfiability threshold. We find that for around 14 ansatz layers, QAOA matches the scaling performance of the highest-performance classical solver.
  arXiv  Detail & Related papers  (2022-08-14T20:39:48Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models [15.857373057387669]
  We prove concentration properties at any constant level (number of layers) on ensembles of random optimization problems in the infinite size limit. Our analysis can be understood via a saddle-point approximation of a sum-over-paths integral. We show that the performance of the QAOA at constant levels is bounded away from optimality for pure $q$-spin models when $qge 4$ and is even.
  arXiv  Detail & Related papers  (2022-04-21T17:40:39Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  The expected improvement (EI) algorithm is one of the most popular strategies for optimization under uncertainty. We propose a variant of EI with a standard incumbent defined via the GP predictive mean. We show that our algorithm converges, and achieves a cumulative regret bound of $mathcal O(gamma_TsqrtT)$.
  arXiv  Detail & Related papers  (2022-03-15T13:17:53Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. We introduce a emphmisspecified kernelized bandit setting where the unknown function can be $epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS) We show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
  arXiv  Detail & Related papers  (2021-11-09T09:00:02Z)
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
  The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to optimization problems. We give an iterative formula to evaluate performance for any $D$ at any depth $p$. We make an optimistic conjecture that the QAOA, as $p$ goes to infinity, will achieve the Parisi value.
  arXiv  Detail & Related papers  (2021-10-27T06:35:59Z)
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit [0.05076419064097732]
  We present an explicit algorithm to evaluate the performance of QAOA on MAX-CUT applied to random Erdos-Renyi graphs of expected degree $d$. This analysis yields an explicit mapping between QAOA parameters for MAX-CUT on Erdos-Renyi graphs, and the Sherrington-Kirkpatrick model.
  arXiv  Detail & Related papers  (2021-10-20T17:58:53Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  We introduce a batch algorithm inspired by finite-arm bandit algorithms. We show that it achieves the cumulative regret upper bound $Oast(sqrtTgamma_T)$ using $O(loglog T)$ batches within time horizon $T$. In addition, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches.
  arXiv  Detail & Related papers  (2021-10-15T00:54:04Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

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.