Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
arXiv:2410.05703 · doi:10.1109/TQE.2025.3602404
Abstract
Combinatorial optimization is a promising area for achieving quantum speedup. Quantum approximate optimization algorithm (QAOA) is designed to search for low-energy states of the Ising model, which correspond to near-optimal solutions of combinatorial optimization problems (COPs). However, effectively dealing with constraints of COPs remains a significant challenge. Existing methods, such as tailoring mixing operators, are typically limited to specific constraint types, like one-hot constraints. To address these limitations, we introduce a method for engineering a compressed space that represents the feasible solution space with fewer qubits than the original. Our approach includes a scalable technique for determining the unitary transformation between the compressed and original spaces on gate-based quantum computers. We then propose compressed space QAOA, which seeks near-optimal solutions within this reduced space, while utilizing the Ising model formulated in the original Hilbert space. Experimental results on a quantum simulator demonstrate the effectiveness of our method in solving various constrained COPs.
14 pages, 9 figures
References in corpus (25)
- Ising formulations of many NP problems
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
- Subspace-search variational quantum eigensolver for excited states
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
- Finding Exponential Product Formulas of Higher Orders
- Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
- Barren Plateaus in Variational Quantum Computing
- -mixers: analytical and numerical results for QAOA
- Resource-efficient digital quantum simulation of -level systems for photonic, vibrational, and spin- Hamiltonians
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- MAXCUT QAOA performance guarantees for p >1
- Hamiltonian variational ansatz without barren plateaus
- Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
- Variational Quantum Algorithm for Non-equilibrium Steady States
- Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
- Variational Gibbs State Preparation on NISQ devices
- Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems
- Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing