Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

• URL: http://arxiv.org/abs/2608.01121v3
• Date: Thu, 06 Aug 2026 09:13:43 GMT
• Title: Polynomial Time Quantum Approximation Schemes for Constrained Optimisation
• Abstract summary: We build on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA.<n>We introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical-processing cost by one power of the problem size.<n> Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables or improve every tested QOptlib reference tour.
• Score: 0.2578242050187029
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: When does a noisy quantum sampler yield an end-to-end polynomial-time optimization algorithm with performance guarantees? Building on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA, we show that inverse-polynomial ideal probability on the optimal set, together with independent sampling, polynomial-time feasibility repair, and scoring, produces an exact-hit fully polynomial randomized approximation scheme, which we call an FPRASq. This guarantee survives device noise within an instance-dependent window. For effective circuit depth linear in the product of layer count and problem size, preserving an inverse-depth fraction of the ideal optimal mass increases the required shot complexity by one power of the problem size. Beyond this window, deterministic repair guarantees feasibility and provides an instance-dependent approximation guarantee whenever the induced objective inflation is controlled. The resulting NP-HQ algorithm fits the Chen-Cotler-Huang-Li oracle model. On any NP-hard kernel-admissible promise family, reproducing its inverse-polynomial optimal overlap with a polynomial-time classical sampler would imply that NP is contained in BPP, even with identical repair and perfect access to the constraint structure. Thus, the separation lies in generating the sampling distribution. We further introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical post-processing cost by one power of the problem size. Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables and match or improve every tested QOptlib reference tour.

Related papers

• Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity [68.54852541944625]
  Black-box optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations.<n>We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters.
  arXiv  Detail & Related papers  (2026-05-29T14:24:54Z)
• Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization [0.7009487789080343]
  We investigate ancilla-free linear combination of unitaries (LCU) as a framework for approximating complex quantum circuits.<n>We show that Fourier-based LCU constructions efficiently decompose broad classes of diagonal and non-diagonal unitaries.
  arXiv  Detail & Related papers  (2026-05-18T18:05:08Z)
• Iterative Optimization with Partial Convergence Guarantees on Neutral Atom Quantum Computers [0.0]
  Lp-Quts is a hybrid quantum-classical framework that integrates an NAQC sampler into a classical cutting-plane algorithm.<n>We show how Lp-Quts can be effectively embedded within classical optimization frameworks to deliver near-optimal solutions with reduced quantum resources.
  arXiv  Detail & Related papers  (2026-03-30T19:12:21Z)
• Global Optimization for Parametrized Quantum Circuits [3.558201566667322]
  We study the training of practical classes of quantum circuits with a constant number of trainable parameters.<n>Our main result is a fully randomized approximation scheme (FPRAS)<n>Unlike the standard hybrid quantum-classical training in variational algorithms, our approach separates the computation into two distinct stages.
  arXiv  Detail & Related papers  (2026-03-23T09:49:40Z)
• BandPO: Bridging Trust Regions and Ratio Clipping via Probability-Aware Bounds for LLM Reinforcement Learning [49.25750348525603]
  BandPO replaces canonical clipping with Band, a unified theoretical operator that projects trust regions into dynamic, probability-aware clipping intervals.<n>We show that BandPO consistently outperforms canonical clipping and Clip-Higher, while robustly mitigating entropy collapse.
  arXiv  Detail & Related papers  (2026-03-05T08:03:05Z)
• Quantum Speedups for Group Relaxations of Integer Linear Programs [3.4310967861393418]
  Super-quadratic quantum speedups for ILPs have been difficult to obtain because classical algorithms for many-constraint ILPs are global and exhaustive.<n>We present a competitive feasibility-preserving classical local-search algorithm for the group relaxation, and a corresponding quantum algorithm that, under reasonable technical conditions, achieves a super-quadratic speedup.
  arXiv  Detail & Related papers  (2026-02-13T21:58:59Z)
• Tensor Network Assisted Distributed Variational Quantum Algorithm for Large Scale Combinatorial Optimization Problem [19.046113542182436]
  We propose the Distributed Variational Quantum Algorithm (DVQA) for solving Combinatorial Optimization Problems (COPs)<n>A key innovation of DVQA is its use of the truncated higher-order singular value decomposition to preserve inter-variable dependencies without relying on complex long-range entanglement.<n> Empirically, DVQA achieves state-of-the-art performance in simulations and has been experimentally validated on the Wu Kong quantum computer for portfolio optimization.
  arXiv  Detail & Related papers  (2026-01-20T13:31:02Z)
• Thompson Sampling via Fine-Tuning of LLMs [68.1722422968855]
  We propose an alternative based on Thompson sampling that eliminates the need for scalable large acquisition functions.<n>Our approach Thompson Sampling via Finening (ToSFiT) leverages the prior knowledge embedded in prompt-conditioned language models, and adapts incrementally toward the posterior.<n>Our analysis reveals the critical role of careful adaptation to the posterior probability of maximality-a principle that underpins our ToSFiT algorithm.
  arXiv  Detail & Related papers  (2025-10-15T09:13:59Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach.<n>Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Harmonic Path Integral Diffusion [0.4527270266697462]
  We present a novel approach for sampling from a continuous multivariate probability distribution, which may either be explicitly known (up to a normalization factor) or represented via empirical samples. Our method constructs a time-dependent bridge from a delta function centered at the origin of the state space at $t=0$, transforming it into the target distribution at $t=1$. We contrast these algorithms with other sampling methods, particularly simulated and path integral sampling, highlighting their advantages in terms of analytical control, accuracy, and computational efficiency.
  arXiv  Detail & Related papers  (2024-09-23T16:20:21Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy. Many algorithms for IRL have an inherently nested structure. We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
  arXiv  Detail & Related papers  (2022-10-04T17:13:45Z)
• Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees [39.287388288477096]
  We consider the task of estimating a structural model of dynamic decisions by a human agent based upon the observable history of implemented actions and visited states. This problem has an inherent nested structure: in the inner problem, an optimal policy for a given reward function is identified while in the outer problem, a measure of fit is maximized. We propose a single-loop estimation algorithm with finite time guarantees that is equipped to deal with high-dimensional state spaces.
  arXiv  Detail & Related papers  (2022-10-04T00:11:38Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.