Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-$k$-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.

References in corpus (32)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Quantum Computing in the NISQ era and beyond
• Ising formulations of many NP problems
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum error correction below the surface code threshold
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Warm-starting quantum optimization
• $XY$-mixers: analytical and numerical results for QAOA
• A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
• Challenges and Opportunities in Quantum Optimization
• IBM Quantum Computers: Evolution, Performance, and Future Directions
• Efficient quantum algorithms for $GHZ$ and $W$ states, and implementation on the IBM quantum computer
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Training A Quantum Optimizer
• Constrained mixers for the quantum approximate optimization algorithm
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Quantum Approximate Multi-Objective Optimization
• A SAT approach to the initial mapping problem in SWAP gate insertion for commuting gates
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
• Bias-field digitized counterdiabatic quantum optimization
• Performance of Quantum Approximate Optimization with Quantum Error Detection
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization