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

arXiv:2304.08395

Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem

Guanzhong Li, Lvzhou Li, Jingquan Luo

Published Apr 17, 2023• 0 citations
arXivHTMLPDF

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 zero-error, 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 impossible to have a deterministic quantum algorithm with exponential speedups for the weled tree problem.

DOI
10.48550/arxiv.2304.08395

Related papers

Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem

Guanzhong Li, Lvzhou Li, Jingquan Luo

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 impossible to have a deterministic quantum algorithm with exponential speedups for the welded tree problem.

Society for Industrial and Applied Mathematics eBooks•Jan 1, 2024•5 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

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

Time-Space Tradeoffs in Searching for a Path in Welded Trees, Classically or Quantumly

Yvan Le Borgne, Shrinidhi Teganahally Sridhara

Welded Trees are a class of graphs designed to exhibit exponential algorithmic speedup for certain search problems via quantum walks, outperforming any classical algorithm. A Welded Tree of depth d consists of two complete binary trees, each of depth d, whose leaves are interconnected by an additional cycle or permutation alternating between the two trees. Access to this graph is provided only through queries to an oracle, which, given a vertex, returns its neighbors. In 2021, Aaronson suggested the FINDING-PATH-TO-EXIT problem, which consists of finding a path to the root of the opposite tree given the root of one tree. This can be seen as an extension of the FINDING-EXIT problem, where the task is simply to find the root of the opposite tree, for which Childs et al. demonstrated an exponential speed-up in 2003. We provide a quantum algorithm for solving the Finding Path To Exit problem that performs Õ(2d/3) queries and also formalize the folklore lower bound that any classical algorithm requires at least Ω̃(2d/2 ) queries. This is the first proof of a polynomial speed-up for this problem over any classical algorithm. In addition, we present and analyze several other algorithms, focusing on the trade-offs between queries and classical or quantum space.

•Sep 3, 2024•0 citations

Exponential Speedups for Quantum Walks in Random Hierarchical Graphs

Shankar Balasubramanian, Tongyang Li, Aram W. Harrow

Abstract There are few known exponential speedups for quantum algorithms and these tend to fall into even fewer families. One speedup that has mostly resisted generalization is the use of quantum walks to traverse the welded-tree graph, due to Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman. We show how to generalize this to a large class of hierarchical graphs in which the vertices are grouped into “supervertices” which are arranged according to a d-dimensional lattice. Supervertices can have different sizes, and edges between supervertices correspond to random connections between their constituent vertices. The hitting times of quantum walks on these graphs are related to the localization properties of zero modes in certain disordered tight binding Hamiltonians. The speedups range from superpolynomial to exponential, depending on the underlying dimension and the random graph model. We also provide concrete realizations of these hierarchical graphs, and introduce a general method for constructing graphs with efficient quantum traversal times using graph sparsification.

arXiv:2307.15062•Communications in Mathematical Physics•Aug 1, 2025•3 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
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 zero-error, 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 impossible to have a deterministic quantum algorithm with exponential speedups for the weled tree problem.
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 impossible to have a deterministic quantum algorithm with exponential speedups for the welded tree problem.
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.
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.
Welded Trees are a class of graphs designed to exhibit exponential algorithmic speedup for certain search problems via quantum walks, outperforming any classical algorithm. A Welded Tree of depth d consists of two complete binary trees, each of depth d, whose leaves are interconnected by an additional cycle or permutation alternating between the two trees. Access to this graph is provided only through queries to an oracle, which, given a vertex, returns its neighbors. In 2021, Aaronson suggested the FINDING-PATH-TO-EXIT problem, which consists of finding a path to the root of the opposite tree given the root of one tree. This can be seen as an extension of the FINDING-EXIT problem, where the task is simply to find the root of the opposite tree, for which Childs et al. demonstrated an exponential speed-up in 2003. We provide a quantum algorithm for solving the Finding Path To Exit problem that performs Õ(2d/3) queries and also formalize the folklore lower bound that any classical algorithm requires at least Ω̃(2d/2 ) queries. This is the first proof of a polynomial speed-up for this problem over any classical algorithm. In addition, we present and analyze several other algorithms, focusing on the trade-offs between queries and classical or quantum space.
Abstract There are few known exponential speedups for quantum algorithms and these tend to fall into even fewer families. One speedup that has mostly resisted generalization is the use of quantum walks to traverse the welded-tree graph, due to Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman. We show how to generalize this to a large class of hierarchical graphs in which the vertices are grouped into “supervertices” which are arranged according to a d-dimensional lattice. Supervertices can have different sizes, and edges between supervertices correspond to random connections between their constituent vertices. The hitting times of quantum walks on these graphs are related to the localization properties of zero modes in certain disordered tight binding Hamiltonians. The speedups range from superpolynomial to exponential, depending on the underlying dimension and the random graph model. We also provide concrete realizations of these hierarchical graphs, and introduce a general method for constructing graphs with efficient quantum traversal times using graph sparsification.
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.