Quantum pricing-based column-generation framework for hard combinatorial problems

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 (3)

• Towards fault-tolerant quantum computing with trapped ions
• Quantum computing with neutral atoms
• Controlling many-body dynamics with driven quantum scars in Rydberg atom arrays

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