MNRS Quantum Walk Search¶

Category C1 · Module oracq.algorithms.input_model.graph_walks · Stage V3

Overview¶

A quantum-walk skeleton for marked-vertex search: setup prepares the initial state \(\frac{1}{\sqrt N}\sum_v A|v\rangle\), followed by iterating Repeat{ walk; marked phase flip }. The implementation basis is Magniez–Nayak–Roland–Santha 2011 (Search via quantum walk; hitting time and step scaling, cited in the module docstring): the step count takes the scaling \(\lceil \frac{\pi}{4}\sqrt{H_{\text{avg}}}\rceil\) of the average hitting time \(H_{\text{avg}}\) of the classical random walk; on the complete graph \(H_{\text{avg}} = N/|M|\), and the step count recovers the Grover scaling \(\frac{\pi}{4}\sqrt{N/|M|}\).

Interface and input model¶

quantum_walk_search(setup, walk, marked, steps, *, name=None)
transition_matrix(neighbors)
hitting_times(transition, marked)
suggest_steps(transition, marked)

API entries: quantum_walk_search, transition_matrix, hitting_times, suggest_steps

setup: the initial-state preparation; it must satisfy the StatePreparation protocol (e.g. the output of szegedy_setup from Szegedy Walk).
walk: a walk-step handle whose registers map, in declaration order, onto contiguous slices of setup.target; it may be an open declaration.
marked: a phase oracle acting on the first few bits of the walk space (target[, work] interface, constructed by phase_marks(width, marked)); for szegedy_walk it acts precisely on the current register.
steps: a non-negative iteration count, which may be chosen with reference to suggest_steps.
All three handles may be open declarations; the generated program is executed after implementations are bound in batches via bind. The overall input model is FO: the graph is given through an Adjacency Oracle, and the marked set through a phase oracle.

quantum_walk_search returns an Operation with registers target: Bits(width) (width is the total walk-space width) and work: Bits(prep.work_width + marked_work). Attributes:

Attribute	Meaning
`algorithm`	`"quantum_walk_search"`
`framework`	`"MNRS"`
`steps` / `walk_width`	iteration count and walk-space width

Classical-side tools: transition_matrix derives \(P[v][u] = |\{j: N(v,j) = u\}| / D\) from the neighbor table; hitting_times solves the linear system \((I - P_{\text{free}})h = \mathbf{1}\) to give the expected number of steps for each vertex to first reach the marked set (0 for marked vertices; raises ValidationError when unreachable); suggest_steps returns \(\max(1, \lceil \frac{\pi}{4}\sqrt{H_{\text{avg}}}\rceil)\), or 0 when the whole graph is marked.

Implementation notes¶

The generated structure is a setup call followed by one Repeat(steps) loop: the loop body first maps the walk step’s registers, in declaration order, onto contiguous slices of target and invokes it, then applies the marked phase flip to the first marked_width bits of target. Width consistency is validated at generation time (the total walk width equals the setup width, marked does not exceed the walk space, steps is non-negative); violations raise ValidationError.

Applicability boundary: the step count is supplied by the caller, and suggest_steps is only a reference — it is a function of the classical hitting time and is unaware of the quantum spectrum; on even cycles (alternating edge-coloring tables) this skeleton does not amplify, see the known gaps section.

Validation approach¶

Category C1 (exact discrete semantics; acceptance criteria in ../../development/validation-plan.md §2): the output distribution must cross-check against an exact construction. Evidence:

Structure: tests/core/test_graph_walks.py:QuantumWalkSearchTests / HittingTimeTests; test_search_rejects_mismatched_handles covers generation-time violations such as negative steps and mismatched setup widths.
Numerical: QuantumWalkSearchTests.test_search_amplifies_marked_vertex_on_hypercube — Q3 hypercube, marked {0}, suggest_steps gives 3 steps: the baseline (0 steps) has marked probability 0.125, and 3 steps give 0.78125 (places = 9); test_search_recovers_grover_limit_on_complete_graph — on the K4 complete graph the probability is exactly 1.0 after 2 steps (places = 10); HittingTimeTests.test_cycle_hitting_times_match_closed_form — the hitting times of every vertex on an 8-cycle cross-check pointwise against the closed form \(h_k = d(8-d)\), \(d = \min(k, 8-k)\) (places = 9); test_suggest_steps_matches_grover_scaling and test_all_marked_needs_no_steps validate the step-count formulas.
Binding: QuantumWalkSearchTests.test_abstract_handles_bind_to_gate_implementations — both the adjacency oracle and the marked oracle are open declarations (unresolved for {G, M}); after binding gate implementations, the marked probability matches direct generation (0.78125, places = 9); test_walk_handle_may_stay_abstract witnesses that the setup/walk handles can likewise stay bound later.

Known gaps and planned stages¶

Consistent with the validation matrix: the element distinctness witness on Johnson graphs is pending, stage V3. Another confirmed fact: on even cycles (alternating edge-coloring neighbor tables) the marked probability stays at the uniform baseline \(1/N\) and does not amplify with the step count (reference simulations rechecked several step counts on the 8-cycle, all 0.125); this has been confirmed as a theoretical result rather than an implementation defect (validation-plan.md §3 records this position); witnesses of amplifiable behavior are carried by the hypercube and complete-graph instances.

Numerical validation¶

Experiment design: three end-to-end search instances, with the step count chosen from an independent Markov-chain reference (hitting times \(H_{\rm avg}\) solved via (I-P_free)h=1) as \(\lceil\frac{\pi}{4}\sqrt{H_{\rm avg}}\rceil\); the final states are compared in full amplitude against the MNRS iteration \((M W)^s|\psi_0\rangle\) assembled independently in numpy (the walk-space reflection operators are constructed directly from the neighbor table, without reusing the tested module).

Complete graph K4 (self-loops padding to \(D=4\), neighbor table \(N(v,j)=j\)), marked \(=\{0\}\): \(H_{\rm avg}=4\), 2 steps, four paths (reference, rir-pysparq, adapter-pysparq, originir-ext).
Hypercube Q3 (\(N=8, D=4\)), marked \(=\{0\}\): \(H_{\rm avg}\approx11.048\), 3 steps, four paths.
K4 with QRAM binding (qram_adjacency + memory table): OriginIR-ext circuits carry no QRAM resources, so this instance runs only the reference and rir-pysparq paths.

Case	Scale	Paths	Metric	Value
mnrs-search-complete-k4	N=4, D=4, steps=2	4 paths	marked probability / max final-state error	0.578125 / 6.3e-16
mnrs-search-hypercube-q3	N=8, D=4, steps=3	4 paths	marked probability / max final-state error	0.78125 / 1.2e-15
mnrs-search-qram-k4	N=4, D=4, steps=2	reference, rir-pysparq	marked probability / max final-state error	0.578125 / 6.3e-16

Informative metrics: \(\text{steps}/\sqrt{H_{\rm avg}}=1.0\) for K4 and 0.903 for the hypercube, the same order of magnitude as \(\pi/4\approx0.785\), consistent with the MNRS \(\sqrt{H}\) scaling; the marked probability 0.578125 of the K4 instance corresponds to the exact walk dynamics under the \(N(v,j)=j\) edge labeling (the transition matrix is the same as, but the walk different from, the 1.0 instance with cyclic edge labeling in the core unit tests; each agrees amplitude by amplitude with its independent reference).

Reproduction command:

PYTHONPATH=src /home/agony/projects/qcfd-dev/quantum-cfd-software/.venv/bin/python tests/verification/verify_search_walks.py

Artifacts: out/verification/search_walks.json (cases mnrs-search-complete-k4, mnrs-search-hypercube-q3, mnrs-search-qram-k4, plus the classical-reference routine cross-check case markov-chain-helpers).