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