Quantum walks, recursion, and time-space tradeoffs for st-connectivity

This thesis studies space-bounded quantum computation, focusing on quantum algorithms in settings where memory is limited. The central goal is to understand which quantum advantages persist under such constraints and how quantum resources affect classical time-space tradeoffs. The thesis approaches these questions through st-connectivity, a central problem in space complexity theory.
We develop quantum algorithms and tradeoff results for both undirected and directed st-connectivity. In the undirected case, we show that quantum algorithms can achieve near-optimal time using only logarithmic space, in contrast to classical algorithms, which exhibit nontrivial time-space tradeoffs. This demonstrates a fundamental difference between classical and quantum computation in memory-constrained regimes.
For directed st-connectivity, we establish the first nontrivial quantum time–space tradeoff. This problem is more challenging, as techniques such as quantum walks and reversibility do not directly apply. We show that quantum computation can improve upon known classical tradeoff bounds even when only a small quantum workspace is available.
A key contribution of the thesis is a compositional framework for quantum algorithms based on multidimensional quantum walks. We introduce subspace graphs, an abstract model that enables modular design and efficient recursion without the overheads that typically slow down recursive quantum algorithms.
Finally, we extend undirected st-connectivity to unitary-labeled graphs, where edges represent quantum transformations. We present an efficient quantum algorithm for this generalized connectivity problem.
Together, these results advance the understanding of space-bounded quantum computation and quantum time-space tradeoffs.