QuantGraph: A Receding-Horizon Quantum Graph Solver
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912771128426496 |
|---|---|
| author | Vaidhyanathan, Pranav Papatheodorou, Aristotelis Arvidsson-Shukur, David R. M. Mitchison, Mark T. Ares, Natalia Havoutis, Ioannis |
| author_facet | Vaidhyanathan, Pranav Papatheodorou, Aristotelis Arvidsson-Shukur, David R. M. Mitchison, Mark T. Ares, Natalia Havoutis, Ioannis |
| contents | 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 these transitions 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. Both stages utilize variants of the Grover-adaptive-search algorithm. 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 overall complexity. Notably, for a fixed query budget, QuantGraph attains a 2x increase in control-discretization precision while still benefiting from Grover-search's inherent quadratic speedup compared to classical methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_15476 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | QuantGraph: A Receding-Horizon Quantum Graph Solver Vaidhyanathan, Pranav Papatheodorou, Aristotelis Arvidsson-Shukur, David R. M. Mitchison, Mark T. Ares, Natalia Havoutis, Ioannis Quantum Physics Robotics Systems and Control Computational Physics 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 these transitions 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. Both stages utilize variants of the Grover-adaptive-search algorithm. 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 overall complexity. Notably, for a fixed query budget, QuantGraph attains a 2x increase in control-discretization precision while still benefiting from Grover-search's inherent quadratic speedup compared to classical methods. |
| title | QuantGraph: A Receding-Horizon Quantum Graph Solver |
| topic | Quantum Physics Robotics Systems and Control Computational Physics |
| url | https://arxiv.org/abs/2512.15476 |