MNRS finite reversible-walk finding

This is the finite-generation and execution procedure OP2 in research/quantum-algorithms-planning/operational-contracts.md, section “OP2 — MNRS approximate reflection and finite tolerant recursive finding”, transcribed with its declared constants and charged branches.

Input. A finite ergodic reversible row chain $(X,P,\pi )$ with ${\pi }_x>0$, a supplied positive dyadic rational lower absolute-gap bound ${\delta }_0$, a dyadic rational marked-mass lower bound ${\epsilon }_0>0$ with promise $\pi (\mathcal{M})=0$ or $\pi (\mathcal{M})\ge {\epsilon }_0$, a coherent marked-bit check of cost $C$, and a dyadic rational failure target $\rho \in (0,1)$. These finite parameter encodings suffice for real positive promises: choose dyadic lower bounds within a factor of two of the gap and nonzero marked-mass bounds, and a dyadic target in $({\rho }_{\ast }\mathrm{/}2,{\rho }_{\ast }]$ for desired failure probability ${\rho }_{\ast }$. Write $\mathrm{\mid }\sqrt{\pi }⟩={\sum }_{x\in X}\sqrt{{\pi }_x}\mathrm{\mid }x⟩$ and let $T\mathrm{\mid }x⟩=\mathrm{\mid }x⟩{\sum }_y\sqrt{P_{xy}}\mathrm{\mid }y⟩$ be the row isometry of Szegedy row-preparation map and discriminant. The supplied clean preparation $A_{\pi }$ maps its specified blank input to the stationary edge state $\mathrm{\mid }{\pi }_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}⟩=T\mathrm{\mid }\sqrt{\pi }⟩={\sum }_{x\in X}\sqrt{{\pi }_x}\mathrm{\mid }x⟩{\sum }_{y\in X}\sqrt{P_{xy}}\mathrm{\mid }y⟩,$ returns all its work registers to their specified blank states, and has charged cost $S$. The row-access interface of Finite row-preparation access model for a Szegedy walk supplies the row-preparation unitary $V_P$, its inverse, controlled forward and inverse calls, the clean-state reflection $R_0$ and its controlled call, and the swap $S$ and its controlled call. On the clean-work logical walk space these implement $R_A=2T{T}^{\ast }-I=V_P{R}_0{V}_P^{\ast }$, $U=S{R}_A$, and $W=U^2$, with each constituent charged. Supply controlled calls to $W$ and $W^{\ast }$ for the coherent QPE circuits and an exact controlled $R_A$ for the all-zero branch. A single bound $U_0$ covers each controlled $W$ or $W^{\ast }$ call and the controlled $R_A$ call, including their factorwise implementation costs. A matrix $P$ alone supplies none of these circuits.

Marked check and retained-state instrument. Write $m(x)={\mathbf{1}}_{\mathcal{M}}(x)$. The supplied exact coherent check is a unitary $B_{\mathcal{M}}$ with separately supplied inverse and specified fresh flag $F$ and scratch $J$. On the declared logical encoding it satisfies, for every $x\in X$, $b\in \{0,1\}$, and vector $\eta$ of all existing remaining registers, $B_{\mathcal{M}}(\mathrm{\mid }x⟩\mathrm{\mid }\eta ⟩\mathrm{\mid }b{⟩}_F\mathrm{\mid }0{⟩}_J)=\mathrm{\mid }x⟩\mathrm{\mid }\eta ⟩\mathrm{\mid }b\oplus m(x){⟩}_F\mathrm{\mid }0{⟩}_J\mathrm{.}$ Its unitary extension outside the logical encoding is supplied too. Thus it preserves the first label and every existing walk, phase, data, and work auxiliary on clean new scratch. In the relevant query/check cost coordinates, $C$ bounds each forward and inverse check call; declare the flag-readout cost separately and include it in $C$ in any coordinate that counts readout as a check. A flag readout uses no value-oracle query. Gate, output-bit, and new flag/scratch costs are separately priced.

On the whole existing register space set ${\mathrm{\Pi }}_1={\mathrm{\Pi }}_{\mathcal{M}}=({\sum }_{x\in \mathcal{M}}\mathrm{\mid }x⟩⟨x\mathrm{\mid })\otimes I_{\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{t}}$ and ${\mathrm{\Pi }}_0=I-{\mathrm{\Pi }}_{\mathcal{M}}$, with identity on every existing auxiliary, including every retained $K_j$. Every marked/unmarked test below uses the specified Lüders instrument ${\mathcal{I}}_a(Z)={\mathrm{\Pi }}_{a}Z{\mathrm{\Pi }}_a,a\in \{0,1\},$ in the sense of Finite instruments and conditional states: its positive-probability conditional density is ${\mathcal{I}}_a(Z)\mathrm{/}\mathrm{tr}({\mathcal{I}}_a(Z))$; no conditional state is assigned when that trace is zero. Execute the test by appending $\mathrm{\mid }0{⟩}_F\mathrm{\mid }0{⟩}_J$, applying $B_{\mathcal{M}}$, reading only the fresh flag with the explicitly chosen computational-basis Lüders maps $Y\mapsto Q_{a}Y{Q}_a$, where $Q_a=I\otimes \mathrm{\mid }a⟩⟨a{\mathrm{\mid }}_F\otimes I_J$, storing $a$ in the classical output record, and applying $B_{\mathcal{M}}^{\ast }$ to return the fresh flag and scratch to zero. Retain every pre-existing register; on an unmarked result read no finer first-label information. A marked result may then be followed by label readout and verification for output. Charge one forward check, one inverse check, and one flag readout per test, hence $O(C)$ in the stated query/check profile. The recursive marked phase flip is implemented by $B_{\mathcal{M}}$, a phase $-1$ on flag $1$, and $B_{\mathcal{M}}^{\ast }$, also with both calls charged.

Approximate stationary reflection $R(\beta )$. Set $s=\min \{q\ge 1:4^q{\delta }_0\ge 64\}$ and $k=\min \{j\ge 1:2^j\beta \ge 2\}$, using exact integer/rational comparisons. With $Q=2^s$, these comparisons give $Q\ge 8\mathrm{/}\sqrt{{\delta }_0}>2\pi \mathrm{/}\sqrt{{\delta }_0}$ using $\pi <4$ from The Gregory-Leibniz series: pi over four equals 1-1/3+1/5-1/7+.... Append $k$ separate $s$-bit zero phase registers. Coherently execute the finite QPE circuit prefix from Quantum phase estimation on $W$ in each register, using the declared controlled powers. This prefix is a unitary circuit on the full walk register and is executed on arbitrary walk states, including superpositions; the eigenvector input in the QPE analysis is not a restriction on the circuit's action. Do not measure these phase registers. If at least one phase register is nonzero, apply $-I$ to the walk state. If all are zero, apply the exact controlled row-space reflection $R_A=2T{T}^{\ast }-I$ using the charged row-preparation, inverse, and clean-state reflection calls. Reverse the $k$ coherent QPE prefixes in reverse chronological order, using the supplied controlled inverse powers. Charge $2k(2^s-1)$ controlled $W$ and $W^{\ast }$ calls, the controlled $R_A$ branch, all-zero comparisons, phase-register gates, and the allocated classical arithmetic. The all-zero branch is required: $W$ has the extra zero-phase subspace $A^{\perp }\cap B^{\perp }$, where $R_A=-I$, while $R_A=+I$ on the stationary state.

Recursive circuit $A_i$. Let $\gamma =1\mathrm{/}120$, ${\beta }_i=\gamma \mathrm{/}(16i^2)$ for $i\ge 1$, and $A_0=I$. For $i>0$, allocate a fresh $K_i$ for $R({\beta }_i)$ and execute chronologically: (i) $A_{i-1}$, the marked phase flip, and $A_{i-1}^{†}$; (ii) coherently test every older $K_j$, $j<i$, applying $-I$ if any is nonzero and otherwise applying $R({\beta }_i)$ on the walk and fresh $K_i$; compute and uncompute the control predicate; (iii) apply $A_{i-1}$. Each ${\beta }_i$ is rational, and the $k_i$ loop in $R({\beta }_i)$ is an exact rational comparison. An inverse means the exact reversed finite gate list, not a reset of measured work.

Tolerant finding wrapper. If ${\epsilon }_0\ge 1\mathrm{/}2$, take $n_s=\min \{n\ge 1:2^{-n}\le \rho \}$ fresh stationary samples, verify each label, return the first marked label, and output NO MARKED if all fail. Otherwise, let $t_{\max }$ be the least integer $t\ge 0$ such that $3^t\arcsin \sqrt{{\epsilon }_0}\ge \pi \mathrm{/}4$. Determine it by the exact algebraic threshold comparison ${\epsilon }_0\ge {\sin }^2(\pi \mathrm{/}(4\cdot 3^t))$; equality takes the $\ge$ branch. Let $n_{\mathrm{o}\mathrm{u}\mathrm{t}}=\min \{n\ge 1:(19\mathrm{/}20{)}^n\le \rho \}$, found by exact rational comparisons. In each outer trial:

1. Prepare a fresh stationary sample, test its first label, and return it if marked.
2. Prepare a fresh stationary walk state with all $K_1,\dots ,K_{t_{\max }}$ zero.
3. For $i=1,\dots ,t_{\max }$, apply $A_i$, execute the marked/unmarked Lüders test specified above, and on a marked outcome read, verify, and return the label. On an unmarked outcome retain the conditional current state and all auxiliary registers, and continue; do not reprepare or reset them.
4. If no level succeeds, discard the trial and begin the next fresh outer trial.

If all trials fail, output NO MARKED. Every loop has a finite cap; all confidence calculations, comparisons, reversible predicates, retained auxiliary space, state preparation, update, inverse, controlled, reflection, and check costs are charged. In the ${\epsilon }_0\ge 1\mathrm{/}2$ branch, the cap above gives false-negative probability at most $\rho$; in the other branch correctness and the sharper cost are proved separately in Finite reversible-walk finding cost.