A gate-time feasibility analysis of quantum breadth-first search for maximum flow problems

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.