Iterative Optimization with Partial Convergence Guarantees on Neutral Atom Quantum Computers

• URL: http://arxiv.org/abs/2603.28933v1
• Date: Mon, 30 Mar 2026 19:12:21 GMT
• Title: Iterative Optimization with Partial Convergence Guarantees on Neutral Atom Quantum Computers
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neutral atom quantum computers (NAQCs) have emerged as a promising platform for solving the maximum weighted independent set (MWIS) problem. However, analog quantum approaches face two key limitations: constraints of the atomic layout on realizable graph geometries and the absence of performance guarantees. We introduce Lp-Quts, a hybrid quantum-classical framework that integrates an NAQC sampler into a classical cutting-plane algorithm. At each iteration, a relaxed linear program (RLP) bounds the MWIS and induces a reduced graph from which independent sets are sampled using an analog quantum sampler. A novel sample-informed separation problem guides odd-cycle cut selection and accelerates convergence. For t-perfect graphs, Lp-Quts inherits polynomial-time convergence guarantees from the classical theory of cutting planes. We evaluate our approach on instances with up to 300 vertices -- a scale that exceeds the capabilities of current NAQC hardware. In this regime, Lp-Quts reaches solutions within 5--10\% of optimality, outperforming direct analog quantum protocols and greedy baselines under equal sampling budgets. As expected, simulated annealing remains the strongest sample-based solver at this scale. These results demonstrate how quantum samplers can be effectively embedded within classical optimization frameworks to deliver near-optimal solutions with reduced quantum resources while preserving formal guarantees.

Related papers

• Quantum Optimization Methods for the Generalized Traveling Salesman Problem [2.4029307306254513]
  This paper studies quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP)<n>We propose a novel GTSP QUBO formulation focused on maintaining feasible solutions for quantum annealing.<n>We implement a constrained QAOA variant using an XY-mixer, which preserves the stepwise Hamming weight in the ideal circuit model.
  arXiv  Detail & Related papers  (2026-04-28T11:58:35Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Scalable Quantum Optimisation using HADOF: Hamiltonian Auto-Decomposition Optimisation Framework [0.0]
  Quantum Annealing (QA) and QAOA are promising quantum optimisation algorithms used for finding approximate solutions to problems on near-term NISQ systems.<n>We present the Hamiltonian Auto-Decomposition optimisation Framework (HADOF), which leverages an iterative strategy to automatically divide the Quadratic Unconstrained Binary optimisation (QUBO) Hamiltonian into sub-Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-03T11:54:41Z)
• Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem [0.11242503819703255]
  Quantum Classical Branch-and-Price (QCBP) is a hybrid quantum-classical algorithm for the Vertex Coloring problem on neutral-atom Quantum Processing Units (QPUs)
  arXiv  Detail & Related papers  (2025-08-26T10:03:56Z)
• Quantum Annealing for Machine Learning: Applications in Feature Selection, Instance Selection, and Clustering [41.94295877935867]
  We implement both quantum and classical solvers to compare their effectiveness.<n>For feature selection, we propose several QUBO configurations that balance feature importance and redundancy.<n>In instance selection, we propose a few novels for instance-level importance measures that extend existing methods.<n>For clustering, we embed a classical-to-quantum pipeline, using classical clustering followed by QUBO-based medoid refinement.
  arXiv  Detail & Related papers  (2025-07-20T17:59:14Z)
• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [50.95799256262098]
  Variational quantum circuits (VQCs) hold promise for quantum machine learning but face challenges in expressivity, trainability, and noise resilience.<n>We propose VQC-MLPNet, a hybrid architecture where a VQC generates the first-layer weights of a classical multilayer perceptron during training, while inference is performed entirely classically.
  arXiv  Detail & Related papers  (2025-06-12T01:38:15Z)
• Analog QAOA with Bayesian Optimisation on a neutral atom QPU [0.0]
  We implement the Quantum Approximate optimisation algorithm in its analog form to solve the Maximum Independent Set problem.<n>We evaluate the approach through a combination of simulations and experimental runs on Pasqal's first commercial quantum processing unit, Orion Alpha.<n>Results show that a limited number of measurements still allows for a quick convergence to a solution, making it a viable solution for resource-efficient scenarios.
  arXiv  Detail & Related papers  (2025-01-27T17:23:52Z)
• Projective Quantum Eigensolver with Generalized Operators [0.0]
  We develop a methodology for determining the generalized operators in terms of a closed form residual equations in the PQE framework. With the application on several molecular systems, we have demonstrated our ansatz achieves similar accuracy to the (disentangled) UCC with singles, doubles and triples.
  arXiv  Detail & Related papers  (2024-10-21T15:40:22Z)
• Optimizing Unitary Coupled Cluster Wave Functions on Quantum Hardware: Error Bound and Resource-Efficient Optimizer [0.0]
  We study the projective quantum eigensolver (PQE) approach to optimizing unitary coupled cluster wave functions on quantum hardware.<n>We derive a bound relating off-diagonal coefficients (residues) of the Hamiltonian to the energy error of the algorithm and the overlap achieved by the obtained wavefunction.
  arXiv  Detail & Related papers  (2024-10-19T15:03:59Z)
• Quantum Gate Optimization for Rydberg Architectures in the Weak-Coupling Limit [55.05109484230879]
  We demonstrate machine learning assisted design of a two-qubit gate in a Rydberg tweezer system. We generate optimal pulse sequences that implement a CNOT gate with high fidelity. We show that local control of single qubit operations is sufficient for performing quantum computation on a large array of atoms.
  arXiv  Detail & Related papers  (2023-06-14T18:24:51Z)
• A self-consistent field approach for the variational quantum eigensolver: orbital optimization goes adaptive [52.77024349608834]
  We present a self consistent field approach (SCF) within the Adaptive Derivative-Assembled Problem-Assembled Ansatz Variational Eigensolver (ADAPTVQE) This framework is used for efficient quantum simulations of chemical systems on nearterm quantum computers.
  arXiv  Detail & Related papers  (2022-12-21T23:15:17Z)
• 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)

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.