Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

Galina Pass

Published Jan 1, 2026• 0 citations
OpenAlex

Abstract

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.

Related papers

(No) Quantum Space-Time Tradeoff for USTCON

Simon Apers, Stacey Jeffery, Galina Pass +1 more

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

arXiv:2212.00094•Leibniz international proceedings in informatics•Nov 30, 2022•5 citations

Quantum simulations of classical random walks and undirected graph connectivity

John Watrous

There are a number of questions in quantum complexity that have been resolved in the time-bounded setting, but remain open in the space-bounded setting. For example, it is not currently known if space-bounded probabilistic computations can be simulated by space-bounded quantum machines without allowing measurements during the computation, while it is known that an analogous statement holds in the time-bounded case. A more general question asks if measurements during a quantum computation can allow for more space-efficient solutions to certain problems. In this paper we show that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes-random walks on undirected graphs-without relying on measurements during the computation. By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and require a single measurement at the end of their computations. It follows that symmetric logspace is contained in the quantum analogue of randomized logspace, i.e., SL/spl sube/QR/sub H/L.

IEEE Conference on Computational Complexity (CCC)•Jan 20, 2003•6 citations

Time-Space Tradeoffs and Query Complexity in Statistics, Coding Theory, and Quantum Computing

Widad Machmouchi

Computational complexity is the field that studies the computational resources needed by algorithms to correctly solve computational problems. In this thesis, we derive lower bounds on the computational complexity of different problems for different classes of algorithms. The computational resources we consider are the running time, the memory usage and the input query complexity; i.e., the number of positions in the input that the algorithm reads. While deriving upper bounds involves constructing algorithms that run efficiently in their computational resources, lower bounds for a computational problem establish limits on how fast or space-efficient any algorithm solving that problem can be. We consider two main themes of lower bounds: time-space tradeoffs and query complexity lower bounds. Time-space tradeoffs define a relation between the running time and space of any algorithm solving a certain problems. They give a complete picture of the hardness of a problem by deriving a lower bound on one resource when the other is limited. Query complexity measures the depth of a decision tree computing the problem. We derive several lower bounds and upper bounds for different problems on different types of classical computational models and on quantum computers, where the queries to the input are represented by quantum operations operating on the qubits of the algorithm: 1) We derive the largest time-space tradeoff known for a randomized algorithm solving an explicit problem. We consider the pointer jumping problem, also known as the outdegree-1 graph accessibility problem and derive a T in Ω(n log(n/S) log log(n/S)) time-space tradeoff for any randomized oblivious algorithm computing it. Oblivious algorithms have the property that the sequence of operations performed is independent of the value of the input. We derive a similar lower bound for randomized oblivious algorithms with boolean inputs. 2) Frequency moments and order statistics are attributes computed on a sequence of numbers and are extremely relevant in various data analysis settings. We consider computing several copies of these functions on overlapping sequences of numbers by considering a window of a fixed length and sliding it over the input; these versions are called sliding-window versions of these functions. We give hardness separations between the sliding-window versions of these statistics. On one hand, we give a TS in Ω(n 2 ) lower bounds for any algorithm computing sliding-window frequency moments. To complement our lower bound, we give a TS in O(n 2 log c n) comparison-based algorithm for sliding-window frequency moments. On the other hand we describe a T 2 S in O(n 3 log c n) algorithm for sliding-window element distinctness. For order statistics, we derive a similar lower bound of TS in Ω(n 2 ) for any algorithm computing a sliding-widow version of the median, while for the sliding window version of maximum (and minimum), we construct an O(n log n)-time, logarithmic space algorithm. 3) We study the increase in complexity on quantum computers when considering sliding-window frequency moments. We show that quantum computers do not require the same increase in complexity as their classical counterparts by constructing a quantum algorithm for sliding-window version of the zero th frequency moments running in time O(n 3/2 ) and logarithmic space, thus beating the classical lower bound for this problem. 4) In the area of error-correcting codes, we study the query complexity of error detection and correction algorithms. We prove that linear codes over large alphabets that are small in size and concentrated in terms of their codeword weights have testers and correctors that require only a constant number of queries to a word received across a noisy channel. Such codes are called locally-testable and self-correctable. As random codes of small size have the property that their codeword weights are concentrated in a small range of values, they are also locally-testable and self-correctable with high probability. 5) For linear codes with information-efficient encoding, we study the tradeoff between the time and space of their encoders, and their error-correction property. We derive properties on generator matrices of asymptotically good linear codes that guarantee an optimal time-space tradeoff of TS in Ω(n 2 ) for any algorithm encoding them. Moreover, we prove a first step in an approach to establish these properties for all generator matrices of such codes. 6) To compare classical computers to their quantum counterparts, we consider the query complexity of quantum algorithms computing frequency moments and the onto function that takes as input a function and determines whether it is surjective. We prove that any quantum computer computing the onto function or the parity of the zero th frequency moment requires a linear number of queries to the input. Since the onto function with boolean inputs has a simple polynomial-size, constant-depth circuit, we obtain an almost linear lower bound on the query complexity of AC 0 , a special class of circuits that have polynomial size, constant depth and unbounded fan-in for their gates.

•Jul 25, 2013•0 citations

Multidimensional quantum walks and the multiplicative ladder adversary

S.A. Zur

Quantum computing offers the potential to solve problems more efficiently than classical methods, yet understanding its capabilities requires new conceptual frameworks. This dissertation explores quantum algorithms with a focus on maintaining connections to classical intuition, clarifying both their strengths and limitations. In Part I, we explore the capabilities of a class of quantum algorithms known as quantum walks. These quantum walks, the quantum analogs of classical random walks, serve as powerful yet accessible tools for solving a variety of computational problems. Our key contribution is the development of a novel way to construct quantum walks, resulting in multidimensional quantum walks. By applying these walks to the $k$-distinctness problem, we achieve a time-efficient algorithm matching the best-known query upper bound up to polylogarithmic factors. Additionally, applying them to the welded tree problem results in exponential speedups, marking the first instance of a discrete quantum walk to do so. Furthermore, we extend the well-known link between quantum walks and electrical networks to the multidimensional quantum walks. In Part II, we turn to the limitations of quantum algorithms by examining techniques for establishing quantum query lower bounds, representing the minimum computational cost required for any quantum algorithm to solve a given computational problem, regardless of the quantum algorithm used. To this goal, we introduce the multiplicative ladder adversary method, a simplified version of the multiplicative adversary method which unifies the compressed oracle technique within the broader adversary framework while extending its applicability, offering a more intuitive approach to establishing quantum lower bounds.

•Jan 1, 2025•0 citations

Quantum Time-Space Tradeoffs for Matrix Problems

Paul W. Beame, Niels Kornerup, Michael Whitmeyer

Abstract. We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs, several of which are tight for every space bound, also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices [Formula: see text], including the discrete Fourier transform matrix, we prove that quantum circuits with at most [Formula: see text] input queries and [Formula: see text] qubits of memory require [Formula: see text] to compute matrix-vector product [Formula: see text] for [Formula: see text]. We similarly prove that matrix multiplication for [Formula: see text] binary matrices requires [Formula: see text]. Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems with any space bound. We obtain matching lower bounds for the stronger notion of quantum cumulative memory complexity—the sum of the space per layer of a circuit. We also consider Boolean (i.e., AND-OR) matrix multiplication and matrix-vector products, improving the previous quantum time-space tradeoff lower bounds for [Formula: see text] Boolean matrix multiplication to [Formula: see text] from [Formula: see text]. Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.

arXiv:2401.05321•SIAM Journal on Computing•May 20, 2026•5 citations

A Quantum Time-Space Tradeoff for Directed $st$-Connectivity

Stacey Jeffery, Galina Pass

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.

arXiv:2510.08403•Leibniz international proceedings in informatics•Oct 9, 2025•2 citations
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.
Undirected ststst-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)T=\tilde{O}(n^2/S)T=O~(n2/S) for any SSS such that S=Ω(log⁡(n))S=Ω(\log (n))S=Ω(log(n)) and S=O(n2/m)S=O(n^2/m)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)\tilde{O}(n)O~(n) and space O(log⁡(n))O(\log (n))O(log(n)) simultaneously. This improves on previous results, which required either O(log⁡(n))O(\log (n))O(log(n)) space and O~(n1.5)\tilde{O}(n^{1.5})O~(n1.5) time, or O~(n)\tilde{O}(n)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.
There are a number of questions in quantum complexity that have been resolved in the time-bounded setting, but remain open in the space-bounded setting. For example, it is not currently known if space-bounded probabilistic computations can be simulated by space-bounded quantum machines without allowing measurements during the computation, while it is known that an analogous statement holds in the time-bounded case. A more general question asks if measurements during a quantum computation can allow for more space-efficient solutions to certain problems. In this paper we show that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes-random walks on undirected graphs-without relying on measurements during the computation. By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and require a single measurement at the end of their computations. It follows that symmetric logspace is contained in the quantum analogue of randomized logspace, i.e., SL/spl sube/QR/sub H/L.
Computational complexity is the field that studies the computational resources needed by algorithms to correctly solve computational problems. In this thesis, we derive lower bounds on the computational complexity of different problems for different classes of algorithms. The computational resources we consider are the running time, the memory usage and the input query complexity; i.e., the number of positions in the input that the algorithm reads. While deriving upper bounds involves constructing algorithms that run efficiently in their computational resources, lower bounds for a computational problem establish limits on how fast or space-efficient any algorithm solving that problem can be. We consider two main themes of lower bounds: time-space tradeoffs and query complexity lower bounds. Time-space tradeoffs define a relation between the running time and space of any algorithm solving a certain problems. They give a complete picture of the hardness of a problem by deriving a lower bound on one resource when the other is limited. Query complexity measures the depth of a decision tree computing the problem. We derive several lower bounds and upper bounds for different problems on different types of classical computational models and on quantum computers, where the queries to the input are represented by quantum operations operating on the qubits of the algorithm: 1) We derive the largest time-space tradeoff known for a randomized algorithm solving an explicit problem. We consider the pointer jumping problem, also known as the outdegree-1 graph accessibility problem and derive a T in Ω(n log(n/S) log log(n/S)) time-space tradeoff for any randomized oblivious algorithm computing it. Oblivious algorithms have the property that the sequence of operations performed is independent of the value of the input. We derive a similar lower bound for randomized oblivious algorithms with boolean inputs. 2) Frequency moments and order statistics are attributes computed on a sequence of numbers and are extremely relevant in various data analysis settings. We consider computing several copies of these functions on overlapping sequences of numbers by considering a window of a fixed length and sliding it over the input; these versions are called sliding-window versions of these functions. We give hardness separations between the sliding-window versions of these statistics. On one hand, we give a TS in Ω(n 2 ) lower bounds for any algorithm computing sliding-window frequency moments. To complement our lower bound, we give a TS in O(n 2 log c n) comparison-based algorithm for sliding-window frequency moments. On the other hand we describe a T 2 S in O(n 3 log c n) algorithm for sliding-window element distinctness. For order statistics, we derive a similar lower bound of TS in Ω(n 2 ) for any algorithm computing a sliding-widow version of the median, while for the sliding window version of maximum (and minimum), we construct an O(n log n)-time, logarithmic space algorithm. 3) We study the increase in complexity on quantum computers when considering sliding-window frequency moments. We show that quantum computers do not require the same increase in complexity as their classical counterparts by constructing a quantum algorithm for sliding-window version of the zero th frequency moments running in time O(n 3/2 ) and logarithmic space, thus beating the classical lower bound for this problem. 4) In the area of error-correcting codes, we study the query complexity of error detection and correction algorithms. We prove that linear codes over large alphabets that are small in size and concentrated in terms of their codeword weights have testers and correctors that require only a constant number of queries to a word received across a noisy channel. Such codes are called locally-testable and self-correctable. As random codes of small size have the property that their codeword weights are concentrated in a small range of values, they are also locally-testable and self-correctable with high probability. 5) For linear codes with information-efficient encoding, we study the tradeoff between the time and space of their encoders, and their error-correction property. We derive properties on generator matrices of asymptotically good linear codes that guarantee an optimal time-space tradeoff of TS in Ω(n 2 ) for any algorithm encoding them. Moreover, we prove a first step in an approach to establish these properties for all generator matrices of such codes. 6) To compare classical computers to their quantum counterparts, we consider the query complexity of quantum algorithms computing frequency moments and the onto function that takes as input a function and determines whether it is surjective. We prove that any quantum computer computing the onto function or the parity of the zero th frequency moment requires a linear number of queries to the input. Since the onto function with boolean inputs has a simple polynomial-size, constant-depth circuit, we obtain an almost linear lower bound on the query complexity of AC 0 , a special class of circuits that have polynomial size, constant depth and unbounded fan-in for their gates.
Quantum computing offers the potential to solve problems more efficiently than classical methods, yet understanding its capabilities requires new conceptual frameworks. This dissertation explores quantum algorithms with a focus on maintaining connections to classical intuition, clarifying both their strengths and limitations. In Part I, we explore the capabilities of a class of quantum algorithms known as quantum walks. These quantum walks, the quantum analogs of classical random walks, serve as powerful yet accessible tools for solving a variety of computational problems. Our key contribution is the development of a novel way to construct quantum walks, resulting in multidimensional quantum walks. By applying these walks to the kkk-distinctness problem, we achieve a time-efficient algorithm matching the best-known query upper bound up to polylogarithmic factors. Additionally, applying them to the welded tree problem results in exponential speedups, marking the first instance of a discrete quantum walk to do so. Furthermore, we extend the well-known link between quantum walks and electrical networks to the multidimensional quantum walks. In Part II, we turn to the limitations of quantum algorithms by examining techniques for establishing quantum query lower bounds, representing the minimum computational cost required for any quantum algorithm to solve a given computational problem, regardless of the quantum algorithm used. To this goal, we introduce the multiplicative ladder adversary method, a simplified version of the multiplicative adversary method which unifies the compressed oracle technique within the broader adversary framework while extending its applicability, offering a more intuitive approach to establishing quantum lower bounds.
Abstract. We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs, several of which are tight for every space bound, also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices [Formula: see text], including the discrete Fourier transform matrix, we prove that quantum circuits with at most [Formula: see text] input queries and [Formula: see text] qubits of memory require [Formula: see text] to compute matrix-vector product [Formula: see text] for [Formula: see text]. We similarly prove that matrix multiplication for [Formula: see text] binary matrices requires [Formula: see text]. Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems with any space bound. We obtain matching lower bounds for the stronger notion of quantum cumulative memory complexity—the sum of the space per layer of a circuit. We also consider Boolean (i.e., AND-OR) matrix multiplication and matrix-vector products, improving the previous quantum time-space tradeoff lower bounds for [Formula: see text] Boolean matrix multiplication to [Formula: see text] from [Formula: see text]. Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.
A Quantum Time-Space Tradeoff for Directed ststst-Connectivity
Directed ststst-connectivity (DSTCON) is the problem of deciding if there exists a directed path between a pair of distinguished vertices sss and ttt 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{\sf NL}NL-completeness. We show that for any S≥log⁡2(n)S\geq \log^2(n)S≥log2(n), there is a quantum algorithm for DSTCON using space SSS and time T≤212log⁡(n)log⁡(n/S)+o(log⁡2(n))T\leq 2^{\frac{1}{2}\log(n)\log(n/S)+o(\log^2(n))}T≤221​log(n)log(n/S)+o(log2(n)), which is an (up to quadratic) improvement over the best classical algorithm for any S=o(n)S=o(\sqrt{n})S=o(n​). Of the SSS total space used by our algorithm, only O(log⁡2(n))O(\log^2(n))O(log2(n)) is quantum space - the rest is classical. This effectively means that we can trade off classical space for quantum time.