Szegedy-walk marked-set detection

Input. A finite symmetric lazy row-stochastic matrix $P$ on nonempty $X$, with uniform stationary law and, when $\mathrm{\mid }X\mathrm{\mid }\ge 2$, real promised lower gap ${\delta }_0\in (0,1]$ satisfying $\delta (P)=1-{\lambda }_2(P)\ge {\delta }_0$; a marked predicate with promise $\mathcal{M}=\mathrm{\varnothing }$ or $\mathrm{\mid }\mathcal{M}\mathrm{\mid }\mathrm{/}\mathrm{\mid }X\mathrm{\mid }\ge {\epsilon }_0$ for real ${\epsilon }_0\in (0,1]$; and a real failure target $\beta \in (0,1)$. Supply an exact two-outcome projective test on the first register with its Lüders instrument and declared cost $C_{\mathrm{m}\mathrm{a}\mathrm{r}\mathrm{k}}$; this cost includes the marked-branch label readout and verification. The finite classical input supplies, for each $z\in \{{\delta }_0,{\epsilon }_0,\beta \}$, a certified dyadic bracket $[z_{-},z_{+}]$ encoded by finite binary numerators and exponents, with $0<z_{-}\le z\le z_{+}\le \min (1,2z_{-})\mathrm{.}$ The bracket containments are input promises; every endpoint bit and all subsequent comparison, precision, and bit-time costs are charged. Such a finite bracket exists for every real parameter in the stated interval. The numerical input model also supplies terminating exact comparisons for rational values and the algebraic real parts of roots of unity used below; it declares and charges their bit-time and description costs. Write $\underset{‾}{\delta }=({\delta }_0{)}_{-}$, $\underset{‾}{\epsilon }=({\epsilon }_0{)}_{-}$, and $\underset{‾}{\beta }={\beta }_{-}$. Also supply a circuit $A_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{f}}$ preparing $\mathrm{\mid }s⟩=\mathrm{\mid }X{\mathrm{\mid }}^{-1\mathrm{/}2}{\sum }_{x\in X}\mathrm{\mid }x⟩$ with its cost and a row-preparation access model for the absorbing chain $P^{\mathrm{\prime }}$ of Discriminant of the marked-state absorbing walk. The model supplies $V_{P^{\mathrm{\prime }}}$, its inverse and controlled forms, the clean-state reflection and its controlled form, and the swap and controlled swap needed for the one-reflection walk; each constituent is separately charged. If $\mathrm{\mid }X\mathrm{\mid }=1$, the procedure measures its sole label with the marked predicate and terminates exactly, without using the gap parameter or walk. Marked-check, preparation, controlled-walk, inverse, gate, precision, comparison, and description-bit costs are separate declared inputs. A matrix alone supplies none of these circuits.

Output. NONEMPTY if a marked label is found or the phase test accepts; otherwise EMPTY. A found label is returned and checked against the supplied predicate.

Instructions.

1. If $\mathrm{\mid }X\mathrm{\mid }=1$, measure its only label, evaluate the supplied predicate and return the exact answer. Otherwise set ${\gamma }_0=\arccos (1-\underset{‾}{\delta }\underset{‾}{\epsilon })$. Start at $m=6$ and increment until the exact comparison $1-\underset{‾}{\delta }\underset{‾}{\epsilon }\le \cos (\pi 2^{5-m}),$ and set $Q=2^m$. Since the compared cosine is the real part of a root of unity, this is a finite exact algebraic comparison; it is equivalent to $m=\lceil {\log }_2(32\pi \mathrm{/}{\gamma }_0)\rceil$. Start at $k=1$ and increment until the exact rational comparison $6^k\underset{‾}{\beta }\ge 1$ holds, equivalently $k=\lceil \ln (1\mathrm{/}\underset{‾}{\beta })\mathrm{/}\ln 6\rceil$. Both loops terminate because $\underset{‾}{\delta }\underset{‾}{\epsilon }>0$ and $\underset{‾}{\beta }>0$. All comparisons and their bit costs are part of the declared input cost model.
2. Repeat the following fresh-state run $k$ times, stopping early if NONEMPTY is returned.
3. Prepare $\mathrm{\mid }s⟩$ with $A_{\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{f}}$ and apply the supplied row preparation $V_{P^{\mathrm{\prime }}}$ to obtain the two-register row state. On the first register, use the supplied two-outcome projective measurement with ${\mathrm{\Pi }}_1={\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 }}_1$, with Lüders branch maps $Z\mapsto {\mathrm{\Pi }}_{a}Z{\mathrm{\Pi }}_a$. These maps form a valid instrument: the projections are non-negative, sum to identity, and equal their own non-negative square roots, so The square-root Lüders maps form an instrument applies. If outcome $1$ occurs, measure the first register in its computational basis, verify the resulting label $x\in \mathcal{M}$, and output NONEMPTY and $x$ immediately. If outcome $0$ occurs with positive probability, continue with its normalized projected state; this preserves coherence among all unmarked labels. Outcome $0$ is impossible when $\mathcal{M}=X$, so no conditional state is needed there.
4. On the unmarked branch, apply the coherent QPE circuit prefix from Quantum phase estimation to the conditioned two-register state for the one-reflection walk $U^{\mathrm{\prime }}=S(2T^{\mathrm{\prime }}{T}^{\mathrm{\prime }\ast }-I)$, where $T^{\mathrm{\prime }}$ is the row-preparation map for $P^{\mathrm{\prime }}$. The QPE prefix is a finite unitary circuit and acts on this arbitrary conditioned superposition; its eigenvector input in the outcome analysis does not restrict the circuit's input domain. Measure the phase register only after the controlled-power and inverse-QFT circuit has run. Use supplied controlled powers if available; otherwise implement each controlled $U^{\mathrm{\prime }{2}^j}$ by $2^j$ sequential controlled one-step $U^{\mathrm{\prime }}$ calls. The factorwise controlled call charges controlled $V_{P^{\mathrm{\prime }}}^{†}$, controlled $V_{P^{\mathrm{\prime }}}$, the controlled clean-state reflection, and controlled swap. No controlled inverse of $U^{\mathrm{\prime }}$ is used.
5. For the measured integer $y\in \{0,\dots ,Q-1\}$, compute $d(y)=\min (y\mathrm{/}Q,1-y\mathrm{/}Q)$ using exact rational arithmetic. Since $0<\underset{‾}{\delta }\underset{‾}{\epsilon }\le 1$, the principal inverse-cosine convention and cosine monotonicity give $0<{\gamma }_0\le \pi \mathrm{/}2$. Return NONEMPTY exactly when $d(y)>{\gamma }_0\mathrm{/}(4\pi )$; equality takes the EMPTY branch. This strict comparison is finite: if $d(y)>1\mathrm{/}8$ accept, and if $d(y)\le 1\mathrm{/}8$ compare the algebraic numbers $\cos (4\pi d(y))$ and $1-\underset{‾}{\delta }\underset{‾}{\epsilon }$, accepting exactly when the former is strictly smaller. Here $4\pi d(y)$ is a rational multiple of $\pi$, so its cosine is the real part of a root of unity; monotonicity of cosine on $[0,\pi ]$ gives the stated comparison. Charge the exact comparison and all phase-register/inverse-QFT gates.
6. If all $k$ fresh runs fail to return NONEMPTY, output EMPTY. A run uses one marked check, the supplied uniform-state and one row-preparation costs, one $m$-bit QPE, and its explicitly charged controlled-walk calls. With only one-step controlled access, QPE uses exactly $Q-1$ controlled $U^{\mathrm{\prime }}$ calls. Gate synthesis, bracket-description bits, exact comparison arithmetic, and classical threshold bits are additional charged costs.