An end-to-end hybrid quantum-classical optimisation framework based on Benders decomposition, capable of solving mixed-integer linear programming (MILP) problems and deeming quantum advantage of this framework unlikely at problems of this size.
Abstract
We demonstrate an end-to-end hybrid quantum-classical optimisation framework based on Benders decomposition, capable of solving mixed-integer linear programming (MILP) problems. The framework builds on a previously presented hybrid quantum-classical end-to-end pipeline based on Multiple Cuts via Multiple Solutions (MCMS) Benders decomposition where the cut selection step was performed on quantum annealing hardware. We extend this with gate-based QAOA implementations for both tensor network emulators and superconducting quantum hardware. The Vehicle Routing Problem (VRP) is used as a representative case study and we run the pipeline end-to-end on 10 permutations of a standardised benchmarking instance (20 customers and 4 vehicles from QOptLib) with a classical solver performing the cut selection step. We find that for our instances, only a small fraction of the compute in classical MCMS Benders decomposition is spent on the cut selection step. For a full hybrid end-to-end assessment, we run the pipeline for a toy problem with MPS-JuliQAOA, a powerful tensor network emulator, to execute QAOA. Here, the majority of the time is spent on the cut selection step, deeming quantum advantage of this framework unlikely at problems of this size. This highlights the need for more large-scale benchmarking research when more powerful (QPU) QUBO solvers are available.
The results suggest that quantum kernels may serve as complementary routing-aware decomposition modules within classical optimization pipelines, particularly for offline structural preprocessing.
Results suggest that near-term quantum sampling is most useful as a selective local repair mechanism rather than as a replacement for classical routing heuristics.
Sampling from discrete Markov random fields (MRFs) is a hard problem and amplitude-encoded i.i.d. sampling for small MRFs where $2^n$ target probabilities are precomputed classically is studied to allow a clean comparison against classical MCMC based on independent circuit samples.
Quantum Processing Units promise speed-ups for selected computational problems, including combinatorial optimisation, but their industrial utility remains an open challenge. We study an industrial variant of the Job-Shop Scheduling Problem using quantum, quantum-inspired, and classical methods across three platforms: IBM Quantum, the D-Wave Quantum Annealer, and the Fujitsu Digital Annealer. By tailoring formulations to hardware-specific constraints, we show that hardware-software co-design is essential for solution quality and scalability. We benchmark all approaches against an exact classical solver and a MILP formulation, evaluating runtime, solution quality, and scalability. Our results indicate that quantum and quantum-inspired optimisation can support industrial solver selection, integration in classical workflows, modelling decisions, and early proof-of-concept development, while suggesting a potential path towards improved approximations for industrial scheduling.
Hila Safi, Karen Wintersperger, O. Sicard et al.· 0 citations
Quantum optimization has attracted growing interest as quantum hardware continues to improve, yet state-of-the-art classical solvers remain a formidable benchmark for practical utility. Rather than seeking a fully quantum replacement for classical optimization, we propose a hybrid strategy that uses quantum information to enhance leading classical heuristics. Specifically, we introduce a warm-start method based on local correlators obtained from the Quantum Approximate Optimization Algorithm (QAOA), and use this information to initialize the Burer-Monteiro (BM) rank-two relaxation. We demonstrate numerically that, compared to a random, multi-start initialization baseline (a standard strategy used for BM), this quantum-informed initialization offers a significant head start, i.e., high-quality solutions with very small number of iterations, for two problem classes -- random Erd\H{o}s R\'{e}nyi graphs with edge density of $10\%$ (ER-10) and fully-connected Sherrington Kirkpatrick (SK) spin glass models, at $n=500$ and $n=1000$ qubits. At the same time, given enough iterations, the random baseline often eventually catches up and slightly outperforms the warm-start strategy on average, an effect visibly stronger for $n=500$ than for $n=1000$. The results demonstrate an exploitation/exploration tradeoff of using WS to quickly arrive at very good solutions vs exploring slightly better solutions with a larger iterations budget via a standard strategy. Our results highlight how low-depth quantum circuits can provide useful structural information for classical optimization and suggest a promising route toward near-term quantum utility through quantum-assisted initialization.
Bao Gia Bach, Ilya Safro, Filip B. Maciejewski· 0 citations
This paper presents a comprehensive investigation of quantum annealing and hybrid quantum-classical algorithms applied to unit load device (ULD) configuration and disruption management in air cargo and multimodal logistics networks, and provides a practical roadmap for near-term adoption of quantum technologies in high-stakes logistics environments.
V. Sharma· International Journal of Cre...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
