Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor

Abstract

This paper presents a new hybrid classical-quantum approach to solve Mixed Integer Linear Programming (MILP) using neutral atom quantum computations. We apply Benders decomposition (BD) to segment MILPs into a master problem (MP) and a subproblem (SP), where the MP is addressed using a neutral-atom device, after being transformed into a Quadratic Unconstrained Binary Optimization (QUBO) model, with an automatized procedure. Our MILP to QUBO conversion tightens the upper bounds of the involved continuous variables, positively impacting the required qubit count, and the convergence of the algorithm. To solve the QUBO, we develop a heuristic for atom register embedding and apply a variational algorithm for pulse shaping. In addition, we implement a Proof of Concept (PoC) that outperforms existing solutions. We also conduct preliminary numerical results: in a series of small MILP instances our algorithm identifies over 95 percent of feasible solutions of high quality, outperforming classical BD approaches where the MP is solved using simulated annealing. To the best of our knowledge, this work is the first to utilize a neutral atom quantum processor in developing an automated, problem-agnostic framework for solving MILPs through BD.

16 pages, 6 figures

References in corpus (12)

• The theory of variational hybrid quantum-classical algorithms
• Adiabatic Quantum Computing
• Superconducting Qubits: Current State of Play
• Quantum computing with neutral atoms
• A compact ion-trap quantum computing demonstrator
• Hybrid Quantum-Classical Approach to Quantum Optimal Control
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Interfacing scalable photonic platforms: solid-state based multi-photon interference in a reconfigurable glass chip
• Quantum pricing-based column-generation framework for hard combinatorial problems
• Environment-assisted analog quantum search
• Functional completeness of planar Rydberg blockade structures

Cited by in corpus (5)

• Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach
• Implementing transferable annealing protocols for combinatorial optimisation on neutral atom quantum processors: a case study on smart-charging of electric vehicles
• Topological order in symmetric blockade structures
• A Quantum Constraint Generation Framework for Binary Linear Programs
• Enhancing the Performance of Quantum Neutral-Atom-Assisted Benders Decomposition