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

Multidimensional quantum walks and the multiplicative ladder adversary

S.A. Zur

Published Jan 1, 2025• 0 citations
OpenAlex

Abstract

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.

Related papers

Multidimensional Quantum Walks

Stacey Jeffery, Sebastian Zur

While the quantum query complexity of k-distinctness is known to be O(n3/4 − 1/4(2k−1)) for any constant k≥ 4 [Belovs, FOCS 2012], the best previous upper bound on the time complexity was O(n1−1/k). We give a new upper bound of O(n3/4 − 1/4(2k−1)) on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in O(n) queries and O(n2) time using this new technique, showing that the new quantum walk framework can achieve exponential speedups.

ACM Symposium on Theory of Computing (STOC)•May 16, 2023•7 citations

A quantum lower bound for path finding in welded trees

Joseph Carolan, Andrew M. Childs, Matthew Coudron +1 more

In the welded tree problem, an algorithm is tasked with navigating a graph formed from two binary trees joined at the leaves through a ``weld'' of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, known efficient quantum algorithms cannot find a path between the roots, as recording the path destroys constructive interference and thus the speedup. We prove that this is inherent: any quantum algorithm needs exponentially many queries to find a path between the roots of an independently matched welded tree graph. This provides an example of a problem that a quantum computer can solve exponentially faster than any classical algorithm by exploring exponentially many paths in superposition, but where it is provably intractable to find any such path. The proof uses compressed permutation oracles to record the progress of a quantum algorithm as it queries the graph. We show that the compressed database remains path-free up to a small error. By controlling such errors and bounding the progress of the algorithm with each compressed oracle query, we show that $Ω(2^{n/12})$ queries are required to find a path in a height-$n$ tree with constant success probability.

quant-pharXiv:2609.26712•Sep 23, 2026•0 citations

Multidimensional Quantum Walks, with Application to $k$-Distinctness

Stacey Jeffery, Sebastian Zur

While the quantum query complexity of $k$-distinctness is known to be $O\left(n^{3/4-1/4(2^k-1)}\right)$ for any constant $k \geq 4$, the best previous upper bound on the time complexity was $\widetilde{O}\left(n^{1-1/k}\right)$. We give a new upper bound of $\widetilde{O}\left(n^{3/4-1/4(2^k-1)}\right)$ on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in $O(n)$ queries and $O(n^2)$ time using this new technique, showing that the new quantum walk framework can achieve exponential speedups. Comment: Journal version for TheoretiCS

arXiv:2208.13492•TheoretiCS•Mar 4, 2025•3 citations

Recovering the Original Simplicity: Succinct and Exact Quantum Algorithm for the Welded Tree Problem

Guanzhong Li, Lvzhou Li, Jingquan Luo

Abstract This work revisits quantum algorithms for the well-known welded tree problem, proposing a very succinct quantum algorithm based on the simplest coined quantum walks. It simply iterates the naturally defined coined quantum walk operator for a predetermined time and finally measure, where the predetermined time can be efficiently computed on classical computers. Then, the algorithm returns the correct answer deterministically, and achieves exponential speedups over any classical algorithm. The significance of the results may be seen as follows. (i) Our algorithm is rather simple compared with the one in (Jeffery and Zur, STOC'2023), which not only breaks the stereotype that coined quantum walks can only achieve quadratic speedups over classical algorithms, but also demonstrates the power of the simplest quantum walk model. (ii) Our algorithm theoretically achieves certainty of success, which is not possible with existing methods. Thus, it becomes one of the few examples that exhibit exponential separation between deterministic (exact) quantum and randomized query complexities, which may also change people's perception that since quantum mechanics is inherently probabilistic, it is impossible to have a deterministic quantum algorithm with exponential speedups for the welded tree problem.

Algorithmica•Oct 4, 2024•4 citations

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

Galina Pass

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.

•Jan 1, 2026•0 citations

A Brief Introduction to Quantum Query Complexity

Yassine Hamoudi

Quantum query complexity is a fundamental model for analyzing the computational power of quantum algorithms. It has played a key role in characterizing quantum speedups, from early breakthroughs such as Grover's and Simon's algorithms to more recent developments in quantum cryptography and complexity theory. This document provides a structured introduction to quantum query lower bounds, focusing on four major techniques: the hybrid method, the polynomial method, the recording method, and the adversary method. Each method is developed from first principles and illustrated through canonical problems. Additionally, the document discusses how the adversary method can be used to derive upper bounds, highlighting its dual role in quantum query complexity. The goal is to offer a self-contained exposition accessible to readers with a basic background in quantum computing, while also serving as an entry point for researchers interested in the study of quantum lower bounds.

arXiv:2508.08852•Aug 12, 2025•0 citations
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.
While the quantum query complexity of k-distinctness is known to be O(n3/4 − 1/4(2k−1)) for any constant k≥ 4 [Belovs, FOCS 2012], the best previous upper bound on the time complexity was O(n1−1/k). We give a new upper bound of O(n3/4 − 1/4(2k−1)) on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in O(n) queries and O(n2) time using this new technique, showing that the new quantum walk framework can achieve exponential speedups.
In the welded tree problem, an algorithm is tasked with navigating a graph formed from two binary trees joined at the leaves through a ``weld'' of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, known efficient quantum algorithms cannot find a path between the roots, as recording the path destroys constructive interference and thus the speedup. We prove that this is inherent: any quantum algorithm needs exponentially many queries to find a path between the roots of an independently matched welded tree graph. This provides an example of a problem that a quantum computer can solve exponentially faster than any classical algorithm by exploring exponentially many paths in superposition, but where it is provably intractable to find any such path. The proof uses compressed permutation oracles to record the progress of a quantum algorithm as it queries the graph. We show that the compressed database remains path-free up to a small error. By controlling such errors and bounding the progress of the algorithm with each compressed oracle query, we show that Ω(2n/12)Ω(2^{n/12})Ω(2n/12) queries are required to find a path in a height-nnn tree with constant success probability.
Multidimensional Quantum Walks, with Application to kkk-Distinctness
While the quantum query complexity of kkk-distinctness is known to be O(n3/4−1/4(2k−1))O\left(n^{3/4-1/4(2^k-1)}\right)O(n3/4−1/4(2k−1)) for any constant k≥4k \geq 4k≥4, the best previous upper bound on the time complexity was O~(n1−1/k)\widetilde{O}\left(n^{1-1/k}\right)O(n1−1/k). We give a new upper bound of O~(n3/4−1/4(2k−1))\widetilde{O}\left(n^{3/4-1/4(2^k-1)}\right)O(n3/4−1/4(2k−1)) on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in O(n)O(n)O(n) queries and O(n2)O(n^2)O(n2) time using this new technique, showing that the new quantum walk framework can achieve exponential speedups. Comment: Journal version for TheoretiCS
Abstract This work revisits quantum algorithms for the well-known welded tree problem, proposing a very succinct quantum algorithm based on the simplest coined quantum walks. It simply iterates the naturally defined coined quantum walk operator for a predetermined time and finally measure, where the predetermined time can be efficiently computed on classical computers. Then, the algorithm returns the correct answer deterministically, and achieves exponential speedups over any classical algorithm. The significance of the results may be seen as follows. (i) Our algorithm is rather simple compared with the one in (Jeffery and Zur, STOC'2023), which not only breaks the stereotype that coined quantum walks can only achieve quadratic speedups over classical algorithms, but also demonstrates the power of the simplest quantum walk model. (ii) Our algorithm theoretically achieves certainty of success, which is not possible with existing methods. Thus, it becomes one of the few examples that exhibit exponential separation between deterministic (exact) quantum and randomized query complexities, which may also change people's perception that since quantum mechanics is inherently probabilistic, it is impossible to have a deterministic quantum algorithm with exponential speedups for the welded tree problem.
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.
Quantum query complexity is a fundamental model for analyzing the computational power of quantum algorithms. It has played a key role in characterizing quantum speedups, from early breakthroughs such as Grover's and Simon's algorithms to more recent developments in quantum cryptography and complexity theory. This document provides a structured introduction to quantum query lower bounds, focusing on four major techniques: the hybrid method, the polynomial method, the recording method, and the adversary method. Each method is developed from first principles and illustrated through canonical problems. Additionally, the document discusses how the adversary method can be used to derive upper bounds, highlighting its dual role in quantum query complexity. The goal is to offer a self-contained exposition accessible to readers with a basic background in quantum computing, while also serving as an entry point for researchers interested in the study of quantum lower bounds.