2025-10-09
A quantum time-space tradeoff for directed st-connectivity
Publication
Publication
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\geq \log^2(n)$, there is a quantum algorithm for DSTCON using space $S$ and time $T\leq 2^{\frac{1}{2}\log(n)\log(n/S)+o(\log^2(n))}$, which is an (up to quadratic) improvement over the best classical algorithm for any $S=o(\sqrt{n})$. Of the $S$ total space used by our algorithm, only $O(\log^2(n))$ is quantum space - the rest is classical. This effectively means that we can trade off classical space for quantum time.
| Additional Metadata | |
|---|---|
| doi.org/10.48550/arXiv.2510.08403 | |
| ASC-Q | |
| Organisation | Algorithms and Complexity |
|
Jeffery, S., & Pass, G. (2025). A quantum time-space tradeoff for directed st-connectivity. doi:10.48550/arXiv.2510.08403 |
|
