Directed $st$-connectivity (DSTCON) is the problem of deciding if there exists a directed path between a pair of distinguished vertices $s$ and $t$ in an input directed graph. This problem appears in many algorithmic applications, and is also a fundamental problem in complexity theory, due to its ${\sf NL}$-completeness. We show that for any $S\geq \log^2(n)$, there is a quantum algorithm for DSTCON using space $S$ and time $T\leq 2^{\frac{1}{2}\log(n)\log(n/S)+o(\log^2(n))}$, which is an (up to quadratic) improvement over the best classical algorithm for any $S=o(\sqrt{n})$. Of the $S$ total space used by our algorithm, only $O(\log^2(n))$ is quantum space - the rest is classical. This effectively means that we can trade off classical space for quantum time.
A Quantum Time-Space Tradeoff for Directed st-Connectivity
Directed st-connectivity (DSTCON) is the problem of deciding if there exists a directed path between a pair of distinguished vertices s and t in an input directed graph. This problem appears in many algorithmic applications, and is also a fundamental problem in complexity theory, due to its NL-completeness. We show that for any S≥log2(n), there is a quantum algorithm for DSTCON using space S and time T≤221log(n)log(n/S)+o(log2(n)), which is an (up to quadratic) improvement over the best classical algorithm for any S=o(n). Of the S total space used by our algorithm, only O(log2(n)) is quantum space - the rest is classical. This effectively means that we can trade off classical space for quantum time.
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.
We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs by combining different classical approaches with quantum techniques. For instance, we show that the Travelling Salesman Problem can be solved quantumly in O(1.859n) time and O(1.315n) QRAM space.
A Quantum Algorithm for st-Transport on Flat Connection Graphs
We study a generalization of undirected st-connectivity to graphs whose edges carry quantum operations. Let G=(V,E) be an undirected graph on n vertices in which each edge {u,v} is labeled by a unitary Uuv∈Ck×k, with Uvu=Uuv†. We assume the labels form a \emph{flat} connection: the ordered product of labels along any path between a pair of vertices u and v is independent of the path. Equivalently, the connection is pure gauge, i.e., gauge-equivalent to the trivial connection; such graphs are exactly the consistent connection graphs of spectral graph theory and the noiseless instances of group synchronization. Consequently, whenever s and t are connected, transporting a state from s to t defines a unique unitary Us(t). Given states ∣ψs⟩,∣ψt⟩∈Ck and an oracle that returns the neighbours of a vertex while coherently applying the corresponding edge unitaries, the \emph{st-transport problem} is to decide whether s and t are connected and, if so, to estimate the squared overlap between Us(t)∣ψs⟩ and ∣ψt⟩ to additive error ε. When k=1 and all labels are trivial, this is exactly undirected st-connectivity. We give a bounded-error quantum algorithm for st-transport that runs in time O(n/ε) and uses O(logn+logk+log(1/ε)) space. We do this by designing a transducer and applying a Metropolis-Hastings reweighting to the input graph. We also prove an Ω(n) quantum query lower bound that holds even when s and t are promised to be connected, so for constant ε our algorithm is optimal up to polylogarithmic factors.
We study space and time-efficient quantum algorithms for two graph problems – deciding whether an n-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in O˜(n 3/2 ) time whilst using O(log n) classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time O˜(n √ dm) and also require O(log n) space, where dm is the maximum degree of any vertex in the input graph.
Given an undirected, weighted graph, with n vertices and m edges, and two special vertices s and t, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in O~(l2m) expected time and uses O(logn) space on graphs where the shortest s-t path is also a minimum resistance s-t subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability q>0.537 of finding the shortest s-t path. In such cases the quantum algorithm outputs the shortest s-t path with high probability in O(ℓm) expected time and O(logn) space, where l is the length (or total weight, in case of weighted graphs) of the shortest s-t path. This algorithm can be parallelised to O~(lm) circuit depth when using O(llogn) space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.
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~(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 O~(n) and space O(log(n)) simultaneously. This improves on previous results, which required either O(log(n)) space and O~(n1.5) time, or 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.