aiqbench analysis
This paper estimates whether Grover-based quantum breadth-first search could beat classical BFS inside Dinic's max-flow algorithm, using gate counts from real datasets. Its main finding is that matching classical speed would require two-qubit gate times one to two orders of magnitude faster than the current physical record for most instances, and only about 1.3 times faster for the smallest ones. Because it uses physical rather than error-corrected gate times, the gap is likely larger, so readers should treat this as a sober feasibility bound rather than a sign of near-term advantage.
A gate-time feasibility analysis of quantum breadth-first search for maximum flow problems
arXiv:2604.24962v2 Announce Type: replace Abstract: The maximum flow problem asks to find the largest possible flow from a source to a sink in a capacitated network. It arises frequently in scheduling, project selection, and as a core subroutine in broader optimisation tasks. Classically, it can be efficiently solved using Dinic's algorithm, which repeatedly performs breadth-first search (BFS) and blocking flow computations on the graph. As a potential candidate for quantum speedups, these BFS subroutines can be naturally replaced with quantum BFS (qBFS), an instantiation of Grover's search algorithm. In this paper, we evaluate the expected performance of qBFS on standard classical datasets. These instances are too large to be solved directly on current quantum hardware, so we adopt a hybrid benchmarking approach: (i) we run a classical implementation of Dinic's algorithm and isolate the runtime of its BFS subroutines; (ii) we analytically estimate the number of two-qubit gates required to implement qBFS, where we use the classically logged data. Our results indicate that, on every tested instance, matching classical BFS would require two-qubit gate operation times below the current physical record by one to two orders of magnitude for most instances, and by a factor of about 1.3 for the smallest, most favourable ones. Since this comparison uses physical rather than error-corrected gate times, the actual gap is larger still.
Abstract:The maximum flow problem asks to find the largest possible flow from a source to a sink in a capacitated network. It arises frequently in scheduling, project selection, and as a core subroutine in broader optimisation tasks. Classically, it can be efficiently solved using Dinic's algorithm, which repeatedly performs breadth-first search (BFS) and blocking flow computations on the graph. As a potential candidate for quantum speedups, these BFS subroutines can be naturally replaced with quantum BFS (qBFS), an instantiation of Grover's search algorithm. In this paper, we evaluate the expected performance of qBFS on standard classical datasets. These instances are too large to be solved directly on current quantum hardware, so we adopt a hybrid benchmarking approach: (i) we run a classical implementation of Dinic's algorithm and isolate the runtime of its BFS subroutines; (ii) we analytically estimate the number of two-qubit gates required to implement qBFS, where we use the classically logged data. Our results indicate that, on every tested instance, matching classical BFS would require two-qubit gate operation times below the current physical record by one to two orders of magnitude for most instances, and by a factor of about 1.3 for the smallest, most favourable ones. Since this comparison uses physical rather than error-corrected gate times, the actual gap is larger still.
arXiv:2604.24962 [quant-ph]
(or arXiv:2604.24962v2 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2604.24962 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 304 words
