A Quantum Time-Space Tradeoff for Directed st-Connectivity

Jeffery, Stacey; Pass, Galina

doi:10.4230/LIPIcs.ICALP.2026.117

A Quantum Time-Space Tradeoff for Directed $s t$ -Connectivity

Stacey Jeffery

CWI, QuSoft, Amsterdam, The Netherlands
University of Amsterdam, The Netherlands Galina Pass

QuSoft, Amsterdam, The Netherlands
University of Amsterdam, The Netherlands

Abstract

Directed $s t$ -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.

Keywords and phrases:

Quantum algorithms, time-space tradeoffs, directed st-connectivity, switching networks, space-bounded computation

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum complexity theory

Related Version:

Full Version: https://arxiv.org/abs/2510.08403

Funding:

This work is co-funded by the European Union (ERC, ASC-Q, 101040624); the project Divide & Quantum (with project number 1389.20.241) of the research programme NWA-ORC, which is (partly) financed by the Dutch Research Council (NWO); and the Dutch National Growth Fund (NGF), as part of the Quantum Delta NL programme. SJ is a CIFAR Fellow in the Quantum Information Science Program.

DOI:

10.4230/LIPIcs.ICALP.2026.117

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In the directed $s t$ -connectivity problem (dstcon), the input is a directed graph on $n$ vertices with two distinguished vertices $s$ and $t$ , and the goal is to decide if there is a directed path from $s$ to $t$ . This fundamental problem underlies a wide range of applications in (e.g.) logistics, databases [1, 19], compilers [2, 16], and model checking [10, 5].

In addition to its practical applications, dstcon plays a central role in space-bounded complexity theory. It is ${\sf NL}$ -complete (under ${\sf NC}^{1}$ reductions), where ${\sf NL}$ is the class of problems decidable by nondeterministic logspace machines. Consequently, understanding its complexity has broad implications for space-bounded computation. For example, a classical (or quantum) algorithm for dstcon using $O(\log(n))$ space would show that ${\sf L}$ , the class of problems solvable in $O(\log(n))$ space (or its quantum analogue) contains ${\sf NL}$ – a major breakthrough in either case.

Currently, the smallest space complexity of any classical or quantum algorithm for dstcon is $S=O(\log^{2}(n))$ , achieved by Savitch’s (classical) algorithm. However, Savitch’s algorithm achieves this low space complexity at the expense of a large quasipolynomial time complexity, using

T\leq 2^{\log^{2}(n)+O(\log(n))}

steps of computation. In contrast, a simple breadth-first search (BFS) algorithm solves this problem in just $T=O(n^{3})$ steps (in the adjacency-matrix model), but at the expense of a much larger $S={\widetilde{O}}(n)$ space requirement. The fundamental nature of this problem, as well as its many applications, motivates understanding the best possible tradeoff between the time and space needed to solve it. Progress was made by Barnes, Buss, Ruzzo and Schieber [6], who gave a classical algorithm that runs in time

T\leq 2^{\log^{2}(\frac{n}{S})+O(\log n\log\log n)}

(1)

given any space $S\geq\log^{2}(n)$ . Their approach combines a breadth-first search with a clever recursive algorithm.

For quantum algorithms, the study of space-bounded complexity is even more well motivated, as quantum memories are expected to be limited in size for the foreseeable future. It is an important question in which memory regimes we can still achieve speedups over classical algorithms, and time-space tradeoffs are a key part of this picture. We can make such a tradeoff even more useful by distinguishing between the quantum space and classical (or total) space needed by the algorithm, as quantum space is the scarce resource.

For dstcon, quantum speedups are known only at the two extreme regimes of space. In the high-space setting, Dürr, Heiligman, Høyer, and Mhalla [11] gave an ${\widetilde{O}}(n^{1.5})$ -time, ${\widetilde{O}}(n)$ -space algorithm using quantum search to build a spanning tree. In the low-space setting, Ref. [14] recently gave a quadratic quantum speedup over Savitch’s algorithm, running in time $T\leq 2^{\frac{1}{2}\log^{2}n+O(\log n)}$ with $S=O(\log^{2}n)$ space. Between these two extremes, however, no quantum improvements over classical tradeoffs were known.

For the undirected variant (ustcon), the picture is much clearer, at least as far as quantum algorithms go: in both the adjacency-matrix and edge-list models of graph access¹¹1In this work, unless otherwise stated, we use the adjacency-matrix model, which assumes the input is given via queries to an adjacency matrix. This distinction is only significant in high-space regimes where the time complexity is polynomial., quantum algorithms achieve optimal time and space simultaneously [9, 4].

However, existing classical and quantum approaches face significant obstacles in the directed case. A random walk on a directed graph, starting from $s$ , may fail to find $t$ even when $t$ is reachable from $s$ , if the walk leads from $s$ to some part of the graph from which $t$ is not reachable. Quantum walks, which are powerful tools for studying undirected graphs, do not generalize to directed graphs. Moreover, known classical algorithms for dstcon such as the time-space tradeoff algorithm in [6] cannot be directly quantized. This stems from the fact that these classical algorithms are not reversible, and making them reversible using standard methods increases the space complexity. These difficulties highlight why directed connectivity remains a challenging and subtle problem. They also show that progress requires algorithmic ideas that go beyond random or quantum walks, and straightforward adaptations of classical tradeoffs.

Our Contribution

We present the first nontrivial quantum time-space tradeoff for dstcon, by designing a new quantum algorithm for this problem that, for any space bound $S\geq\log^{2}(n)$ , runs in time

T\leq 2^{\frac{1}{2}\log(n)\log(\frac{n}{S})+O(\log n\log\log n)}.

In particular, our result yields a quantum speedup over the best known classical algorithm (see (1)) in the regime $S=o(n^{1/2})$ . We also show that, of the $S$ space, the required quantum space is always $O(\log^{2}(n))$ , which makes this result much more applicable to quantum computers with a limited number of qubits. This effectively means that we can tradeoff classical space for quantum time. We formally state this result in Theorem 13.

Our Techniques

The classical algorithm of Barnes et al. [6] achieves a time-space tradeoff for dstcon by combining breadth-first search with a recursive subroutine that decides, for any pair of vertices $u$ and $v$ , if there is a directed path from $u$ to $v$ of length at most $L$ . We call this problem $\textsc{Dist}_{L}$ . The breadth-first search saves on space by not traversing the whole graph, but only those vertices at a distance from $s$ that is a multiple of $L$ (the space then decreases as $L$ increases). The subroutine is used to find these vertices in a manner that is more space efficient, but less time efficient, than BFS.

The BFS portion of this classical algorithm could be sped up using quantum search techniques, but this saves at most a polynomial factor in the time (and nothing in the space), which is not very interesting in the small-space regime (where we get our quantum improvement) where such polynomial factors are hidden by the $O(\log(n))$ in the exponent. On the other hand, a direct quantization of their subroutine for $\textsc{Dist}_{L}$ fails, in large part because this subroutine is not reversible, and making it so would increase the space complexity. Moreover, the subroutine calls itself recursively, with significant depth of recursion. A quantum speedup of this subroutine would most likely have bounded error. Naively composing bounded-error quantum subroutines to depth $d$ results in $\log^{d}$ factors, which can be significant. Recent techniques for composing bounded error quantum algorithms without log-factor overhead [8, 7] could reduce this overhead to $c^{d}$ for some constant, but this could still be significant, if $c>1$ . Overcoming these limitation requires a fundamentally different approach.

To address this, we design a new quantum algorithm for $\textsc{Dist}_{L}$ that is based on a recursively constructed switching network. A switching network (Definition 3) is an undirected graph with terminals $u$ and $v$ , whose edges are labeled by Boolean variables $\{x_{1},\dots,x_{m}\}$ , that can switch the edges “on” or “off”, by their truth value. Such a network naturally defines a Boolean function $f:\{0,1\}^{m}\rightarrow\{0,1\}$ , with $f(x)=1$ (we then say the switching network accepts $x$ ) if and only if $u$ and $v$ are connected by a path consisting of edges whose labels are true under the assignment $x$ . An example is given in Figure 1.

Figure 1: (L) An example of a switching network. (R) The same switching network, with edges switched on (thick) or off (dashed) by the assignment

x=10101

. In this example,

u

and

v

are connected by a path of edges labelled by variables that are true under

x

, and so the switching network accepts

x

.

Switching networks are a natural and well-motivated model in classical computing, and have been used to study classical space-bounded complexity (see, e.g., [18]). They also give a simple way of designing quantum algorithms, as any switching network can be compiled into a quantum algorithm for the associated function, whose time and space complexity depend on certain properties of the switching network. Quantum algorithms for evaluating switching networks were developed in [13] using span program techniques inspired by [9], and a subsequent work [12] provided a tight analysis of these span program algorithms for arbitrary switching networks, in terms of query complexity. These quantum algorithms were only explicitly related to the classical model of switching networks in [14], where more detailed techniques were developed for efficiently implementing this type of quantum algorithm, and rigorously analyzing their time complexity.

Switching networks lend themselves well to quantum algorithms in part because they are a naturally reversible structure, being defined by undirected graphs. Moreover, they give a natural way of defining recursive quantum algorithms: by defining a switching network recursively, and turning the final product into a quantum algorithm, bounded error is introduced only once, when turning the switching network into a quantum algorithm, and there are no factors of $c^{d}$ or $\log^{d}$ on the complexity of the algorithm, even when the depth of recursion in the switching network is $d$ .

Because we keep the more space-intensive outer BFS algorithm classical, most of the space needed by the algorithm is classical. For any $S$ , we only need $O(\log^{2}(n))$ qubits of quantum space to implement our quantum subroutine for $\textsc{Dist}_{L}$ , the remainder of the $S$ space is classical.

Our algorithm for $\textsc{Dist}_{L}$ provides a compelling example of how switching networks can be used within quantum algorithms. It exploits the full power of the classical switching network model, while at the same time extending it into a setting where time-space tradeoffs become essential. It is the first time switching networks have been used to prove a quantum time-space tradeoff. Beyond its role in our algorithm for dstcon, our algorithm for $\textsc{Dist}_{L}$ may be of independent interest as a quantum primitive for other space-efficient graph algorithms.

Open Problems

Our speedup over the best known classical algorithm is quadratic when $S=\log^{2}(n)$ , and gets worse as $S$ increases towards $\sqrt{n}$ , at which point we no longer achieve any speedup. However, we do know there is a quadratic speedup at the other extreme, $S=n$ . It is thus very natural to hope that we might get a quadratic speedup over the algorithm of [6] for all $S$ . One difficulty in this is that our algorithm is not just a quantization of the algorithm of [6], but actually does something different.

As mentioned earlier, for the undirected variant (ustcon), quantum algorithms achieve optimal time and space simultaneously [9, 4]. This naturally raises the question of whether a similar result is possible in the directed case.

We have already mentioned the compelling open problem of showing a $O(\log(n))$ -space quantum algorithm for dstcon. This would necessarily be a polynomial-time algorithm, and so it would, in some rough sense, achieve the above goal of have optimal space and time simultaneously. It would also show that the quantum analogue of ${\sf L}$ (logspace) is contained in ${\sf NL}$ (nondeterministic logspace). Ref. [3] made some progress on this question by showing that a promise version of dstcon in which the input has few paths can be solved in $O(\log(n))$ quantum space. We remark that any $o(\log^{2}(n))$ upper bound on the quantum space complexity of dstcon would be interesting.

Organization

The remainder of this paper is organized as follows. In Section 2, we give the necessary preliminaries on graph theory, switching networks, and quantum algorithms. In Section 3, we present our main result, a quantum algorithm for dstcon with a parameter $L$ that can be used to tune the classical space complexity of the algorithm. The key technical building block of this algorithm is a quantum subroutine for the problem $\textsc{Dist}_{L}$ , which we describe in Section 4.

2 Preliminaries

Here we state preliminaries. In Section 2.1, we define both directed and undirected graphs, as well as the notation we will use to talk about them. In Section 2.2, we formally define switching networks, and state results about quantum algorithms for evaluating them.

First, we state a few simple conventions and notational definitions. Unless otherwise specified, logarithms are with respect to base 2. We let $\bar{0}$ denote the all-zeros string, which throughout this paper will always have length $\log n$ . We use ${\widetilde{O}}(f(n))$ to suppress poly $(\log n)$ factors, where $n$ is always the number of vertices in the input digraph. So, for example, ${\widetilde{O}}(1)$ is polylog $(n)$ .

2.1 Graphs

A directed graph $G=(V(G),E(G))$ , or digraph, consists of a vertex set $V(G)=\{v_{1},\dots,v_{n}\}$ and an edge set $E(G)\subseteq\{(u,v)\in V(G)^{2}:u\neq v\}$ . We say $v$ is reachable from $u$ in $G$ if there exists a path $u=u_{0},\dots,u_{\ell}=v$ such that for all $i\in[\ell]$ , $(u_{i-1},u_{i})\in E(G)$ . When $G$ is clear from context, we just write $V$ and $E$ .

We are interested in solving the $s t$ -connectivity – or reachability – problem on directed graphs, but we will also make use of undirected graphs, in the context of switching networks, described shortly.

An undirected graph ${\cal N}$ is just a directed graph, where we don’t care about the direction of the edge – and in fact, we will ultimately want to assign to each edge an arbitrary orientation, for convenience, so we could even take the same definition we used for directed graphs, and just change notions like reachability. However, for our purpose an undirected graph will ultimately define a quantum algorithm on a space spanned by the edges of ${\cal N}$ . We therefore take a somewhat edge-centric definition, which has the added bonus of accommodating multigraphs.

Definition 1.

An undirected graph ${\cal N}=(V({\cal N}),E({\cal N}))$ is specified by a pair of finite sets of vertex labels, $V$ and edge labels, $E$ ; as well as incidence sets $E_{\cal N}({\sf u})=E_{\cal N}^{\leftarrow}({\sf u})\sqcup E_{\cal N}^{% \rightarrow}({\sf u})$ for each ${\sf u}\in V$ , such that for all $e\in E$ , there are unique distinct vertices ${\sf u},{\sf v}\in V$ such that $e\in E^{\rightarrow}({\sf u})\cap E^{\leftarrow}({\sf v})$ . We think of $E^{\rightarrow}({\sf u})$ as the set of edges coming out of ${\sf u}$ , and $E^{\leftarrow}({\sf u})$ as the set of edges going into ${\sf u}$ . When ${\cal N}$ is clear from context, we omit it from the notation, as we have just demonstrated.

This definition gives us the freedom to specify $e\in E$ however we want to, not necessarily by its endpoints, as $e=({\sf u},{\sf v})$ . To recover this usual edge set, we can map $e$ to $({\sf u},{\sf v})$ such that $e\in E^{\rightarrow}({\sf u})\cap E^{\leftarrow}({\sf v})$ . When this holds for some edge, we will abuse notation by writing $({\sf u},{\sf v})\in E$ , to mean “there is an edge from ${\sf u}$ to ${\sf v}$ in ${\cal N}$ .” Note that while each edge does have an orientation, these are arbitrary and for convenience only. We say that ${\sf u}$ is connected to ${\sf v}$ in ${\cal N}$ (or reachable from ${\sf v}$ ) if there is a ${\sf u}{\sf v}$ -path ${\sf u}={\sf u}_{0},\dots,{\sf u}_{\ell}={\sf v}$ such that for all $i\in[\ell]$ , $({\sf u}_{i-1},{\sf u}_{i})\in E$ or $({\sf u}_{i},{\sf u}_{i-1})\in E$ .

Finally, we will often build a (undirected) graph ${\cal N}$ out of graphs ${\cal N}_{1}$ and ${\cal N}_{2}$ by “gluing” (identifying) some of the vertices in ${\cal N}_{1}$ with some vertices in ${\cal N}_{2}$ . The following definition makes precise what we mean by this.

Definition 2.

Let ${\cal N}_{1}$ and ${\cal N}_{2}$ be graphs, with ${\sf u}_{1,1},\dots,{\sf u}_{1,r}\in V({\cal N}_{1})$ and ${\sf u}_{2,1},\dots,{\sf u}_{2,r}\in V({\cal N}_{2})$ . The graph ${\cal N}$ obtained from these graphs by gluing vertex ${\sf u}_{1,i}$ with ${\sf u}_{2,i}$ for all $i\in[r]$ is defined by the following vertex and edge (label) sets:

	$\displaystyle V({\cal N})$	$\displaystyle=V({\cal N}_{1})\sqcup(V({\cal N}_{2})\setminus\{{\sf u}_{2,1},% \dots,{\sf u}_{2,r}\})$
	$\displaystyle\mbox{and }E({\cal N})$	$\displaystyle=E({\cal N}_{1})\sqcup E({\cal N}_{2})$

and incidence sets:

	$\displaystyle\forall{\sf u}\in V({\cal N}_{1})\setminus\{{\sf u}_{1,1},\dots,{% \sf u}_{1,r}\},\;E_{\cal N}^{\rightarrow}({\sf u})$	$\displaystyle=E_{{\cal N}_{1}}^{\rightarrow}({\sf u})\mbox{ and }E_{{\cal N}}^% {\leftarrow}({\sf u})=E_{{\cal N}_{1}}^{\leftarrow}({\sf u}),$
	$\displaystyle\forall{\sf u}\in V({\cal N}_{2})\setminus\{{\sf u}_{2,1},\dots,{% \sf u}_{2,r}\},\;E_{\cal N}^{\rightarrow}({\sf u})$	$\displaystyle=E_{{\cal N}_{2}}^{\rightarrow}({\sf u})\mbox{ and }E_{{\cal N}}^% {\leftarrow}({\sf u})=E_{{\cal N}_{2}}^{\leftarrow}({\sf u}),$
	$\displaystyle\mbox{and }\forall i\in[r],\;E^{\rightarrow}_{\cal N}({\sf u}_{1,% i})$	$\displaystyle=E_{{\cal N}_{1}}^{\rightarrow}({\sf u}_{1,i})\sqcup E_{{\cal N}_% {2}}^{\rightarrow}({\sf u}_{2,i})$
	$\displaystyle\mbox{ and }E^{\leftarrow}_{\cal N}({\sf u}_{1,i})$	$\displaystyle=E_{{\cal N}_{1}}^{\leftarrow}({\sf u}_{1,i})\sqcup E_{{\cal N}_{% 2}}^{\leftarrow}({\sf u}_{2,i}).$

We made the arbitrary choice to let the glued vertices inherit their names from ${\cal N}_{1}$ rather than ${\cal N}_{2}$ , but since in practice, we will mainly work on the edges of the graph, this detail doesn’t matter so much. What is more important is that the edge set is simply a disjoint union of the edges sets of ${\cal N}_{1}$ and ${\cal N}_{2}$ .

2.2 Switching Networks

A switching network on $\{0,1\}^{m}$ (see e.g. [18]) is an undirected graph $\cal N$ with two distinct boundary vertices ${\sf s}$ and ${\sf t}$ , in which each edge is labeled by a literal from $\{x_{1},\dots,x_{m},\allowbreak\neg x_{1},\dots,\neg x_{m},1\}$ . To simplify things slightly, in our case, we only have edges labeled with positive literals, $\{x_{1},\dots,x_{m}\}$ , so we can just use the label set $[m]$ (or more specifically, in our case, the labels will be pairs $i,j\in[n]$ , with $x_{i,j}=1$ if and only if $(v_{i},v_{j})\in E(G)$ for $G$ the input digraph). For $x\in\{0,1\}^{m}$ , letting ${\cal N}(x)$ denote the subgraph of ${\cal N}$ that includes only those edges whose labels are true under the string $x$ , we say that ${\cal N}$ accepts $x$ if and only if ${\sf s}$ is connected to ${\sf t}$ in ${\cal N}(x)$ . In [14], formalizing [13], switching networks were additionally equipped with some associated subspaces, as we describe in the following definition.

Definition 3.

A switching network ${\cal N}$ on $\{0,1\}^{m}$ consists of:

1.

an undirected multigraph ${\cal N}=(V,E)$ with a source ${\sf s}\in V$ and sink ${\sf t}\in V\setminus\{{\sf s}\}$ ;
2.

for each edge $e\in E$ , a query label $\varphi_{e}\in[m]$ .

For $x\in\{0,1\}^{m}$ , we define ${\cal N}(x)$ by restricting ${\cal N}$ to those edges $e\in E$ such that $x_{\varphi_{e}}=1$ . We associate the following spaces with ${\cal N}$ , and an input $x$ :

1.

$\Xi_{{\sf s}}^{\cal A}=\mathrm{span}\{{\lvert}{\sf s}\rangle+{\lvert}% \leftarrow,{\sf s}\rangle\}$ and $\Xi_{{\sf t}}^{\cal A}=\mathrm{span}\{{\lvert}\rightarrow,{\sf t}\rangle+{% \lvert}{\sf t}\rangle\}$
2.

for all ${\sf v}\in V\setminus\{{\sf s},{\sf t}\}$ , ${\cal V}_{{\sf v}}=\mathrm{span}\{{\lvert}\psi_{\star}({\sf v})\rangle\mathrel% {\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{% \vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\sum_{e% \in E^{\rightarrow}({\sf v})}{\lvert}\rightarrow,e\rangle+\sum_{e\in E^{% \leftarrow}({\sf v})}{\lvert}\leftarrow,e\rangle\}$
3.

${\cal V}_{{\sf s}}=\mathrm{span}\{{\lvert}\psi_{\star}({\sf s})\rangle\mathrel% {\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{% \vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\sum_{e% \in E^{\rightarrow}({\sf s})}{\lvert}\rightarrow,e\rangle+\sum_{e\in E^{% \leftarrow}({\sf s})}{\lvert}\leftarrow,e\rangle+{\lvert}\leftarrow,{\sf s}\rangle\}$
4.

${\cal V}_{{\sf t}}=\mathrm{span}\{{\lvert}\psi_{\star}({\sf t})\rangle\mathrel% {\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{% \vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\sum_{e% \in E^{\rightarrow}({\sf t})}{\lvert}\rightarrow,e\rangle+\sum_{e\in E^{% \leftarrow}({\sf t})}{\lvert}\leftarrow,e\rangle+{\lvert}\rightarrow,{\sf t}\rangle\}$
5.

for all $e\in E$ , $\Xi_{e}=\mathrm{span}\{{\lvert}\rightarrow,e\rangle,{\lvert}\leftarrow,e\rangle\}$ , $\Xi_{e}^{\cal A}(x)=\mathrm{span}\{{\lvert}\rightarrow,e\rangle+(-1)^{x_{% \varphi_{e}}}{\lvert}\leftarrow,e\rangle\}$ , $\Xi_{e}^{\cal B}=\mathrm{span}\{{\lvert}\rightarrow,e\rangle+{\lvert}% \leftarrow,e\rangle\}$ .

Then we let $H_{\cal N}=\bigoplus_{e\in E}\Xi_{e}\oplus\mathrm{span}\{{\lvert}{\sf s}% \rangle,{\lvert}{\sf t}\rangle,{\lvert}\leftarrow,{\sf s}\rangle,{\lvert}% \rightarrow,{\sf t}\rangle\}$ and define the following two important subspaces of $H_{\cal N}$ :

{\cal A}(x)=\Xi_{{\sf s}}^{\cal A}\oplus\Xi_{{\sf t}}^{\cal A}\oplus\bigoplus_% {e\in E}\Xi_{e}^{\cal A}(x)\quad\mbox{and}\quad{\cal B}=\bigoplus_{{\sf u}\in V% (G)}{\cal V}_{{\sf u}}+\bigoplus_{e\in E}\Xi_{e}^{\cal B}\oplus\mathrm{span}\{% {\lvert}\leftarrow,{\sf s}\rangle+{\lvert}\rightarrow,{\sf t}\rangle\}.

(2)

A single switching network can potentially compute different functions for different possible values of ${\sf s}$ or ${\sf t}$ . Thus, we will later find it convenient to equip a set of sinks²²2We could also allow multiple sources instead of just a single ${\sf s}$ , but we don’t need that for our constructions., which, together with the single source ${\sf s}$ , will form a boundary for ${\cal N}$ .

$\blacktriangleright$ Remark 4.

It is also possible to assign weights to the edges of ${\cal N}$ in the definition of a switching network, which impacts the complexity of the quantum algorithm for evaluating it, but in this work we will assume all edges have weight 1.

A switching network, along with the spaces defined in Definition 3, is a special case of a subspace graph, defined in [14]. As there, we can define working bases for a switching network as a pair of bases $\Psi^{\cal A}$ and $\Psi^{\cal B}$ for ${\cal A}$ and ${\cal B}$ respectively. For switching networks, the natural working basis for ${\cal A}$ is simply

\Psi_{\cal A}(x)=\left\{{\lvert}\rightarrow,e\rangle+(-1)^{x_{\varphi_{e}}}{% \lvert}\leftarrow,e\rangle:e\in E(\cal N)\right\}\cup\{{\lvert}{\sf s}\rangle+% {\lvert}\leftarrow,{\sf s}\rangle,{\lvert}\rightarrow,{\sf t}\rangle+{\lvert}{% \sf t}\rangle\}.

It’s not difficult to see that this basis can be generated using a query to $x$ , and $O(1)$ basic operations, by which we mean the following.

Definition 5 (Basis Generation).

We say an orthonormal basis $\Psi=\{{\lvert}b_{\ell}\rangle\}_{\ell\in L}\subset H_{\cal N}$ can be generated in time $T$ if:

1.

The reflection around the subspace span $\{{\lvert}\ell\rangle:\ell\in L\}$ of $H_{\cal N}$ can be implemented in time $T$ .
2.

There is a map that acts as ${\lvert}\ell\rangle\mapsto{\lvert}b_{\ell}\rangle$ for all $\ell\in L$ that can be implemented in time $T$ .

For the space ${\cal B}$ , we construct a basis for the orthogonal complement and invoke the following lemma from [14, Corollary 2.11], which guarantees that this suffices.

Lemma 6.

If $\Psi$ is a basis that can be generated in time $T$ , then there is a basis $\Psi^{\prime}$ for $\mathrm{span}\{\Psi\}^{\bot}$ that can be generated in time $T$ .

The following is a special case of [14, Theorem 3.13], which is proven by analyzing a phase estimation algorithm on the product of reflections around ${\cal A}$ , and ${\cal B}$ . It is also similar to [13, Theorem 13], but with a different implementation of reflection around ${\cal B}$ by generating a basis directly, rather than via a quantum walk, which is potentially more expensive.

Theorem 7.

For $f:\{0,1\}^{m}\rightarrow\{0,1\}$ , let ${\cal N}$ be a switching network that accepts $x\in\{0,1\}^{m}$ if and only if $f(x)=1$ . Suppose that for all $x$ accepted by ${\cal N}$ , there is an ${\sf s}{\sf t}$ -path in ${\cal N}(x)$ of length at most $W_{+}$ . Suppose the space ${\cal B}^{\perp}$ of $\cal N$ has a basis $\Psi_{\cal B}^{\perp}$ that can be generated in time $T_{B}$ . Then there is a quantum algorithm that decides $f$ with bounded error in time $O(T_{B}\sqrt{W_{+}|E({\cal N})|})$ and space $O(\log|E({\cal N})|).$

We can get a stronger version of this theorem by replacing path length with effective resistance, and cut size with capacitance (see [12]), but the theorem as stated suffices for our purposes.

3 Quantum Algorithm for DSTCON

In this section, we prove our main result, by describing a quantum algorithm for dstcon that works for any space bound $S\geq\log^{2}(n)$ . We begin by stating the main technical result of this paper, which we prove in Section 4. Specifically, we present a quantum algorithm for deciding directed $s t$ -connectivity under an additional constraint on the path length (i.e. solving ${\tt Dist}_{L}$ ). While this subroutine is quantum, the algorithm we decide in the remainder of this section is otherwise classical.

Theorem 8.

Let $G=(V,E)$ be a directed graph such that $V=\{v_{1},\dots,v_{n}\}$ . Assume that $G$ can be accessed via a quantum oracle $\mathcal{O}_{G}$ that can be implemented in time $O(1)$ , where for any $i,j\in[n]$ , $b\in\{0,1\}$

\mathcal{O}_{G}:{\lvert}i\rangle{\lvert}j\rangle{\lvert}b\rangle\mapsto\begin{% cases}{\lvert}i\rangle{\lvert}j\rangle{\lvert}b\oplus 1\rangle&\mbox{if }(v_{i% },v_{j})\in E\\ {\lvert}i\rangle{\lvert}j\rangle{\lvert}b\rangle&\mbox{otherwise.}\end{cases}

Let $L\leq n$ be a power of 2. Then there is a bounded-error quantum algorithm, ${\tt D}_{L}(G,u,v)$ , that decides for any $u,v\in V$ whether there is a directed path from $u$ to $v$ in $G$ of length at most $L$ , in time

{\widetilde{O}}\left(\left(L^{\log 3}(2n+1)^{\log L}n\right)^{1/2}\right)

and space $O\left(\log(L)\log(n)\right).$

In Section 4, we prove the statement for $L$ a power of 2, using a recursive structure, but a simple corollary extends this result to any $L$ .

Corollary 9.

Let $G$ be as in Theorem 8, and let $L$ be any positive integer. Then there is a bounded-error quantum algorithm, ${\tt Dist}_{L}(G,u,v)$ , that decides for any $u,v\in V$ whether there is a directed path from $u$ to $v$ in $G$ of length at most $L$ , in time

{\widetilde{O}}\left(\left(L^{\log 3}(2n+1)^{\log L}n\right)^{1/2}\right)

and space $O\left(\log(L)\log(n)\right).$

Proof.

To prove the statement, we exhibit a quantum algorithm, Algorithm 1 that uses one call to the subroutine ${\tt D}$ from Theorem 8, on a graph $G^{\prime}$ that is constructed from $G$ by adding a directed path from some new vertex $s_{1}$ into $u$ of length such that any $u v$ -path of length at most $L$ corresponds to a $s_{1}v$ -path of length at most $2^{\lceil\log L\rceil}$ (see Figure 2). Since $G^{\prime}$ can be queried using at most one query to $G$ , the result follows. $\hfill\blacktriangleleft$

Algorithm 1 Dist

{}_{L}(G,u,v)

.

Parameter: a positive integer $L\leq n$
Input: a directed graph $G=(V,E)$ and a pair of vertices $u,v\in V$
Output: 0 or 1 indicating there is a path of length at most $L$ between $u$ and $v$ in $G$

1.

Let $\ell=\lceil\log L\rceil$ and $a=2^{\ell}-L$
2.

Let $G^{\prime}$ be the graph $G$ with $a$ new vertices $s_{1},\dots,s_{a}$ and $a$ new edges $(s_{1},s_{2}),\dots,(s_{a-1},s_{a}),(s_{a},u)$ . Then $G^{\prime}$ is just $G$ with a directed path of length $a$ coming into $u$ , and can easily be queried using queries to $G$ .
3.

Return ${\tt D}_{2^{\ell}}(G^{\prime},s_{1},v)$ .

Figure 2: The graph

G^{\prime}

constructed from

G

. It is clear that there is a

u v

-path of length at most

L

in

G

if and only if there is a

s_{1}v

-path of length at most

L+a

in

G^{\prime}

.

3.1 BFS algorithm that calls the quantum short path subroutine

To get a time-space tradeoff for dstcon, and prove our main result, we describe a classical BFS-based algorithm, Algorithm 2, from [6], that makes calls to a subroutine for the problem Dist ${}_{L}(G,u,v)$ , of deciding whether there is a path of length at most $L$ from $u$ to $v$ in a directed graph $G$ . Our algorithm for dstcon is obtained by instantiating that subroutine with the quantum algorithm ${\tt Dist}_{L}$ from Corollary 9.

Algorithm 2 DSTCON

{}_{L}(G,s,t)

[6].

Parameter: a positive integer $L\leq n$
Input: a directed graph $G=(V,E)$ and a pair of vertices $s,t\in V$
Output: Connected if there is a directed path from $s$ to $t$ in $G$ , Not Connected otherwise

Ref. [6] show that this algorithm correctly decides dstcon whenever ${\tt Dist}_{L}$ decides whether there is a path of length at most $L$ . From [6], or by inspecting Algorithm 2, we get the following.

Lemma 10.

Let ${\tt Dist}_{L}(G,u,v)$ be a bounded-error algorithm for $\textsc{Dist}_{L}$ , with time complexity $D_{T}(n,L)$ , and the space complexity is $D_{S}(n,L)$ . Then the time complexity of Algorithm 2 is

{\widetilde{O}}\left(\frac{n^{3}}{L}D_{T}(n,L)\right)

and its space complexity is

O\left(\frac{n\log n}{L}+D_{S}(n,L)\right).

If ${\tt Dist}_{L}$ is implemented by a quantum algorithm, then the quantum space complexity is at most $O(D_{S}(n,L))$ , and any remaining space is classical.

Substituting the result of Corollary 9 yields the following theorem, which combines our quantum subroutine with the classical BFS algorithm. Although the algorithm in Corollary 9 has bounded error, its success probability can be boosted high enough that the outer algorithm will not notice, using majority voting, at the cost of an overhead of $\log{\widetilde{O}}(n^{3}/L)$ , which is hidden in the ${\widetilde{O}}$ of the final complexity.

Theorem 11.

Let $G=(V,E)$ be a directed graph such that $V=\{v_{1},\dots,v_{n}\}$ , and $s,t\in V$ . Assume that $G$ can be accessed via a quantum oracle $\mathcal{O}_{G}$ that can be implemented in time $O(1)$ , where for any $i,j\in[n]$ , $b\in\{0,1\}$ ,

\mathcal{O}_{G}:{\lvert}i\rangle{\lvert}j\rangle{\lvert}b\rangle\mapsto\begin{% cases}{\lvert}i\rangle{\lvert}j\rangle{\lvert}b\oplus 1\rangle&\mbox{if }(v_{i% },v_{j})\in E\\ {\lvert}i\rangle{\lvert}j\rangle{\lvert}b\rangle&\mbox{otherwise.}\end{cases}

Then there is a quantum algorithm that decides whether there is a directed path from $s$ to $t$ in $G$ with bounded error in time

{\widetilde{O}}\left(n^{3.5}L^{.5\log(3)-1}(2n+1)^{0.5\log L}\right)

and total space

{\widetilde{O}}\left(\left(\frac{n}{L}+\log L\right)\log n\right)

of which $O(\log(L)\log(n))$ is quantum space.

3.2 Complexity comparison: classical vs. quantum

Theorem 12 ([6]).

Let $G=(V,E)$ be a directed graph such that ${V}=\{v_{1},\dots,v_{n}\}$ , and $s,t\in V$ . Assume that $G$ can be accessed via a classical oracle ${\cal O}_{G}$ that can be implemented in time $O(1)$ , where for any $i,j\in[n]$ ,

{\cal O}_{G}(i,j)=\begin{cases}1&\mbox{if }(v_{i},v_{j})\in E\\ 0&\mbox{otherwise.}\end{cases}

Then for any $S\geq\log^{2}(n)$ , there is a classical algorithm that decides whether there is a directed path from $s$ to $t$ in $G$ using space $O(S)$ and time

T\leq 2^{\log^{2}\frac{n}{S}+O(\log n\log\log n)}.

In [6], they state a bound of $T\leq 2^{O(\log^{2}(n/S))}$ , but using their choice of parameters, and a slightly more precise analysis of their algorithm, we can compute the more fine-grained upper bound we have stated above. We improve on their result in our main theorem, which is the following.

Theorem 13.

Let $G=(V,E)$ be a directed graph such that $V=\{v_{1},\dots,v_{n}\}$ , and $s,t\in V$ . Assume that $G$ can be accessed via a quantum oracle $\mathcal{O}_{G}$ that can be implemented in time $O(1)$ , where for any $i,j\in[n]$ , $b\in\{0,1\}$ ,

\mathcal{O}_{G}:{\lvert}i\rangle{\lvert}j\rangle{\lvert}b\rangle\mapsto\begin{% cases}{\lvert}i\rangle{\lvert}j\rangle{\lvert}b\oplus 1\rangle&\mbox{if }(v_{i% },v_{j})\in E\\ {\lvert}i\rangle{\lvert}j\rangle{\lvert}b\rangle&\mbox{otherwise.}\end{cases}

Then for any $S\geq\log^{2}(n)$ , there is a quantum algorithm that decides for any $s,t\in V$ whether there is a directed path from $s$ to $t$ in $G$ with bounded error using space $O(S)$ and time

T\leq 2^{\frac{1}{2}\log n\log\frac{n}{S}+O(\log n\log\log n)}.

This algorithm uses $O(\log^{2}(n))$ quantum space.

Proof.

We analyze the time-space tradeoff of the quantum algorithm of Theorem 11. Assuming $L\log L=O(n)$ , its space complexity becomes $S=O\left(\frac{n}{L}\log n\right)$ , with only $O(\log(L)\log(n))=O(\log^{2}(n))$ quantum space. That is, we can express $L=\Theta\left(\frac{n}{S}\log n\right)$ . Substituting this into the time complexity $T={\widetilde{O}}\left(n^{3.5}L^{.5\log(3)-1}(2n+1)^{0.5\log L}\right)$ and taking logarithms, we obtain

	$\displaystyle\log T$	$\displaystyle=3.5\log n+\log L\left(\frac{\log(2n+1)}{2}+.5\log(3)-1\right)+O(% \log\log n)$
		$\displaystyle=\left(\log\frac{n}{S}+\log\log n+O(1)\right)\left(\frac{\log n}{% 2}+O(1)\right)+O(\log n)$
		$\displaystyle=\frac{1}{2}\log(\frac{n}{S})\log(n)+O\left(\log(n)\log\log(n)% \right).$

$\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 14.

For $S=o(n^{1/2})$ , the quantum algorithm of Theorem 13 achieves a better time-space tradeoff than the classical time-space tradeoff stated in Theorem 12.

4 Quantum short path subroutine

In this section, we prove Theorem 8 by describing and analyzing a quantum algorithm for $\textsc{Dist}_{L}(G,s,t)$ , for $G=(V,E)$ a directed graph with $V=\{v_{1},\dots,v_{n}\}$ , $s,t\in V$ any pair of vertices, and $L\in\mathbb{N}$ a power of 2. The algorithm is designed by exhibiting a switching network (Definition 3), and then applying Theorem 7.

In Section 4.1, we describe the switching network, through a recursive construction. In order to apply Theorem 7, we need to analyze the number of edges in the switching network, and upper bound the distance between its source ${\sf s}$ and sink ${\sf t}$ , which we do in Section 4.2. Finally, in Section 4.3, we put it all together to prove Theorem 8.

4.1 Switching network

The switching networks we will work with will have vertices represented by a tuple $[u_{1},\dots,u_{k}]\allowbreak\in V^{k}$ , of some number $k$ of vertices of $G$ , as well as possibly some additional information. We will not actually care so much about naming conventions for the vertices, but the important detail is that each vertex of a switching network has an associated subset $\{u_{1},\dots,u_{k}\}\subseteq V$ (so the order of the tuple actually doesn’t matter). In particular, we will construct switching networks by gluing together switching networks of this form (see Definition 2), and it will be important that any pair of vertices we glue together have the same associated set, so there is no ambiguity.

The way we construct our switching networks, we will only have an edge between a pair of vertices where the associated sets are of the form $\{u_{1},\dots,u_{k}\}$ and $\{u_{1},\dots,u_{k},u_{k+1}\}$ , and the query label for that edge (see Definition 3) is $(u_{i},u_{k+1})$ for some $i\in[k]$ . Such switching networks were first studied in [17]. This structure ensures that a vertex $[u]$ can only be connected to a vertex $[u_{1},\dots,u_{k}]$ by a path of “on” edges if each $u_{i}$ is reachable from $u$ in $G$ – a property that will be crucial for our analysis in Section 4.1.2.

In this section, we will describe and analyze a switching network ${\cal N}_{L}(s)$ of the above described form. This will be built inductively from switching networks ${\cal N}_{2^{\ell}}(u)$ for $\ell\in\{0,\dots,\log L\}$ , and $u\in V$ , called the root. ${\cal N}_{2^{\ell}}(u)$ has a single source $[u]$ and $n$ sinks $\{[u,v_{i}]:v_{i}\in V\}$ . With respect to the $i$ -th sink $[u,v_{i}]$ , the switching network computes whether $v_{i}$ is reachable from $u$ by a path of length at most $2^{\ell}$ , for every $v_{i}\in V$ simultaneously (i.e. $v_{i}$ is reachable from $u$ by a path of length at most $2^{\ell}$ in $G$ if and only if $[u]$ and $[u,v_{i}]$ are connected in ${\cal N}_{2^{\ell}}(u)(G)$ ). This “extended boundary” is used solely for the recursive construction in Section 4.1.1. The final construction ${\cal N}_{L}(s)$ has source ${\sf s}=[s]$ and a single sink ${\sf t}=[s,t]$ . We write ${\cal N}_{L}(s,t)$ when we want to emphasize this.

4.1.1 Graph construction

Define $\Sigma=\{(0,\bar{0})\}\cup\{(1,i):i\in\{0,1\}^{\log n}\}\cup\{(2,j):j\in\{0,1% \}^{\log n}\}$ , an alphabet of size $2n+1$ . We have ensured that all symbols in this alphabet have an obvious representation as a string in $\{0,1,2\}\times\{0,1\}^{\log n}$ , but for convenience we will sometimes use $0$ to denote $(0,\bar{0})$ , and $1i$ or $2j$ to denote $(1,i)$ or $(2,j)$ . For any $\sigma\in\Sigma^{*}$ , let $|\sigma|$ denote its length, and define:

f_{1}(\sigma):=\left\{\begin{array}[]{ll}\max\{i\in\{1,\dots,|\sigma|\}:\sigma% _{i}\in\{1\}\times\{0,1\}^{\log n}\}&\mbox{if }\exists i:\sigma_{i}\in\{1\}% \times\{0,1\}^{\log n}\\ 0&\mbox{else.}\end{array}\right.

We now define ${\cal N}_{2^{\ell}}(u)$ for $\ell\in[\log L]$ , by a recursive construction.

Base construction

For the base case, $\ell=0$ , the switching network ${\cal N}_{1}(u)$ consists of a source vertex $[u]$ connected to $n$ sinks $[u,v_{i}],v_{i}\in V$ . The edges have query labels $(u,v_{i})$ , each “checking” whether there is an edge $(u,v_{i})$ in $G$ (see Figure 3). More precisely, we formally define the sets of vertices and edges as follows.

V_{1}=\{[u]\}\cup\{[u,v_{i}]:v_{i}\in V\},\quad\mbox{and}\quad E_{1}=\{{\lvert% }e_{i}\rangle={\lvert}i\rangle:i\in[n]\}.

Above, we put edge labels in a ket, to emphasize that they form an orthonormal basis of some inner product space. The incidence of edges and vertices is defined (see Definition 1 for a reminder of how undirected graphs are specified):

E_{1}^{\rightarrow}([u])=E_{1}\quad\mbox{and}\quad E_{1}^{\leftarrow}([u])=\emptyset

\forall i\in[n],\;E_{1}^{\rightarrow}([u,v_{i}])=\emptyset\quad\mbox{and}\quad E% _{1}^{\leftarrow}([u,v_{i}])=\{{\lvert}e_{i}\rangle\}.

The query label of the edge $e_{i}$ is $(u,v_{i})$ .

Figure 3: Graph construction for the switching network

{\cal N}_{1}(u)

that decides whether each vertex of a graph

G=(V,E)

is reachable from a vertex

u\in V

by a path of length

1

. Each edge

([u],[u,v_{i}])

of

{\cal N}_{1}(u)

has query label

(u,v_{i})

and is “on” in

{\cal N}_{1}(u)(G)

if and only if

(u,v_{i})\in E

. Therefore, it holds that

v_{i}

is reachable from

u

by a path of length at most

1

in

G

if and only if

[u]

and

[u,v_{i}]

are connected in

{\cal N}_{1}(u)(G)

.

Recursive construction

Next, we describe the construction of ${\cal N}_{2^{\ell}}(u)$ , assuming that a construction of ${\cal N}_{2^{\ell-1}}(u)$ is given. Let ${\cal N}_{2^{\ell-1}}^{v}(u)$ denote a copy of ${\cal N}_{2^{\ell-1}}(u)$ in which each vertex-tuple of the switching network is augmented with an additional vertex $v\in V$ (although the order in the tuple doesn’t matter, for clarity, assume we append $v$ to the front of each tuple).

The construction of ${\cal N}_{2^{\ell}}(u)$ uses $2n+1$ copies ${\cal N}_{2^{\ell-1}}(u^{\prime})$ for some $u^{\prime}$ , some of them augmented by additional vertices. Specifically, define:

	$\displaystyle{\cal N}_{2^{\ell-1}}^{0}$	$\displaystyle={\cal N}_{2^{\ell-1}}(u)$
	$\displaystyle\forall i\in[n],\;{\cal N}_{2^{\ell-1}}^{(1,i)}$	$\displaystyle={\cal N}_{2^{\ell-1}}^{u}(v_{i})$
	$\displaystyle\forall j\in[n],\;{\cal N}_{2^{\ell-1}}^{(2,j)}$	$\displaystyle={\sf Rev}({\cal N}_{2^{\ell-1}}^{v_{j}}(u)).$

Above, we used the notation ${\sf Rev}({\cal N})$ to be the switching network ${\cal N}$ except with the orientation of every edge reversed. As we will see shortly, this ensures that all edges of ${\cal N}_{2^{\ell}}(u)$ have a logical left-to-right orientation. Define ${\cal N}_{2^{\ell}}(u)$ from these $2n+1$ copies of ${\cal N}_{2^{\ell-1}}$ by gluing (as made precise in Definition 2) the $i$ -th sink of ${\cal N}_{2^{\ell}}^{0}$ – which encodes $[u,v_{i}]$ – to the source of ${\cal N}_{2^{\ell}}^{(1,i)}$ – which also encodes $[u,v_{i}]$ – (for all $i\in[n])$ ; and gluing the $j$ -th sink of ${\cal N}_{2^{\ell}}^{(1,i)}$ – which encodes $[u,v_{i},v_{j}]$ – to the $i$ -th sink of ${\cal N}_{2^{\ell}}^{(2,j)}$ – which also encodes $[v_{j},u,v_{i}]\equiv[u,v_{i},v_{j}]$ – (for all $i,j\in[n]$ ), as in Figure 4. Note that the source of ${\cal N}_{2^{\ell}}^{(2,j)}$ , which encodes $[v_{j},u]\equiv[u,v_{j}]$ , is the $j$ -th sink of ${\cal N}_{2^{\ell}}(u)$ . The source $[u]$ of ${\cal N}_{2^{\ell-1}}^{0}$ is the source of ${\cal N}_{2^{\ell}}(u)$ .

Figure 4: Graph construction for the switching network

{\cal N}_{2^{\ell}}(u)

that decides whether each vertex of a graph

G=(V,E)

is reachable from a vertex

u\in V

by a path of length

2^{\ell}

.

The edges $E_{2^{\ell}}$ of ${\cal N}_{2^{\ell}}$ should be the disjoint union of the edge sets of the $2n+1$ copies of ${\cal N}_{2^{\ell-1}}$ . We use the elements of $\Sigma$ labeling each copy to make this union disjoint:

E_{2^{\ell}}=\bigsqcup_{\sigma\in\Sigma}E({\cal N}_{2^{\ell-1}}^{\sigma})=% \Sigma\times E_{2^{\ell-1}}=\Sigma^{\ell}\times E_{1}.

(3)

For $\sigma\in\Sigma^{\ell}$ and $i\in\{0,1\}^{\log n}$ , we will sometimes denote the edge ${\lvert}\sigma,e_{i}\rangle={\lvert}\sigma,i\rangle$ using

(-1)^{|\sigma|_{2}}{\lvert}e_{i}^{\sigma}\rangle:={\lvert}\sigma,e_{i}\rangle,

(4)

where $|\sigma|_{2}$ denotes the number of occurrences of $(2,j)$ for some $j$ in $\sigma$ . The reason for the sign is that we always want ${\lvert}\sigma,e_{i}\rangle$ to represent the $i$ -th edge in the $\sigma$ -labeled copy of ${\cal N}_{1}$ oriented from left-to-right³³3Such an orientation is not strictly necessary, but is more intuitive. (i.e. from source towards sinks), and we therefore need to reverse the edge orientations every time we use a copy of ${\cal N}_{2^{\ell}}$ in the $(2,j)$ -th position for some $j$ . Generally, if ${\lvert}\psi\rangle\in\mathrm{span}\{{\lvert}e\rangle:e\in E_{2^{\ell}}\}$ – equivalently, $\psi$ is a function on $E_{2^{\ell}}$ – and $\sigma\in\Sigma^{\ell^{\prime}}$ , we will let

{\lvert}\psi^{\sigma}\rangle=(-1)^{|\sigma|_{2}}{\lvert}\sigma\rangle{\lvert}% \psi\rangle,

(5)

which is a state in $\mathrm{span}\{{\lvert}e\rangle:e\in E_{2^{\ell+\ell^{\prime}}}\}$ that is only supported on the $\sigma$ -labeled copy of ${\cal N}_{2^{\ell}}$ (which we may denote ${\cal N}_{2^{\ell}}^{\sigma}$ ) in ${\cal N}_{2^{\ell+\ell^{\prime}}}$ .

Each of the $2n+1$ copies of ${\cal N}_{2^{\ell-1}}$ in ${\cal N}_{2^{\ell}}$ has a unique label $\sigma\in\Sigma$ . From this label, and the (global) root $u$ of ${\cal N}_{2^{\ell}}(u)$ , we can extract the root of the specific copy ${\cal N}_{2^{\ell-1}}^{\sigma}$ , and the vertex that is additionally stored in all of its vertices.

Inductively, we assign to each copy of ${\cal N}_{2^{\ell-k}},k\in[\ell]$ a label $\sigma\in\Sigma^{k}$ , from which we can extract the root of the specific copy ${\cal N}_{2^{\ell-k}}^{\sigma}$ and the set that is additionally stored in its vertices, knowing the global root $u\in V$ . In particular, each copy of ${\cal N}_{1}$ has a label $\sigma\in\Sigma^{\ell}$ and consists of $n$ edges. We can extract the root of each copy of ${\cal N}_{1}$ from its label $\sigma$ and the global root $u\in V$ and, hence, recover the edge query labels as well. In the following lemma, we show how exactly the query label can be extracted from the label of an edge.

Lemma 15.

Let $\sigma\in\Sigma^{\ell}$ and $i\in[n]$ encode an edge in ${\cal N}_{2^{\ell}}(u)$ . Then its edge is labeled by the query $((v_{\sigma_{\left(f_{1}(\sigma)\right)_{2}})},v_{i})$ , if $f_{1}(\sigma)\neq 0$ , and $(u,v_{i})$ otherwise.

Proof.

We prove the statement by induction. In the base case of ${\cal N}_{1}(u)$ , the claim is trivial. Since $\sigma\in\Sigma^{0}$ is an empty string, we have $f_{1}(\sigma)=0$ . The edges are encoded as ${\lvert}e_{i}\rangle={\lvert}i\rangle$ , and the corresponding query labels are $(u,v_{i})$ .

For the induction step, assume that the claim holds for ${\cal N}_{2^{\ell-1}}$ . The switching network ${\cal N}_{2^{\ell}}(u)$ consists of $2n+1$ copies of ${\cal N}_{2^{\ell-1}}$ labeled by $0,(1,i),(2,j)$ , where $i,j\in[n]$ . The edges in each of these switching networks are encoded by ${\lvert}\tilde{\sigma},k\rangle$ , where $\tilde{\sigma}\in\Sigma^{\ell-1}$ and $k\in[n]$ . First, consider the copies of ${\cal N}_{2^{\ell-1}}$ labeled by $0$ and $(2,j)$ for $j\in[n]$ . These are the switching networks ${\cal N}_{2^{\ell-1}}(u)$ and ${\cal N}_{2^{\ell-1}}^{v_{j}}(u)$ for $j\in[n]$ , all of which have $u$ as root, which is the same as the global root of ${\cal N}_{2^{\ell}}(u)$ . By the induction hypothesis, the query label of an edge ${\lvert}\tilde{\sigma},k\rangle$ in one of these switching networks is $((v_{\tilde{\sigma}_{\left(f_{1}(\tilde{\sigma})\right)_{2}})},v_{k})$ , if $f_{1}(\tilde{\sigma})\neq 0$ , and $(u,v_{k})$ otherwise. In the global switching network ${\cal N}_{2^{\ell}}(u)$ , the same edge is encoded by ${\lvert}\sigma,k\rangle$ , where $\sigma=0\tilde{\sigma}$ or $\sigma=(2,j)\tilde{\sigma}$ , depending on the copy of ${\cal N}_{2^{\ell-1}}(u)$ . Note that, in both cases, $f_{1}(\sigma)=f_{1}(\tilde{\sigma})$ , which proves the statement for the copies of ${\cal N}_{2^{\ell-1}}$ labeled by $0$ and $(2,j)$ for $j\in[n]$ .

Next, consider the copies of ${\cal N}_{2^{\ell-1}}^{(1,i)}$ for $i\in[n]$ . These are the switching networks ${\cal N}_{2^{\ell-1}}^{u}(v_{i})$ for $i\in[n]$ that have $v_{i}$ as their roots. By the induction hypothesis, the query label of an edge $(\tilde{\sigma},k)$ in one of these switching networks is $((v_{\tilde{\sigma}_{\left(f_{1}(\tilde{\sigma})\right)_{2}})},v_{k})$ , if $f_{1}(\tilde{\sigma})\neq 0$ , and $(v_{i},v_{k})$ otherwise. In the global switching network ${\cal N}_{2^{\ell}}(u)$ , the same edge is encoded by ${\lvert}\sigma,k\rangle$ , where $\sigma=(1,i)\tilde{\sigma}$ . Note that $f_{1}(\sigma)=f_{1}(\tilde{\sigma})$ if $f_{1}(\tilde{\sigma})\neq 0$ and $f_{1}(\sigma)=1$ otherwise. This proves the statement for the copies of ${\cal N}_{2^{\ell-1}}$ labeled by $(1,i)$ with $i\in[n]$ , and thus concludes the proof. $\hfill\blacktriangleleft$ Finally, we describe a top-down approach to building up ${\cal N}_{2^{\ell+1}}$ .

Lemma 16.

Let ${\cal N}^{\prime}$ be a switching network obtained from ${\cal N}_{2^{\ell}}$ by replacing each ${\cal N}_{1}$ block with an ${\cal N}_{2}$ block with the same boundary. Then ${\cal N}^{\prime}={\cal N}_{2^{\ell+1}}$ .

Proof.

We prove the statement by induction. The base case is trivial, ${\cal N}_{1}$ is entirely replaced with ${\cal N}_{2}$ . For the induction step, assume that the statement holds for every ${\cal N}_{2^{\ell^{\prime}}}$ such that $\ell^{\prime}<\ell$ . To show it for ${\cal N}_{2^{\ell}}$ , we observe that it consists of ${\cal N}_{2^{\ell-1}}$ blocks. For each such block, if we replace every ${\cal N}_{1}$ block with ${\cal N}_{2}$ , it becomes ${\cal N}_{2^{\ell}}$ by the induction hypothesis. Therefore, the whole switching network becomes ${\cal N}_{2^{\ell+1}}$ . $\hfill\blacktriangleleft$

4.1.2 Correctness of the construction

Next, we show that this construction is indeed a switching network that simultaneously decides the connectivity of all $v_{i}$ to $u$ . The proofs in this section follow the general ideas of [18, Chapter 3], adapted to the setting of our switching network.

Lemma 17.

For every $\ell\in\{0,\dots,\log L\}$ and $u,v_{i}\in V$ , $v_{i}$ is reachable from $u$ by a path of length at most $2^{\ell}$ in $G$ if and only if source $[u]$ and sink $[u,v_{i}]$ are connected in ${\cal N}_{2^{\ell}}(u)(G)$ .

To prove the statement of Lemma 17, we define the following pebbling game on the input graph $G$ .

$\blacksquare$

Initially, there is one pebble on the vertex $u$ ;
$\blacksquare$

For vertices $v,v^{\prime}\in V$ such that $(v,v^{\prime})\in E$ , if there is a pebble on $v$ , it is legal to put a pebble on $v^{\prime}$ or remove a pebble from $v^{\prime}$ .

In such a game, various choices of legal moves give rise to different “pebblings” – sets of vertices containing pebbles – of the graph. Clearly no vertex not reachable from $u$ can ever be pebbled (i.e., contain a pebble). Restricting the number of pebbles available may further restrict the possible configurations achievable, as the following two lemmas show.

Lemma 18 ([15]).

Let $D(\ell)$ be the maximal distance from $u$ on which a vertex can be pebbled if $\ell$ pebbles are available in the game. Then $D(\ell)\leq 2^{\ell-1}-1$ .

Lemma 19.

Let $D_{r}(\ell)$ be the maximal distance from $u$ such that it is possible to obtain pebbling configuration $[u,v]$ for some $v\in V$ using only $\ell$ pebbles. Then $D_{r}(\ell)\leq 2^{\ell-2}$

Proof.

We prove the statement by showing that $D_{r}(\ell+1)\leq D(\ell)+1$ . The claim then follows from Lemma 18. Assume for contradiction that it is possible to obtain a configuration $[u,u_{D(\ell)+2}]$ for some $u_{D(\ell)+2}\in V(G)$ such that the distance from $u$ to $u_{D(\ell)+2}$ is at least $D(\ell)+2$ . Before the last time a pebble is placed on $u_{D(\ell)+2}$ , there is a pebble on some $u_{D(\ell)+1}\in V(G)$ such that the distance from $u$ to $u_{D(\ell)+1}$ is at least $D(\ell)+1$ . After this, the pebble is removed from $u_{D(\ell)+1}$ using only $\ell$ pebbles. Consider the sequence of moves that accomplishes this in reverse. It is a sequence of moves that allows to put a pebble on $u_{D(\ell)+1}$ using only $\ell$ pebbles, since one pebble always stays on $u_{D(\ell)+2}$ . This is a contradiction, since the distance from $u$ to $u_{D(\ell)+1}$ is at least $D(\ell)+1$ . $\hfill\blacktriangleleft$

Lemma 20.

If a vertex $v\in V(G)$ is reachable from $u$ by a path of length at most $L$ in $G$ , then it is possible to obtain pebbling configuration $[u,v]$ using $\log L+2$ pebbles and $L^{\log 3}$ moves of the pebbling game on $G$ .

Proof.

Let $u=u_{0},u_{1},\ldots,u_{L}=v$ be the path from $u$ to $v$ in $G$ . Without loss of generality, its length is $L$ , which is a power of $2$ . We show by induction how to put pebbles on vertices of the path to obtain the configuration $[u,v]$ . Assume that there is a sequence of $M_{k}$ moves that ends in the configuration $[u,u_{k}]$ , $k\leq L/2$ . Then we can obtain $[u,u_{2k}]$ as follows, using $M_{2k}=3T_{k}$ moves.

1.

Perform the sequence of $T_{k}$ moves to obtain $[u,v_{k}]$ ;
2.

Perform the same sequence of $T_{k}$ moves with respect to $v_{k}$ to obtain $[u,v_{k},v_{2k}]$ ;
3.

Perform step 1 in reverse to obtain $[u,v_{2k}]$ .

The base case is putting a pebble on $v_{1}$ while there is a pebble on $u$ , which is a valid pebbling game move. In the base case, we use $2$ pebbles while traversing distance $1$ in $M_{1}=1$ moves. In the induction step, we double the distance from $u$ and use one additional pebble for this. Therefore, we need $\log(L)+2$ pebbles in order to obtain $[u,v]$ , and $M_{L}=3M_{L/2}=3^{\log L}=L^{\log 3}$ . $\hfill\blacktriangleleft$

Lemma 21.

Let $S$ be a list of vertices of $G$ . If pebbling configuration $[S]$ can be obtained in the pebbling game on $G$ then every $v\in S$ is reachable from $u$ in $G$ .

Proof.

We prove this statement by induction. The base case is the starting configuration $[u]$ , the starting vertex $u$ is reachable from itself. For the induction step we assume that $[S]$ is a pebbling configuration that can be obtained in the pebbling game and each vertex in $S$ is reachable from $u$ in $G$ . Then, we consider the two types of possible pebbling game moves.

$\blacksquare$

If we remove a pebble from a vertex in $S$ , then all remaining vertices remain reachable from $u$ .
$\blacksquare$

If we put a pebble on a new vertex $v^{\prime}$ , then it is reachable by some vertex $v\in S$ . Since $v$ is reachable from $u$ by the induction hypothesis, we can combine paths form $u$ to $v$ and from $v$ to $v^{\prime}$ and conclude that $v^{\prime}$ is reachable from $u$ .

$\hfill\blacktriangleleft$

Lemma 22.

It is possible to obtain pebbling configuration $[u,v]$ in the pebbling game on $G$ if and only if there is a path from $u$ to $v$ in $G$ .

Proof.

If there is a path from $u$ to $v$ in $G$ , then, by Lemma 20, configuration $[u,v]$ can be obtained in the pebbling game.

If it is possible to obtain pebbling configuration $[u,v]$ in the pebbling game on $G$ , then, by Lemma 21, $v$ is reachable from $u$ in $G$ . $\hfill\blacktriangleleft$

Lemma 23.

Every path in ${\cal N}_{2^{\ell}}(u)(G)$ corresponds to a sequence of moves in the pebbling game on $G$ transforming the corresponding configurations.

Proof.

Every vertex of the switching network contains a list of vertices of $G$ and represents a configuration of pebbles. By construction, every edge that is “on” is of the form $\{[S],[S,v^{\prime}]\}$ labeled by $(v,v^{\prime})\in E(G)$ for some $v\in S$ . Therefore, depending on the direction, an edge of a path in the switching network corresponds either to adding a pebble to a vertex of $G$ or removing a pebble from a vertex of $G$ . $\hfill\blacktriangleleft$

Proof of Lemma 17.

We prove by induction that if $v_{i}$ is reachable from $u$ by a path of length $2^{\ell}$ , then the source $[u]$ and the sink $[u,v_{i}]$ are connected in $\mathcal{N}_{2^{\ell}}(u)(G)$ .

Base case.

For $\ell=0$ , consider $\mathcal{N}_{1}(u)(G)$ . If the edge $(u,v_{i})$ is present in $G$ , then the edge with query label $(u,v_{i})$ and endpoints $[u]$ and $[u,v_{i}]$ is present in $\mathcal{N}_{1}(u)(G)$ . Consequently, $[u]$ and $[u,v_{i}]$ are connected.

Induction step.

Assume the claim holds for $2^{\ell-1}$ . Let $p$ be a path of length at most $2^{\ell}$ from $u$ to $v_{i}$ in $G$ , and let $u^{\prime}$ denote the midpoint of $p$ . Then $u^{\prime}$ is reachable from $u$ by a path of length at most $2^{\ell-1}$ , and $v_{i}$ is reachable from $u^{\prime}$ by a path of length at most $2^{\ell-1}$ . By the induction hypothesis:

$\blacksquare$

$[u]$ and $[u,u^{\prime}]$ are connected in $\mathcal{N}_{2^{\ell-1}}(u)(G)$ ;
$\blacksquare$

$[u,u^{\prime}]$ and $[u,u^{\prime},v_{i}]$ are connected in $\mathcal{N}^{u}_{2^{\ell-1}}(u^{\prime})(G)$ ;
$\blacksquare$

$[u,u^{\prime},v_{i}]$ and $[u,v_{i}]$ are connected in ${\sf Rev}(\mathcal{N}^{v_{i}}_{2^{\ell-1}}(u)(G))$ .

Concatenating these paths yields a path from $[u]$ to $[u,v_{i}]$ in $\mathcal{N}_{2^{\ell}}(u)(G)$ . This completes the induction.

If source $[u]$ and sink $[u,v_{i}]$ are connected in ${\cal N}_{2^{\ell}}(u)(G)$ , then, by Lemma 23, there is a sequence of pebbling game moves on $G$ that transforms $[u]$ into $[u,v_{i}]$ . Therefore, by Lemma 22, there is a path from $u$ to $v_{i}$ in $G$ . Note that the configurations in the sequence contain at most $\ell+2$ vertices of $G$ , by construction of ${\cal N}_{2^{\ell}}(u)(G)$ . Hence, by Lemma 19, the path in $G$ is of length at most $2^{\ell}$ . $\hfill\blacktriangleleft$

4.2 Complexity analysis of the switching network

Lemma 24.

Fix any $\ell\in\{0,\dots,\log L\}$ and $u,v\in V$ such that there is a path from $u$ to $v$ in $G$ of length at most $2^{\ell}$ . Then there is a path connecting the source $[u]$ and the sink $[u,v]$ in ${\cal N}_{2^{\ell}}(u)(G)$ of length at most $2^{\ell\log 3}$ .

Proof.

The statement of this lemma follows directly from the proof of Lemma 17. $\hfill\blacktriangleleft$

Lemma 25.

For any $\ell\in\{0,\dots,\log L\}$ , and $u\in V$ , $|E({\cal N}_{2^{\ell}}(u))|\leq(2n+1)^{\ell}n$ .

Proof.

$\left|E({\cal N}_{2^{\ell}}(u))\right|=(2n+1)\left|E({\cal N}_{2^{\ell-1}}(u))% \right|=(2n+1)^{\ell}\left|E({\cal N}_{1}(u))\right|=(2n+1)^{\ell}n.$ $\hfill\blacktriangleleft$

4.3 Complexity of the subroutine

It remains to justify the basis-generation assumption required by Theorem 7. We use the following technical lemma, whose proof is deferred to the full version.

Lemma 26.

There exists an orthonormal basis of ${\cal B}^{\perp}({\cal N}_{L}(s,t))$ that can be generated in time ${\widetilde{O}}(1)$ .

We conclude by combining the switching network and corresponding basis generation we have given in the previous sections with Theorem 7 to prove Theorem 8, which states the existence of an algorithm for $\textsc{Dist}_{L}$ .

Proof of Theorem 8.

From Lemma 17, it follows that the switching network ${\cal N}_{L}(s,t)$ accepts $G$ if and only if there is a path of length at most $L$ from $s$ to $t$ in $G$ . We apply Theorem 7 to ${\cal N}_{L}(s,t)$ . By Lemma 24, whenever there is a $s t$ -path of length $\leq L$ in $G$ , there is a path from the source $[s]$ to the sink $[s,t]$ in ${\cal N}_{L}(s,t)(G)$ of length at most $W_{+}:=L^{\log 3}$ . By Lemma 25, $|E({\cal N}_{L}(s,t))|\leq(2n+1)^{\log L}n$ . By Lemma 26, there exists an orthonormal basis of ${\cal B}^{\perp}({\cal N}_{L}(s,t))$ that can be generated in time $T_{B}={\widetilde{O}}(1)$ . Hence, by Theorem 7, there exists a quantum algorithm that decides whether there is a path of length at most $L$ from $s$ to $t$ in $G$ in time

O(T_{B}\sqrt{|E({\cal N}_{L}(u,v))|W_{+}})={\widetilde{O}}\left(\left(L^{\log 3% }(2n+1)^{\log L}n\right)^{1/2}\right)

and space

O(\log\left|E({\cal N}_{L}(u,v))\right|)=O(\log L\log n).\

$\hfill\blacktriangleleft$

References

[1] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.
[2] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Pearson, 2nd edition, 2006.
[3] Simon Apers and Roman Edenhofer. Directed st-Connectivity with Few Paths Is in Quantum Logspace. In Srikanth Srinivasan, editor, 40th Computational Complexity Conference (CCC 2025), volume 339 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:15, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CCC.2025.18.
[4] Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter. (No) Quantum Space-Time Tradeoff for USTCON. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms (ESA 2023), volume 274 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:17, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2023.10.
[5] Christel Baier and Joost-Pieter Katoen. Principles of Model Checking. MIT Press, 2008.
[6] Greg Barnes, Jonathan F Buss, Walter L Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed st connectivity. SIAM Journal on Computing, 27(5):1273–1282, 1998. doi:10.1137/S0097539793283151.
[7] Aleksandrs Belovs and Stacey Jeffery. Space-efficient quantum error reduction without log factors, 2025. arXiv: 2502.09249
[8] Aleksandrs Belovs, Stacey Jeffery, and Duyal Yolcu. Taming quantum time complexity. Quantum, 8(1444), 2024. arXiv: 2311.15873 doi:10.22331/q-2024-08-23-1444.
[9] Aleksandrs Belovs and Ben W. Reichardt. Span programs and quantum algorithms for $s t$ -connectivity and claw detection. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), pages 193–204, 2012. doi:10.1007/978-3-642-33090-2_18.
[10] Edmund M. Clarke, Orna Grumberg, and Doron A. Peled. Model Checking. MIT Press, 1999.
[11] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310–1328, 2006. Earlier version in ICALP’04. arXiv: quant-ph/0401091 doi:10.1137/050644719.
[12] Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum algorithms for connectivity and related problems. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA), pages 49:1–49:13, 2018. doi:10.4230/LIPIcs.ESA.2018.49.
[13] Stacey Jeffery and Shelby Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1(26), 2017. doi:10.22331/q-2017-08-17-26.
[14] Stacey Jeffery and Galina Pass. Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), volume 327 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1–54:16, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2025.54.
[15] Ming Li and Paul Vitányi. Reversibility and adiabatic computation: trading time and space for energy. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 452(1947):769–789, 1996.
[16] Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Principles of Program Analysis. Springer, 1999.
[17] Aaron Potechin. Bounds on monotone switching networks for directed connectivity. Journal of the ACM, 9(4), 2014.
[18] Aaron H Potechin. Analyzing monotone space complexity via the switching network model. PhD thesis, Massachusetts Institute of Technology, 2015.
[19] Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, Volumes 1–2. Computer Science Press, 1988–1989.

[bib.bib1] [1] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.

[bib.bib2] [2] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Pearson, 2nd edition, 2006.

[bib.bib3] [3] Simon Apers and Roman Edenhofer. Directed st-Connectivity with Few Paths Is in Quantum Logspace. In Srikanth Srinivasan, editor, 40th Computational Complexity Conference (CCC 2025), volume 339 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:15, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CCC.2025.18.

[bib.bib4] [4] Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter. (No) Quantum Space-Time Tradeoff for USTCON. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms (ESA 2023), volume 274 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:17, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2023.10.

[bib.bib5] [5] Christel Baier and Joost-Pieter Katoen. Principles of Model Checking. MIT Press, 2008.

[bib.bib6] [6] Greg Barnes, Jonathan F Buss, Walter L Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed st connectivity. SIAM Journal on Computing, 27(5):1273–1282, 1998. doi:10.1137/S0097539793283151.

[bib.bib7] [7] Aleksandrs Belovs and Stacey Jeffery. Space-efficient quantum error reduction without log factors, 2025. arXiv: 2502.09249

[bib.bib8] [8] Aleksandrs Belovs, Stacey Jeffery, and Duyal Yolcu. Taming quantum time complexity. Quantum, 8(1444), 2024. arXiv: 2311.15873 doi:10.22331/q-2024-08-23-1444.

[bib.bib9] [9] Aleksandrs Belovs and Ben W. Reichardt. Span programs and quantum algorithms for $s t$ -connectivity and claw detection. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), pages 193–204, 2012. doi:10.1007/978-3-642-33090-2_18.

[bib.bib10] [10] Edmund M. Clarke, Orna Grumberg, and Doron A. Peled. Model Checking. MIT Press, 1999.

[bib.bib11] [11] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310–1328, 2006. Earlier version in ICALP’04. arXiv: quant-ph/0401091 doi:10.1137/050644719.

[bib.bib12] [12] Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum algorithms for connectivity and related problems. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA), pages 49:1–49:13, 2018. doi:10.4230/LIPIcs.ESA.2018.49.

[bib.bib13] [13] Stacey Jeffery and Shelby Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1(26), 2017. doi:10.22331/q-2017-08-17-26.

[bib.bib14] [14] Stacey Jeffery and Galina Pass. Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), volume 327 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1–54:16, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2025.54.

[bib.bib15] [15] Ming Li and Paul Vitányi. Reversibility and adiabatic computation: trading time and space for energy. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 452(1947):769–789, 1996.

[bib.bib16] [16] Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Principles of Program Analysis. Springer, 1999.

[bib.bib17] [17] Aaron Potechin. Bounds on monotone switching networks for directed connectivity. Journal of the ACM, 9(4), 2014.

[bib.bib18] [18] Aaron H Potechin. Analyzing monotone space complexity via the switching network model. PhD thesis, Massachusetts Institute of Technology, 2015.

[bib.bib19] [19] Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, Volumes 1–2. Computer Science Press, 1988–1989.

A Quantum Time-Space Tradeoff for Directed s⁢t-Connectivity

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our Contribution

Our Techniques

Open Problems

Organization

2 Preliminaries

2.1 Graphs

Definition 1.

Definition 2.

2.2 Switching Networks

Definition 3.

▶ Remark 4.

Definition 5 (Basis Generation).

Lemma 6.

Theorem 7.

3 Quantum Algorithm for DSTCON

Theorem 8.

Corollary 9.

Proof.

3.1 BFS algorithm that calls the quantum short path subroutine

Lemma 10.

Theorem 11.

3.2 Complexity comparison: classical vs. quantum

Theorem 12 ([6]).

Theorem 13.

Proof.

▶ Remark 14.

4 Quantum short path subroutine

4.1 Switching network

4.1.1 Graph construction

Base construction

Recursive construction

Lemma 15.

Proof.

Lemma 16.

Proof.

4.1.2 Correctness of the construction

Lemma 17.

Lemma 18 ([15]).

Lemma 19.

Proof.

Lemma 20.

Proof.

Lemma 21.

Proof.

Lemma 22.

Proof.

Lemma 23.

Proof.

Proof of Lemma 17.

Base case.

Induction step.

4.2 Complexity analysis of the switching network

Lemma 24.

Proof.

Lemma 25.

Proof.

4.3 Complexity of the subroutine

Lemma 26.

Proof of Theorem 8.

References

A Quantum Time-Space Tradeoff for Directed $s t$ -Connectivity

$\blacktriangleright$ Remark 4.

$\blacktriangleright$ Remark 14.