(No) Quantum Space-Time Tradeoff for USTCON

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 = O^e(n²/S) for any S such that S = Ω(log(n)) and S = O(n²/m). Surprisingly, we show that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time O^e(n) and space O(log(n)) simultaneously. This improves on previous results, which required either O(log(n)) space and O^e(n^1.5) time, or O^e(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.