Convergence guarantee for linearly-constrained combinatorial optimization with a quantum alternating operator ansatz
Open Access
- 8 September 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
Abstract
We present a quantum alternating operator ansatz (QAOA + ) that solves a class of linearly constrained optimization problems by evolving a quantum state within a Hilbert subspace of feasible problem solutions. Our main focus is on a class of problems with a linear constraint containing sequential integer coefficients. For problems in this class, we devise QAOA + circuits that provably converge to the optimal solution as the number of circuit layers increases, generalizing previous guarantees for solving unconstrained problems or problems with symmetric constraints. Our approach includes asymmetric “mixing” Hamiltonians that drive transitions between feasible states, as well as a method to incorporate an arbitrary known feasible solution as the initial state, each of which can be applied beyond the specific linear constraints considered here. This analysis extends QAOA + performance guarantees to a more general set of linearly-constrained problems and provides tools for future generalizations.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Constrained optimization via quantum Zeno dynamicsCommunications Physics, 2023
- Approaches to Constrained Quantum Approximate OptimizationSN Computer Science, 2023
- Constrained quantum optimization for extractive summarization on a trapped-ion quantum computerScientific Reports, 2022
- Scaling quantum approximate optimization on near-term hardwareScientific Reports, 2022
- Multi-angle quantum approximate optimization algorithmScientific Reports, 2022
- Empirical performance bounds for quantum approximate optimizationQuantum Information Processing, 2021
- Variational quantum algorithmsNature Reviews Physics, 2021
- Quantum approximate optimization of non-planar graph problems on a planar superconducting processorNature Physics, 2021
- A quantum walk-assisted approximate algorithm for bounded NP optimisation problemsQuantum Information Processing, 2019
- Reducibility among Combinatorial Problems1972