Mechanism of Efficacy in QAOA for Random k-SAT: From Adiabatic Manifold to Sublinear Parameter Optimization

• URL: http://arxiv.org/abs/2605.20288v1
• Date: Tue, 19 May 2026 06:53:02 GMT
• Title: Mechanism of Efficacy in QAOA for Random k-SAT: From Adiabatic Manifold to Sublinear Parameter Optimization
• Abstract summary: We study QAOA for random $k$-SAT problems within a universal-mixer $k$-local search framework.<n>This correspondence yields a rigorous performance guarantee for random instances with clause density $m=O(n1+)$ and circuit depth $(n2)$.<n>We propose the smooth adiabatic-manifold parameterization (SAMP) strategy, transforming parameter optimization from an unstructured high-dimensional search into a guided refinement process.
• Score: 0.8021197489470758
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for demonstrating quantum advantage on near-term devices, yet the physical origins of its efficacy remain poorly understood. In this work, we study QAOA for random $k$-SAT problems within a universal-mixer $k$-local search framework, establishing a formal correspondence between adiabatic state transfer and the QAOA ansatz. This correspondence yields a rigorous performance guarantee for random instances with clause density $m=O(n^{1+ε})$ and circuit depth $Θ(n^2)$. We further investigate the NISQ regime with shallow circuits of depth $p=O(n)$. Surprisingly, the optimal parameters do not become stochastic under depth compression, but instead remain confined to a structured low-dimensional region, which we identify as a smooth adiabatic manifold. Numerical evidence indicates that this manifold persists across different circuit depths and arises from the variational suppression of adiabatic leakage. Based on this structure, we propose the smooth adiabatic-manifold parameterization (SAMP) strategy, transforming parameter optimization from an unstructured high-dimensional search into a guided refinement process. Numerical experiments on random 3-SAT instances show that SAMP achieves sublinear optimization scaling with circuit depth while providing robust zero-cost initialization for deep circuits.

Related papers

• Universally Empowering Zeroth-Order Optimization via Adaptive Layer-wise Sampling [43.822941944402544]
  Zeroth-Order optimization presents a promising memory-efficient paradigm for fine-tuning Large Language Models.<n>However, its practical adoption is severely constrained by slow wall-clock convergence and high estimation variance.<n>We propose AdaLeZO, an Adaptive Layer-wise ZO optimization framework.
  arXiv  Detail & Related papers  (2026-04-20T13:37:31Z)
• On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation [44.084531611147305]
  We provide a refined convergence analysis of the Single-loop Approximate Implicit Differentiation (SSAID) algorithm.<n>Our result is noteworthy in two aspects: (i) it matches the optimal $mathcalO(-2)$ rate of state-of-the-art multi-loop methods; and (ii) it provides the first explicit, fine-grained characterization of the $$-dependence.
  arXiv  Detail & Related papers  (2026-02-27T03:12:08Z)
• Evidence that the Quantum Approximate Optimization Algorithm Optimizes the Sherrington-Kirkpatrick Model Efficiently in the Average Case [3.4872784636892047]
  Sherrington-Kirkpatrick (SK) model serves as a foundational framework for understanding disordered systems.<n>Quantum Approximate Optimization Algorithm (QAOA) is a quantum optimization algorithm whose performance monotonically improves with its depth $p$.<n>We analyze QAOA applied to the SK model in the infinite-size limit and provide numerical evidence that it obtains a $(1-epsilon)$ approximation to the optimal energy with circuit depth $mathcalO(n/epsilon1.13)$ in the average case.
  arXiv  Detail & Related papers  (2025-05-12T18:00:01Z)
• Improving Quantum Optimization to Achieve Quadratic Time Complexity [13.190476985206043]
  We introduce Penta-O, a level-wise parameter-setting strategy that eliminates the classical outer loop, maintains minimal sampling overhead, and ensures non-decreasing performance.<n>For a $p$-level QAOA, Penta-O achieves an unprecedented time complexity of $mathcalO(p2)$ and a sampling overhead proportional to $5p+1$.
  arXiv  Detail & Related papers  (2025-01-23T08:33:26Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• A Recursive Lower Bound on the Energy Improvement of the Quantum Approximate Optimization Algorithm [0.0]
  We use an analytic expansion of the cost function around transition states to gain insights into the deep QAOA. Our numerical study confirms the accuracy of our approximations, and reveals that the obtained bound and the true value of the QAOA cost function gain have a characteristic exponential decrease with the number of layers $p$.
  arXiv  Detail & Related papers  (2024-05-16T14:24:37Z)
• Adiabatic-Passage-Based Parameter Setting for Quantum Approximate Optimization Algorithm [0.7252027234425334]
  We propose a novel adiabatic-passage-based parameter setting method. This method remarkably reduces the optimization cost, specifically when applied to the 3-SAT problem, to a sublinear level.
  arXiv  Detail & Related papers  (2023-11-30T01:06:41Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
  We propose a strategy to give high approximation ratio on average, even at large circuit depths, by initializing QAOA with the optimal parameters obtained from the previous depths. We test our strategy on the Max-cut problem of certain classes of graphs such as the 3-regular graphs and the Erd"os-R'enyi graphs.
  arXiv  Detail & Related papers  (2021-08-11T15:44:16Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.