  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.
