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:2605.11228

Quantum Algorithm for Identifying Hidden Graphs: Spectral Theory and Numerical Evidence

Pawel Wocjan

quant-phSubmitted May 11, 2026• Announced May 13, 2026• 0 citations
arXivHTMLPDF

Abstract

We give a quantum algorithm for a novel type of black-box problem: identifying a hidden $d$-regular base graph $G$ on $n$ vertices from oracle access to an obfuscated version of it, rather than traversing it. From $G$ we build the spired graph $G_{\rm spire}$ in three steps: each vertex is lifted into an exponentially large cluster, with adjacent clusters joined by a random bipartite graph; each cluster is then crowned with a balanced spire; finally, all vertices are randomly relabelled. Specializing to $G=K_2$ recovers the welded-trees graph. Our algorithm is conceptually simple: a continuous-time quantum walk on $G_{\rm spire}$, followed by a single Hadamard test at a classically precomputed time $t^*$; the algorithm returns the candidate whose predicted amplitude is closest to the measurement. The design rests on a rigorous spectral theory: from the apex of any spire, the walk is confined to a polynomial-dimensional invariant subspace evolving under the adjacency matrix of a simpler towered graph $G_{\rm tower}$; that matrix block-diagonalizes into $n$ independent tridiagonal systems of size $n$, each solved in closed form by a Chebyshev secular equation. Efficient numerics enabled by this decomposition supply $t^*$ and the predicted amplitudes. On the prism graphs $Y_m$ versus the Möbius ladders $M_m$ (each on $n=2m$ vertices), the numerical study supports a precise conjecture that $\widetilde O(n^2/\log n)$ measurements at evolution time of order $m^2$ suffice to distinguish the two families; we have tested $4 \le m \le 5121$ ($n$ up to $10242$). By analogy with the welded-trees lower bounds, we further conjecture that any classical algorithm requires queries exponential in $n$. Together these conjectures point to an exponential quantum speedup for the identification of an obfuscated base graph.

Related papers

Quantum Algorithms and the Power of Forgetting

Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani

The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find another distinguished EXIT vertex using polynomially many queries, though without finding any particular path from ENTRANCE to EXIT. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the ENTRANCE, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation.

arXiv:2211.12447•Leibniz international proceedings in informatics•Nov 22, 2022•5 citations

Hardness of Pathfinding in a Welded Tree

David Miloschewsky, Supartha Podder

Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.

quant-pharXiv:2609.20651•Sep 18, 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

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

Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem

Cheng Xin

The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$, finds and verifies a homogeneous $K$-set using $O\!\left(2^K K\log\frac Kη\right)$ edge queries with failure probability at most $η$. At the Ramsey scale $N=2^n$, this yields a homogeneous set of order $\lfloor n/2\rfloor+1$ using $O(\sqrt N\log N\log(\log N/η))$ queries, improving on the $O(N)$ queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an $Ω(N^{1/12})$ quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an $Ω(N^{1-1/\sqrt2})$ randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution $G(N,1/2)$. On that distribution a greedy quantum search uses only $\widetilde O(N^{1/4})$ queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.

quant-pharXiv:2609.05812•Sep 8, 2026•0 citations

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
We give a quantum algorithm for a novel type of black-box problem: identifying a hidden ddd-regular base graph GGG on nnn vertices from oracle access to an obfuscated version of it, rather than traversing it. From GGG we build the spired graph GspireG_{\rm spire}Gspire​ in three steps: each vertex is lifted into an exponentially large cluster, with adjacent clusters joined by a random bipartite graph; each cluster is then crowned with a balanced spire; finally, all vertices are randomly relabelled. Specializing to G=K2G=K_2G=K2​ recovers the welded-trees graph.
Our algorithm is conceptually simple: a continuous-time quantum walk on GspireG_{\rm spire}Gspire​, followed by a single Hadamard test at a classically precomputed time t∗t^*t∗; the algorithm returns the candidate whose predicted amplitude is closest to the measurement. The design rests on a rigorous spectral theory: from the apex of any spire, the walk is confined to a polynomial-dimensional invariant subspace evolving under the adjacency matrix of a simpler towered graph GtowerG_{\rm tower}Gtower​; that matrix block-diagonalizes into nnn independent tridiagonal systems of size nnn, each solved in closed form by a Chebyshev secular equation. Efficient numerics enabled by this decomposition supply t∗t^*t∗ and the predicted amplitudes.
On the prism graphs YmY_mYm​ versus the Möbius ladders MmM_mMm​ (each on n=2mn=2mn=2m vertices), the numerical study supports a precise conjecture that O~(n2/log⁡n)\widetilde O(n^2/\log n)O(n2/logn) measurements at evolution time of order m2m^2m2 suffice to distinguish the two families; we have tested 4≤m≤51214 \le m \le 51214≤m≤5121 (nnn up to 102421024210242). By analogy with the welded-trees lower bounds, we further conjecture that any classical algorithm requires queries exponential in nnn. Together these conjectures point to an exponential quantum speedup for the identification of an obfuscated base graph.
The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find another distinguished EXIT vertex using polynomially many queries, though without finding any particular path from ENTRANCE to EXIT. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the ENTRANCE, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation.
Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height nnn, any quantum query algorithm requires at least Ω(2n/24)Ω(2^{n/24})Ω(2n/24) queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.
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.
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.
The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an NNN-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every K≥2K\ge2K≥2 and N≥4K−1N\ge4^{K-1}N≥4K−1, finds and verifies a homogeneous KKK-set using O ⁣(2KKlog⁡Kη)O\!\left(2^K K\log\frac Kη\right)O(2KKlogηK​) edge queries with failure probability at most ηηη. At the Ramsey scale N=2nN=2^nN=2n, this yields a homogeneous set of order ⌊n/2⌋+1\lfloor n/2\rfloor+1⌊n/2⌋+1 using O(Nlog⁡Nlog⁡(log⁡N/η))O(\sqrt N\log N\log(\log N/η))O(N​logNlog(logN/η)) queries, improving on the O(N)O(N)O(N) queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an Ω(N1/12)Ω(N^{1/12})Ω(N1/12) quantum lower bound by a reduction from collision finding. The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an Ω(N1−1/2)Ω(N^{1-1/\sqrt2})Ω(N1−1/2​) randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution G(N,1/2)G(N,1/2)G(N,1/2). On that distribution a greedy quantum search uses only O~(N1/4)\widetilde O(N^{1/4})O(N1/4) queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.
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.