quant-phDec 17, 2025

QuantGraph: A Receding-Horizon Quantum Graph Solver

Authors: Pranav Vaidhyanathan, Aristotelis Papatheodorou, David R. M. Arvidsson-Shukur, Mark T. Mitchison, Natalia Ares, Ioannis Havoutis

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

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Sep 17, 2026

Quantum Graph Convolutional Networks: Implementation and Trainability Analysis

Graph Neural Networks (GNNs) achieve state-of-the-art performance on graph-structured data, but training and inference on large graphs are often bottlenecked by memory constraints and sparse linear-algebra workloads. Quantum computing offers an alternative set of primitives that may improve scalability for graph learning. Building on the quantum graph neural network (QGNN) framework of Liao et al., this work implements two representative architectures --- the Simplified Graph Convolution (SGC) and Linear Graph Convolution (LGC) models --- and evaluates them on open benchmark graph datasets and semi-supervised learning tasks using quantum simulation. We compare predictive performance and optimization behavior against classical baselines, showing that the quantum models achieve competitive performance with fewer parameters. Finally, we present a cost gradient analysis that identifies the tasks for which the models showcased are trainable. This is followed by a classical simulability study to find regimes in which the proposed circuits remain robust during training.
May 8, 2026

Optimal FALQON for Quantum Approximate Optimization via Layer-wise Parameter Tuning

Feedback-based adaptive quantum optimization (FALQON) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum devices, but prior studies report that standard fixed-parameter schedules can require relatively deep circuits to reach strong solution quality. We study Optimal FALQON, a layer-wise formulation that treats the time-step δkδ_k and scaling parameter wkw_k as classical decision variables optimized per layer. The benchmark uses all 94 non-isomorphic 3-regular graphs with 12 vertices under 8192-shot simulation and compares standard FALQON, Optimal FALQON, and QAOA/QAOA-MA Powell runs warm-started from FALQON-derived schedules. Across approximation ratio, success probability, evaluation-normalized efficiency, and layer-normalized efficiency, Optimal FALQON substantially improves on standard FALQON, and Optimal-FALQON warm starts substantially improve on standard-FALQON warm starts.
Mar 12, 2026

Quantum mechanical framework for quantization-based optimization: from Gradient flow to Schroedinger equation

This work presents a quantum mechanical framework for analyzing quantization-based optimization algorithms. The sampling process of the quantization-based search is modeled as a gradient-flow dissipative system, leading to a Hamilton-Jacobi-Bellman (HJB) representation. Through a suitable transformation of the objective function, this formulation yields the Schroedinger equation, which reveals that quantum tunneling enables escape from local minima and guarantees access to the global optimum. By establishing the connection to the Fokker-Planck equation, the framework provides a thermodynamic interpretation of global convergence. Such an analysis between the thermodynamic and the quantum dynamic methodology unifies combinatorial and continuous optimization, and extends naturally to machine learning tasks such as image classification. Numerical experiments demonstrate that quantization-based optimization consistently outperforms conventional algorithms across both combinatorial problems and nonconvex continuous functions.