A Quantum Time-Space Tradeoff for Directed st-Connectivity

2025/10/09 by Jeffery, Stacey, Pass, Galina
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2510.08403

Abstract

Directed st-connectivity (DSTCON) is the problem of deciding if there exists a directed path between a pair of distinguished vertices s and t in an input directed graph. This problem appears in many algorithmic applications, and is also a fundamental problem in complexity theory, due to its \sf NL-completeness. We show that for any S≥ log²(n), there is a quantum algorithm for DSTCON using space S and time T≤ 2^{(1)/(2)log(n)log(n/S)+o(log2(n))}, which is an (up to quadratic) improvement over the best classical algorithm for any S=o(√(n)). Of the S total space used by our algorithm, only O(log²(n)) is quantum space - the rest is classical. This effectively means that we can trade off classical space for quantum time.

Citations

• Space-Efficient Quantum Error Reduction without log Factors
• Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer
• Quantum Algorithms for Graph Connectivity and Formula Evaluation
• Bounds on monotone switching networks for directed connectivity
• Creating superpositions that correspond to efficiently integrable probability distributions

Related

• Directed st-connectivity with few paths is in quantum logspace
• Time and Space Efficient Quantum Algorithms for Detecting Cycles and\n Testing Bipartiteness
• Quantum algorithms through graph composition
• Spatial search using the discrete time quantum walk
• Advances in quantum algorithms for the shortest path problem