Quantum query complexity of Welded Tree path-finding

Unsolved ID op_17bba2d8f41697f6 Last edited 8 October 2026
Edit

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

Reports do not certify correctness or automatically change the problem's status. Progress policy.

  • 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].

  • In a September 2026 preprint, Miloschewsky and Podder report an exponential quantum-query lower bound for unrestricted algorithms on a colored welded-tree distribution. Theorems 1.2 and 4.1 give success probability \(O(q^6/N^{1/4})\) for \(1\leq q\leq\sqrt N/100\), where \(N=2^n\) and \(n\geq16\) is even, implying \(\Omega(2^{n/24})\) queries for constant success probability. Their three-color neighbor oracle samples cycles compatible with fixed edge colorings, conditioned on forming a single cycle; the discussion after Theorem 1.2 explicitly distinguishes this from a uniformly random alternating cycle. This resolves the unrestricted path-finding lower-bound question for their colored distribution, rather than only for genuine rooted algorithms, but does not establish the lower bound for the exact distribution in this record [MP26].

  • In independent concurrent work, Carolan, Childs, Coudron, and Gilani report an exponential lower bound for general quantum algorithms on independently matched welded trees. Definition 3.1 and Sec. 3.2 specify three independent uniform bijections, one per edge color, between the eligible left and right leaves whose tree-edge color differs from that color; parallel weld edges of different colors are allowed. For trees of even depth \(n\), formal Theorem 4.3 gives the constant-success lower bound \(\Omega(2^{n/12}/(n+2)^{2/3})=2^{\Omega(n)}\). The abstract and informal Theorem 1.1 state the exponential scale as \(\Omega(2^{n/12})\) without this polynomial factor. The algorithms need not retain paths to queried vertices or restrict queries to previously obtained labels. In the introduction, the authors state that adapting their argument to the original random-cycle distribution is straightforward, but leave the details for future work. This resolves the unrestricted lower-bound question for their independently matched ensemble; the cited version does not supply the lower bound for the exact uniform alternating-cycle distribution specified above [CCCG26].

  • Reported progress: PR #78.

Comment

The September 2026 preprints report unrestricted exponential quantum-query lower bounds for two closely related welded-tree ensembles: Miloschewsky and Podder’s fixed-coloring-compatible single-cycle distribution and Carolan, Childs, Coudron, and Gilani’s independently matched distribution. These results settle the central unrestricted path-finding lower-bound question in those models, without the earlier genuine-rooted restrictions [MP26][CCCG26]. What remains unresolved in this record is the exponential lower bound in (2) for the exact uniform alternating-cycle distribution specified in the statement, or an algorithm refuting it. Carolan et al. describe a transfer to the original distribution as straightforward, but do not supply its details in the cited version. The record retains Unsolved for this precise distributional question.

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
[MP26]
David Miloschewsky and Supartha Podder, “Hardness of Pathfinding in a Welded Tree,” arXiv preprint, version 1 (17 September 2026).arXiv
[CCCG26]
Joseph Carolan, Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani, “A quantum lower bound for path finding in welded trees,” arXiv preprint, version 1 (22 September 2026).arXiv

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-11-06}
}

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-11-06.

Share this problem

Permanent link

Identifiers

op_17bba2d8f41697f6
01M21QD4KR3RBCKD1WEK2XSD4K