A Quantum Time-Space Tradeoff for Directed $st$-Connectivity

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 $\mathsf{NL}$-completeness. We show that for any $S\ge {\log }^2(n)$, there is a quantum algorithm for DSTCON using space $S$ and time $T\le 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.