QuantGraph: A Receding-Horizon Quantum Graph Solver
Organizations: Department of Engineering Science, University of Oxford, Oxford OX1 3PJ, United Kingdom · Hitachi Cambridge Laboratory, J. J. Thomson Avenue, Cambridge CB3 0HE, United Kingdom · School of Physics, Trinity College Dublin, College Green, Dublin D02 K8N4, Ireland · Department of Physics, King’s College London, Strand, London WC2R 2LS, United Kingdom
Abstract
Dynamic programming is a cornerstone of graph-based optimization. While effective, it scales unfavorably with problem size. In this work, we present QuantGraph, a two-stage quantum-enhanced framework that casts local and global graph-optimization problems as quantum-searches over discrete trajectory spaces. The solver is designed to operate efficiently by first finding a sequence of locally optimal transitions in the graph (local stage), without considering full trajectories. The accumulated cost of the resulting candidate acts as a threshold that prunes the search space (up to 60% reduction for certain examples). The subsequent global stage, based on this threshold, refines the solution. To achieve scalability and robustness, we draw on principles from control theory and embed QuantGraph's global stage within a receding-horizon model-predictive-control scheme. This classical layer stabilizes and guides the quantum search, improving precision and reducing computational burden. In practice, the resulting closed-loop system exhibits robust behavior and lower query complexity. Notably, for a fixed control horizon and query budget, QuantGraph supports approximately twice as many control discretization bits while still benefiting from Grover-search's inherent quadratic speedup compared to classical methods.
Figures & tables
| Trajectories | Cost |
|---|---|
| 23 | |
| 18 | |
| 22 | |
| 34 | |
| 29 |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Setting | Double integrator | Cart pole |
|---|---|---|
| Time interval [ ] | ||
| Duration [ ] | ||
| Initial state | ||
| Target state | ||
| Local control bits | Disabled | |
| Global control bits |