Imagine you're blindfolded in a hedge maze. You can feel your way from entrance to exit—maybe even do it quickly if you can somehow split yourself into many copies exploring all branches simultaneously. But the moment someone asks you to describe the route you took, turn by turn, you go blank. The act of writing down directions collapses the very trick that let you move fast. That is the welded tree problem, and this paper proves the map-drawing failure isn't a bug in current algorithms—it's a theorem. The committed claim: any quantum algorithm requires Ω(2^{n/12}) queries to find a path between the roots of a height-n welded tree graph. This is exponential in n, meaning path-finding is provably intractable for quantum computers on this problem, even though quantum walks can reach the destination in polynomial time. The result is a clean separation: quantum can solve a decision problem ("does a path exist? what's at the other root?") exponentially faster than classical, but the search problem ("show me the path") is hard for both. The welded tree graph is constructed by taking two perfect binary trees of height n and connecting their leaves through a random matching—the "weld." A quantum walk on this structure exhibits constructive interference that funnels amplitude from one root to the other in poly(n) steps. Classical algorithms, by contrast, get lost in the exponentially many leaves. The key insight from prior work (Childs et al., 2003) was that recording which edges you traverse destroys the interference pattern. This paper upgrades that intuition from "known algorithms fail" to "all algorithms must fail." The proof machinery is where the real contribution lives. The authors introduce compressed permutation oracles—a bookkeeping device that tracks what a quantum algorithm has learned about the graph without storing the full adjacency structure. They show that the compressed database remains "path-free" (contains no root-to-root path information) up to a small error that they control across all queries. Each query can only increment the algorithm's progress by a bounded amount, and accumulating enough progress to find a path requires exponentially many queries. The technique generalizes Zhandry's compressed oracle framework from random functions to random permutations, which is a nontrivial extension with independent value. For the ladder: the upper bound for quantum traversal (reaching the opposite root) is O(n) queries via quantum walk. The classical lower bound for even traversal is 2^{Ω(n)}. This paper now establishes that quantum path-finding requires 2^{Ω(n/12)} queries. The constant in the exponent (n/12 vs. n) leaves room for tightening—the authors note this gap explicitly—but the exponential nature of the bound is the load-bearing result. No prior work had any super-polynomial lower bound for quantum path-finding on welded trees. The integrity story is strong for a theory paper: this is a mathematical proof, not a simulation or experiment. The validation is the proof itself, checked against the compressed oracle formalism. There is no benchmark gaming or cherry-picking possible—either the proof holds or it doesn't. The result applies to the independently matched welded tree model (where the weld is a uniformly random perfect matching), which is the standard model in the literature. The broader significance is conceptual. This is one of the cleanest demonstrations that quantum speedup can be fundamentally non-extractable—you can benefit from the computation's result without being able to explain how you got there. This has implications for quantum complexity theory (the relationship between decision and search problems), quantum cryptography (the welded tree structure has been proposed for cryptographic applications), and our basic understanding of what quantum advantage means in practice. When someone says "quantum computers explore exponentially many possibilities simultaneously," this paper shows exactly how that metaphor breaks: they explore, but they cannot report the route.
