Quantum-Assisted Bellman-Ford Algorithm: Conditional Quadratic Speedups for Single-Source Shortest Paths with Negative Weights

The Bellman-Ford algorithm computes single-source shortest paths in graphs with negative edge weights but requires \(O(V E)\) time in the worst case. We propose a Quantum-assisted Bellman-Ford (QBF) algorithm that maintains exactness and negative-cycle detection while achieving conditional quadratic speedups through quantum subroutines. Our approach employs quantum early-termination oracles (QET) using amplitude amplification to detect relaxable edges, and quantum relaxable-edge search (QRES) to find improving edges faster when many exist. QBF preserves correctness through classical verification of all quantum-found candidates. Under ideal QRAM assumptions, we achieve \(O(√E/M_t)\) complexity per iteration when \(M_t\) edges are relaxable, providing speedups in dense-update regimes while gracefully degrading to classical performance in sparse cases. Experimental validation on synthetic and realworld graphs demonstrates practical improvements of 2-4× in simulator wall-time for graphs with frequent relaxations, with robust error mitigation through zero-noise extrapolation. Our work establishes the first quantum algorithm for exact shortest paths with negative weights that maintains polynomial space complexity while offering conditional quantum advantage.