(No) Quantum space-time tradeoff for USTCON

Abstract

Undirected $st$-connectivity is important both for its applications in network problems, and for its theoretical connections with logspace complexity. Classically, a long line of work led to a time-space tradeoff of $T=\tilde{O}(n^2/S)$ for any $S$ such that $S=\Omega (\log (n))$ and $S=O(n^2/m)$. Surprisingly, we show that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time $\tilde{O}(n)$ and space $O(\log (n))$ simultaneously. This improves on previous results, which required either $O(\log (n))$ space and $\tilde{O}(n^{1.5})$ time, or $\tilde{O}(n)$ space and time. To complement this, we show that there is a nontrivial time-space tradeoff when given a lower bound on the spectral gap of a corresponding random walk.

17 pages, 2 figures