Quantum Information and Quantum Computation
Open Problem Zoo
Random Unsolved Solved

Quantum query complexity of Welded Tree path-finding

Unsolved ID op_17bba2d8f41697f6 Last edited 9 September 2026
Edit
Field
Topic

Problem

Does finding an explicit ENTRANCE-to-EXIT path in the standard Welded Tree oracle problem require exponentially many quantum queries?

For an integer \(n\geq 2\), construct a graph \(G_n\) from two complete binary trees of depth \(n\). Designate the root of the left tree as ENTRANCE \(s\) and the root of the right tree as EXIT \(t\). Join the \(2^n\) leaves of the left tree and the \(2^n\) leaves of the right tree into a uniformly random cycle that alternates between leaves of the two trees. Assign the vertices distinct random binary labels of length \(2n\).

The algorithm is given the label of \(s\) and coherent quantum-query access to an adjacency-list oracle. The oracle is a static function of vertex labels: for every valid vertex label, including labels guessed without prior traversal, it returns the labels of the vertex’s neighbors, and it returns distinguished invalid outputs only for labels that are not vertices and for missing neighbor slots. Validity of a queried label is independent of the algorithm’s query history, and coherent queries may be arbitrary superpositions of label strings.

The path-finding task is to output an explicit sequence of vertex labels \(v_0,v_1,\ldots,v_\ell\) satisfying

\begin{equation} v_0=s, \qquad v_\ell=t, \qquad \{v_{j-1},v_j\}\in E(G_n) \quad \text{for every }1\leq j\leq\ell . \tag{1} \end{equation}

Let \(Q_{\mathrm{WTPath}}(n)\) denote the minimum number of oracle queries used by a quantum algorithm that outputs a valid path satisfying (1) with bounded error on the standard random Welded Tree oracle distribution. The open question is whether there exists a constant \(c>0\) such that, for all sufficiently large \(n\),

\begin{equation} Q_{\mathrm{WTPath}}(n) \geq 2^{cn}. \tag{2} \end{equation}

Equivalently, does the exponential quantum-query lower bound in (2) hold for unrestricted quantum algorithms?

Source

Explicitly posed by Scott Aaronson in Aaronson (2021), Problem 10, as the question of whether a quantum computer requires exponentially many queries to find a left-to-right path in the Welded Tree oracle problem [Aar21]. The distinction originates in the Welded Tree algorithm of Childs et al. (2003), whose quantum walk finds the EXIT but does not identify a particular ENTRANCE-to-EXIT path; Childs, Coudron, and Gilani (2023) describe efficient path-finding versus quantum hardness as a longstanding open problem and prove a restricted no-go result. The statement above is a self-contained formulation of Aaronson’s question rather than a verbatim quotation.

Progress

  • Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman introduced the Welded Tree oracle problem as an early example of an exponential quantum speedup based on quantum walks rather than the quantum Fourier transform: their continuous-time quantum walk reaches the EXIT using polynomially many oracle queries, whereas classical randomized algorithms require exponentially many queries in the relevant black-box model. Crucially, the quantum algorithm finds the label of the EXIT without producing a particular path from the ENTRANCE to the EXIT [CCGS03].

  • The graph always contains short ENTRANCE-to-EXIT paths, so the difficulty is not an exponentially long required output; rather, the quantum walk propagates amplitude through the graph by interference without retaining enough classical information to reconstruct which sequence of vertices constitutes such a path [CCGS03].

  • Aaronson isolated the question explicitly as Problem 10 in his 2021 list of open problems in quantum query complexity, asking whether even a quantum computer requires exponentially many queries to find a left-to-right path in the Welded Tree graph; the lower-bound formulation, rather than merely the absence of a known polynomial-time algorithm, is the canonical form of the open problem [Aar21].

  • Childs, Coudron, and Gilani introduced a class of genuine rooted quantum algorithms: within each branch of their superposition they always store a set of vertex labels forming a connected subgraph that includes the ENTRANCE, and they only provide such meaningful vertex labels as oracle inputs. They proved that these genuine rooted quantum algorithms cannot find an ENTRANCE-to-EXIT path with polynomially many queries [CCG23].

  • The restricted result does not establish the exponential lower bound for unrestricted algorithms: the EXIT-finding quantum walk is itself not rooted in the relevant sense, since it can discard information about the route by which its amplitude reached a vertex. A general path-finding algorithm might therefore exploit precisely this non-rooted, forgetful behavior, and hardness proofs require techniques that can handle such algorithms [CCG23].

  • Efficient quantum path-finding has subsequently been demonstrated on graph families inspired by Welded Trees: Li and Zur constructed a regular welded-tree circuit graph for which multidimensional quantum walks and electrical-flow states yield an exponential quantum speedup for finding an explicit path. This result concerns a modified graph family and does not give an efficient path-finding algorithm for the original randomly welded binary-tree oracle [LZ25].

Comment

Two qualitatively different alternatives remain for the original Welded Tree oracle: either an unrestricted exponential quantum-query lower bound of the form (2), extending beyond the genuine-rooted model, or a quantum algorithm that finds an explicit path using subexponentially many queries. A polynomial-query path-finding algorithm would show an even stronger failure of the exponential conjecture in (2).

References

[CCGS03]
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman, “Exponential Algorithmic Speedup by Quantum Walk,” in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), 59–68 (2003).DOIarXiv
[Aar21]
Scott Aaronson, “Open Problems Related to Quantum Query Complexity,” ACM Transactions on Quantum Computing 2, Article 14 (2021).DOIarXiv
[CCG23]
Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani, “Quantum Algorithms and the Power of Forgetting,” in 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), LIPIcs 251, 37:1–37:22 (2023).DOIarXiv
[LZ25]
Jianqiang Li and Sebastian Zur, “Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems,” Quantum 9, 1733 (2025).DOIarXiv

Page edit log

  • Record created
  • Last edited
  • Revisions2

View the full history on GitHub

Your contribution is welcome!

Found progress, a correction, or a resolution? Edit this record on GitHub and open a pull request, or report an update with the primary sources. The proposal page explains the available submission route; see the contribution guide for details.

Cite this page

“Quantum query complexity of Welded Tree path-finding,” Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo), ID op_17bba2d8f41697f6, accessed 2026-09-09.

Use the Cite button above for BibTeX and the permanent link.

Cite this problem

Please also cite the primary sources listed under References. Cite this page for the statement, status, and stable identifier.

BibTeX

@incollection{qiqcop_op_17bba2d8f41697f6,
  title = {Quantum query complexity of Welded Tree path-finding},
  booktitle = {Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo)},
  year = {2026},
  howpublished = {\url{https://qiqc-op.com/problem/op_17bba2d8f41697f6/}},
  note = {Stable ID op_17bba2d8f41697f6; status: Unsolved; accessed 2026-09-09}
}

Plain text

“Quantum query complexity of Welded Tree path-finding,” Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo), https://qiqc-op.com/problem/op_17bba2d8f41697f6/, ID op_17bba2d8f41697f6, accessed 2026-09-09.

Share this problem

Permanent link

Identifiers

op_17bba2d8f41697f6
01M21QD4KR3RBCKD1WEK2XSD4K