Quantum transport through glued binary trees

The graph that matters

Two complete binary trees of depth n. Their leaves are connected by one random alternating cycle (purple), not merged. All vertices have degree 3 except the entrance and exit, which have degree 2. The drawing reveals structure for explanation; the neighbor-query solver receives only opaque random vertex names.

Click a vertex to inspect its hidden name and neighbor names.

How the walk works

1. Prepare the entrance. There is no coin register and no global Grover route oracle. The graph adjacency defines H=γA, with γ=1/√2 per edge.
2. Evolve coherently. ψ(t)=exp(−iHt)ψ(0). Each amplitude's derivative is −iγ times the sum of neighboring amplitudes. Phase differences create interference.
3. Use symmetry to inspect it. A column state is the equal-amplitude sum over all vertices at that level, normalized by √(column size). Couplings between columns are 1, except √2 across the weld. Equal amplitudes per vertex remain equal in a column even though the weld is random.
4. Choose time before measuring. Reset, choose t uniformly from [0,T] where T=4(n+1), then measure once. The main success statistic is the analytic average probability of observing the exit. A failed attempt may be repeated. This short transport window is an experiment, not the conservative polynomial-time bound from the theorem.
5. Classical comparison. A continuous-time random walker jumps along each incident edge at rate γ. At each column, aggregate all probability mass. On the exit side there are twice as many edges leading back toward the weld as toward the exit, so classical transport is biased away from the exit.

On the hidden graph, the quantum dynamics do not need to know which vertex belongs to which column: the symmetry emerges from the evolution. Our CPU model uses the column assignment as an analyst's shortcut. That assignment is not supplied to an algorithm in the oracle theorem.

The exit is not absorbing. Curves show probability at the exit at a single final measurement time, not “ever reached the exit.” Moving the slider inspects independent experiments; it does not measure the walker along the way. Finding the exit name also does not return a route.

Inspect amplitude and interference

The probability of an individual vertex is column probability divided by column size. The local derivative explains amplitude flow; amplitude itself can be complex. Probability is |a|², not a.

Exit probability at each final time

Blue: quantum; orange: classical. The grid maximum is descriptive only. The reported protocol chooses time uniformly and does not choose the best-looking time.

Depth sweep: the widening transport gap

All requested depths are reported. The quantum average is an analytic time integral; the classical average uses a positive Poisson expansion, retaining tiny probabilities without subtracting nearly equal numbers. No seed or peak-time selection is used to improve these values.

Expected model time, logarithmic scale: blue = repeated quantum uniform-time attempts T/(2p), orange = classical random walk mean first-passage time. Both use the same γ. Quantum repeats assume free reset and exit verification; neither curve is hardware runtime or the optimal classical algorithm's query complexity. At small depths the quantum protocol may cost more.

The exponential separation against all classical algorithms is a theorem about hidden random names and local neighbor access, not a conclusion drawn from these two curves. Revealing columns makes this family easy to simulate classically too. BFS with the full graph is not the same input model as a hidden oracle.

Independent full-graph checks

B maps normalized columns to full-vertex amplitudes. Full-graph spectral evolution is compared with SDK column-circuit output at five times. The neighbor-query BFS identifies the other degree-2 vertex without receiving its name or tree coordinates. Testing this one classical strategy is not a classical lower-bound proof.

Actual SDK circuit and CPU costs

Column-to-energy basis change, energy-dependent phase evolution, and inverse basis change. Three logical operations on the reduced register; no hardware-native gate count or coherent graph-oracle implementation is claimed.

Research context

Childs, Cleve, Deotto, Farhi, Gutmann and Spielman, STOC 2003: Exponential algorithmic speedup by quantum walk. Sections II and III distinguish the simple leaf-identified graph from the random-cycle construction and derive its column Hamiltonian. Section IV gives the classical oracle lower bound.

This is a transport reproduction and explanation. It does not run on a QPU, materialize the large graphs, implement the hidden-name coherent oracle, or independently prove the theorem.