Quantum pricing-based column-generation framework for hard combinatorial problems
arXiv:2301.02637 · doi:10.1103/PhysRevA.107.032426
Abstract
In this work, we present a complete hybrid classical-quantum algorithm involving a quantum sampler based on neutral atom platforms. This approach is inspired by classical column generation frameworks developed in the field of Operations Research and shows how quantum procedures can assist classical solvers in addressing hard combinatorial problems. We benchmark our method on the Minimum Vertex Coloring problem and show that the proposed hybrid quantum-classical column generation algorithm can yield good solutions in relatively few iterations. We compare our results with state-of-the-art classical and quantum approaches.
References in corpus (15)
- Noisy intermediate-scale quantum (NISQ) algorithms
- Adiabatic Quantum Computing
- Superconducting Qubits: Current State of Play
- Towards fault-tolerant quantum computing with trapped ions
- Quantum computing with neutral atoms
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Controlling many-body dynamics with driven quantum scars in Rydberg atom arrays
- A compact ion-trap quantum computing demonstrator
- Quantum Annealing: An Overview
- Implementation of quantum imaginary-time evolution method on NISQ devices: Nonlocal approximation
- Pulser: An open-source package for the design of pulse sequences in programmable neutral-atom arrays
- Interfacing scalable photonic platforms: solid-state based multi-photon interference in a reconfigurable glass chip
- Benchmarking quantum co-processors in an application-centric, hardware-agnostic and scalable way
- Constrained quantum annealing of graph coloring
- Environment-assisted analog quantum search
Cited by in corpus (9)
- Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
- Annealing-Assisted Column Generation for Inequality-Constrained Combinatorial Optimization Problems
- Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor
- Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach
- Quantum Reservoir Computing for Realized Volatility Forecasting
- Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
- Enhancing the Performance of Quantum Neutral-Atom-Assisted Benders Decomposition
- Efficient Construction of Feasible Solutions in Column Generation using Quantum Annealing
- Leveraging Analog Neutral Atom Quantum Computers for Diversified Pricing in Hybrid Column Generation Frameworks