Finite reversible-walk finding cost

By [F2], the stationary eigenvalue $1$ is simple and every other eigenvalue of the reversible transition operator has $\mathrm{\mid }\lambda \mathrm{\mid }\le 1-{\delta }_{\mathrm{a}\mathrm{c}\mathrm{t}}\le 1-{\delta }_0$. By [F20], the discriminant is similar to this transition operator and has the same eigenvalues; the stationary eigenvector corresponds to $\sqrt{\pi }$. In the two-reflection Szegedy walk, the circular phase distance of a nonstationary signal eigenvalue is $d_{\mathbb{T}}(\arccos (\lambda )\mathrm{/}\pi )=\arccos (\mathrm{\mid }\lambda \mathrm{\mid })\mathrm{/}\pi$. For $t=\arccos (1-{\delta }_0)\in [0,\pi \mathrm{/}2]$, [F14] and [F15] give ${\delta }_0=1-\cos t=2{\sin }^2(t\mathrm{/}2)\le t^2\mathrm{/}2$, so $t\ge \sqrt{2{\delta }_0}$. Thus every nonstationary signal phase has circular distance at least $\sqrt{2{\delta }_0}\mathrm{/}\pi$. The only additional zero-phase subspace is the walk-space orthogonal complement in [F3], on which the exact row-space reflection $R_A$ equals $-I$; on the stationary vector it equals $+I$.

In $R(\beta )$, the QPE scale satisfies $Q=2^s\ge 8\mathrm{/}\sqrt{{\delta }_0}>2\pi \mathrm{/}\sqrt{{\delta }_0}$ by the algorithm's exact integer test and $\pi <4$ from [F11]. On the stationary phase $0$, [F7] returns outcome $0$ in every register, so the all-zero branch applies $R_A=+I$ and uncomputes; the stationary state is fixed exactly. For a nonzero signal phase at circular distance $d\ge \sqrt{{\delta }_0}\mathrm{/}\pi$, the outcome-kernel [F5] and the geometric sum [F6] give $\mathrm{Pr}(y=0)\le \frac{1}{4Q^2{d}^2}<\frac{1}{16}$. The first inequality follows because $\mathrm{\mid }1-\exp (2\pi i\theta )\mathrm{\mid }=2\sin (\pi d)\ge 4d$ and $\mathrm{\mid }1-\exp (2\pi iQ\theta )\mathrm{\mid }\le 2$. Repeating QPE coherently in $k=\min \{j\ge 1:2^j\beta \ge 2\}$ fresh phase registers makes the all-zero branch norm at most $4^{-k}$. On a nonzero signal eigenvector, the actual reflection differs from the ideal $-I$ only on that branch, where it applies $R_A$; before QPE uncomputation the difference is $(R_A+I)$ on the all-zero component. By [F20], $R_A=2{\mathrm{\Pi }}_A-I$ for the orthogonal projection ${\mathrm{\Pi }}_A=T{T}^{\ast }$, so $R_A+I=2{\mathrm{\Pi }}_A$ and orthogonal decomposition gives $\mathrm{\parallel }{\mathrm{\Pi }}_{A}w\mathrm{\parallel }\le \mathrm{\parallel }w\mathrm{\parallel }$; hence the coherent state error is at most $2\cdot 4^{-k}\le 2^{1-k}\le \beta$. Reversing the QPE prefixes is unitary and preserves this norm bound. For each nonzero eigenphase, the $k$ QPE circuits use fresh registers and leave the walker eigenvector unchanged, so the joint all-zero probability is the product of the single-register bounds and is at most ${16}^{-k}$. For a superposition of eigenspaces, the joint all-zero branch is still block-diagonal in the orthogonal eigenspaces; expanding its squared norm gives the eigenspace-weighted average of these joint probabilities (the same orthogonal calculation as [F8]). Its branch norm is therefore at most $4^{-k}$ times the input norm, and the same estimate applies. On $A^{\perp }\cap B^{\perp }$, the phase is exactly zero and $R_A=-I$, so the algorithm also agrees exactly with the ideal reflection there. Thus the bound is a coherent state-vector bound, not just an outcome-probability statement.

The projectors ${\mathrm{\Pi }}_0,{\mathrm{\Pi }}_1$ of the algorithm are self-adjoint idempotents summing to identity. For each $a$, $⟨{\mathrm{\Pi }}_{a}v,v⟩=\mathrm{\parallel }{\mathrm{\Pi }}_{a}v{\mathrm{\parallel }}^2\ge 0$, so they form a POVM by [F21]; each ${\mathrm{\Pi }}_a$ is its own nonnegative square root. The square-root-instrument theorem in [F21] therefore proves that the selected maps $Z\mapsto {\mathrm{\Pi }}_{a}Z{\mathrm{\Pi }}_a$ are a finite instrument, and its projective conditional-state theorem applies on positive-probability branches. For a unit vector $\psi$ of the whole existing register space, the algorithm's clean check sends $\psi \mathrm{\mid }0{⟩}_F\mathrm{\mid }0{⟩}_J$ to ${\sum }_{a=0}^1({\mathrm{\Pi }}_a\psi )\mathrm{\mid }a{⟩}_F\mathrm{\mid }0{⟩}_J$. The specified computational Lüders readout of the fresh flag selects precisely $({\mathrm{\Pi }}_a\psi )\mathrm{\mid }a{⟩}_F\mathrm{\mid }0{⟩}_J$; after recording $a$, the inverse check maps this vector to $({\mathrm{\Pi }}_a\psi )\mathrm{\mid }0{⟩}_F\mathrm{\mid }0{⟩}_J$. The resulting branch on the original registers is thus exactly ${\mathrm{\Pi }}_a\mathrm{\mid }\psi ⟩⟨\psi \mathrm{\mid }{\mathrm{\Pi }}_a=\mathrm{\mid }{\mathrm{\Pi }}_a\psi ⟩⟨{\mathrm{\Pi }}_a\psi \mathrm{\mid }$. Its coordinate trace is ${\sum }_j\mathrm{\mid }({\mathrm{\Pi }}_a\psi {)}_j{\mathrm{\mid }}^2=\mathrm{\parallel }{\mathrm{\Pi }}_a\psi {\mathrm{\parallel }}^2=p_a$ by [F16] and [F21]. If $p_a>0$, division gives the pure conditional vector ${\mathrm{\Pi }}_a\psi \mathrm{/}\mathrm{\parallel }{\mathrm{\Pi }}_a\psi \mathrm{\parallel }$; if $p_a=0$, the branch has zero weight and no conditional state. The identities hold on all retained auxiliary registers, even when entangled with the first label; only the fresh flag and scratch are cleared. Each test uses one forward check, one inverse check and one separately priced flag readout, so it costs $O(C)$ in the algorithm's query/check profile. The same compute/phase/uncompute word implements the exact marked phase flip with two check calls and its separately priced phase gate.

Let $\mathrm{\Pi }$ be any orthogonal projection and let $\xi ,\zeta$ be unit vectors with $\mathrm{\parallel }\xi -\zeta \mathrm{\parallel }\le \mathrm{\Delta }$. Put $a=\mathrm{\Pi }\xi$ and $b=\mathrm{\Pi }\zeta$. By [F16], $\mathrm{\Pi }$ is contractive, so $\mathrm{\parallel }a-b\mathrm{\parallel }\le \mathrm{\Delta }$; [F19] gives $\mathrm{\mid }\mathrm{\parallel }a\mathrm{\parallel }-\mathrm{\parallel }b\mathrm{\parallel }\mathrm{\mid }\le \mathrm{\Delta }$. If $\mathrm{\parallel }b\mathrm{\parallel }\ge 2\mathrm{/}3$ and the actual projected branch has positive probability (so $\mathrm{\parallel }a\mathrm{\parallel }>0$), [F18] yields $\parallel \frac{a}{\mathrm{\parallel }a\mathrm{\parallel }}-\frac{b}{\mathrm{\parallel }b\mathrm{\parallel }}\parallel \le \frac{\mathrm{\parallel }a-b\mathrm{\parallel }+\mathrm{\mid }\mathrm{\parallel }a\mathrm{\parallel }-\mathrm{\parallel }b\mathrm{\parallel }\mathrm{\mid }}{\mathrm{\parallel }b\mathrm{\parallel }}\le 3\mathrm{\Delta }\mathrm{.}$ The same estimate applies when one input is an ideal state and the other differs by a known reflection-error vector.

For the recursive branch suppose $0<p:=\pi (\mathcal{M})<1\mathrm{/}2$ and put ${\varphi }_0=\arcsin \sqrt{p}$. If $p\ge 1\mathrm{/}2$, the initial stationary sample already succeeds with probability at least $1\mathrm{/}2$, by [F1] and [F16], so no angle analysis is needed. In an exact recursive amplitude-amplification step, the marked phase flip followed by reflection about the current state triples its marked angle. In the ordered marked/unmarked basis, write $s=\sin \varphi ,c=\cos \varphi$ and $\mathrm{\mid }\psi ⟩=(s,c)$. The reflection matrix is $\left(\begin{array}{cc}2s^2-1& 2sc\\ 2sc& 2c^2-1\end{array}\right)=\left(\begin{array}{cc}-\cos 2\varphi & \sin 2\varphi \\ \sin 2\varphi & \cos 2\varphi \end{array}\right)$. Multiplying it by $\mathrm{diag}(-1,1)(s,c)=(-s,c)$ gives first coordinate $s\cos 2\varphi +c\sin 2\varphi =3s-4s^3=\sin 3\varphi$ and second coordinate $-s\sin 2\varphi +c\cos 2\varphi =4c^3-3c=\cos 3\varphi$, using [F13] and [F14]. At level $i$, let ${\varphi }_i$ be the actual angle after $A_i$, let ${\bar{\varphi }}_i=3^i{\varphi }_0$, and put $e_i=\mathrm{\mid }\sin {\varphi }_i-\sin {\bar{\varphi }}_i\mathrm{\mid }$. Let $t$ be the first ideal index with ${\bar{\varphi }}_t\ge \pi \mathrm{/}4$; then ${\bar{\varphi }}_t<3\pi \mathrm{/}4$ and, if $t\ge 2$, every $i\le t-1$ has ${\bar{\varphi }}_{i-1}<\pi \mathrm{/}12$. Inductively $e_{i-1}\le \gamma {\bar{\varphi }}_{i-1}\mathrm{/}\pi$ implies $\sin {\varphi }_{i-1}\le \sin (\pi \mathrm{/}12)+\gamma \mathrm{/}12$. By [F11] and [F15], the right side is less than $7\mathrm{/}24+1\mathrm{/}1440<1\mathrm{/}2$, while $\sin (\pi \mathrm{/}4)>1\mathrm{/}2$ by [F17]; hence both angles lie in $[0,\pi \mathrm{/}4]$. On the input to the level-$i$ approximate stationary reflection, after conjugating by $A_{i-1}^{†}$, the component orthogonal to the stationary vector has norm $\mathrm{\mid }\sin (2{\varphi }_{i-1})\mathrm{\mid }$. By step 1.2 the reflection error on that component has norm at most ${\beta }_i\mathrm{\mid }\sin (2{\varphi }_{i-1})\mathrm{\mid }$. The marked-amplitude change is no larger than this norm: the marked projector is orthogonal by [F16], so its orthogonal decomposition makes it contractive, and [F19] bounds the change in projected norms by the vector error. To compare triple angles, set $x=\sin a,y=\sin b$ for $a,b\in [0,\pi \mathrm{/}4]$, so $x,y\in [0,1\mathrm{/}\sqrt{2}]$ by [F14]. The identity $\sin 2a=2x\sqrt{1-x^2}$ shows that the absolute difference of the two double-angle values is at most $2\mathrm{\mid }x-y\mathrm{\mid }$: for $x\ge y$, the function $2x\sqrt{1-x^2}$ is increasing because its square difference is $4(x^2-y^2)(1-x^2-y^2)\ge 0$, while $2x\sqrt{1-x^2}-2y\sqrt{1-y^2}=2(x-y)\sqrt{1-x^2}+2y(\sqrt{1-x^2}-\sqrt{1-y^2})\le 2(x-y)\mathrm{.}$ The case $y\ge x$ is symmetric. By [F13], the triple-angle difference is $(x-y)(3-4(x^2+xy+y^2))$, whose coefficient has absolute value at most $3$ because $0\le x^2+xy+y^2\le 3\mathrm{/}2$. Therefore, for $i\le t-1$, $e_i\le {\beta }_i(\sin (2{\bar{\varphi }}_{i-1})+2e_{i-1})+3e_{i-1}\le 2{\beta }_i({\bar{\varphi }}_{i-1}+e_{i-1})+3e_{i-1}\mathrm{.}$ For these indices $\sin (2{\bar{\varphi }}_{i-1})\le 2{\bar{\varphi }}_{i-1}$ by [F15], so the last inequality follows.

Define ${\tilde{e}}_0=0$ and ${\tilde{e}}_i=4{\beta }_i{\bar{\varphi }}_{i-1}+3{\tilde{e}}_{i-1}$. Suppose inductively that $e_{i-1}\le {\tilde{e}}_{i-1}\le {\bar{\varphi }}_{i-1}$; then step 2.1 gives $e_i\le {\tilde{e}}_i$. Also $u_i:={\tilde{e}}_i\mathrm{/}(\gamma {\bar{\varphi }}_i)$ satisfies $u_i=(4\mathrm{/}(3\gamma )){\sum }_{j=1}^i{\beta }_j$. Since ${\beta }_j=\gamma \mathrm{/}(16j^2)$ and $j^{-2}\le (j-1{)}^{-1}-j^{-1}$ for $j\ge 2$, telescoping by [F10] gives ${\sum }_{j=1}^i{\beta }_j\le \gamma \mathrm{/}8$. Thus $u_i\le 1\mathrm{/}6<1\mathrm{/}\pi$ by [F11]. It follows that ${\tilde{e}}_i\le \gamma {\bar{\varphi }}_i\mathrm{/}\pi \le {\bar{\varphi }}_i$ for $i\le t-1$, closing the induction and giving $e_{t-1}\le \gamma {\bar{\varphi }}_{t-1}\mathrm{/}\pi <\gamma \mathrm{/}4$ when $t\ge 2$. At the last step, $\sin {\varphi }_{t-1}\le 1\mathrm{/}\sqrt{2}+\gamma \mathrm{/}4<18\mathrm{/}25$. By [F13], $g(s)=\sin (3\arcsin s)=3s-4s^3$ and $g(s)-g(u)=(s-u)(3-4(s^2+su+u^2))$; for $s,u\in [0,18\mathrm{/}25]$ the coefficient has absolute value at most $13\mathrm{/}4$. Therefore $e_t\le {\beta }_t+\frac{13}{4}{e}_{t-1}<\frac{\gamma }{8}+\frac{13\gamma }{16}<\gamma$, since ${\beta }_t\le \gamma \mathrm{/}16$. If $t=1$, $e_0=0$ and $e_1\le {\beta }_1<\gamma$. Finally ${\bar{\varphi }}_t\in [\pi \mathrm{/}4,3\pi \mathrm{/}4]$, so $A_t$ on a fresh stationary state has marked amplitude at least $1\mathrm{/}\sqrt{2}-\gamma$.

In the tolerant wrapper, after an unsuccessful marked measurement at level $i$, let $\mathrm{\mid }{\nu }_i^{\perp }⟩$ be the normalized unmarked component and let $\mathrm{\mid }{\mu }_i^{\perp }⟩$ be the normalized unmarked component of the ideal recursive state $\mathrm{\mid }{\varphi }_i⟩=A_i\mathrm{\mid }\pi ⟩$. The actual state differs from $A_i\mathrm{\mid }\pi ⟩$ by the previous input discrepancy ${\mathrm{\Delta }}_i=\mathrm{\parallel }{\nu }_{i-1}^{\perp }-\pi \mathrm{\parallel }$, since the same unitary $A_i$ is applied to both inputs. By the explicit Lüders realization in step 1.3, the positive-probability branches are the normalized projected components on all retained registers, and [F16] gives their squared-norm probabilities. For $i<t$, ${\bar{\varphi }}_i<\pi \mathrm{/}4$ and $e_i\le \gamma \mathrm{/}4$, so $\sin {\varphi }_i\le 1\mathrm{/}\sqrt{2}+\gamma \mathrm{/}4<18\mathrm{/}25$ and the unmarked norm exceeds $2\mathrm{/}3$ (since $1-(18\mathrm{/}25{)}^2>4\mathrm{/}9$). Projecting the two states onto the unmarked subspace and normalizing gives $\mathrm{\parallel }{\nu }_i^{\perp }-{\mu }_i^{\perp }\mathrm{\parallel }\le 3{\mathrm{\Delta }}_i$: the projected vectors differ by at most ${\mathrm{\Delta }}_i$, their norms differ by at most ${\mathrm{\Delta }}_i$, and the ideal norm is at least $2\mathrm{/}3$. The ideal unmarked directions drift by at most $12{\beta }_{i+1}{\bar{\varphi }}_i$: the error vector in the recursive reflection has norm at most $4{\beta }_{i+1}{\bar{\varphi }}_i$, and normalizing its unmarked projection costs at most a factor $3$. Also $\mathrm{\parallel }{\mu }_0^{\perp }-\pi \mathrm{\parallel }=2\sin ({\varphi }_0\mathrm{/}2)\le {\varphi }_0$; the equality follows from the inner product $⟨{\mu }_0^{\perp },\pi ⟩=\cos {\varphi }_0$ and the inequality from [F15]. Let ${\mathrm{\Delta }}_1=0$. The preceding bounds give, for $1\le i<t$, ${\mathrm{\Delta }}_{i+1}\le 3{\mathrm{\Delta }}_i+12{\varphi }_0{\sum }_{j=1}^i{3}^{j-1}{\beta }_j+{\varphi }_0\mathrm{.}$ Iterating this recurrence gives $\begin{array}{rl}{\displaystyle {\mathrm{\Delta }}_t}& {\displaystyle \le {\varphi }_0\sum _{i=1}^{t-1}{3}^{t-1-i}+12{\varphi }_0\sum _{i=1}^{t-1}{3}^{t-1-i}\sum _{j=1}^i{3}^{j-1}{\beta }_j}\\ {\displaystyle }& {\displaystyle \le \frac{1}{2}{3}^{t-1}{\varphi }_0+23^t{\varphi }_0\sum _{j=1}^{t-1}{\beta }_j}\\ {\displaystyle }& {\displaystyle \le \frac{\pi }{8}+\frac{3\gamma }{4}\mathrm{.}}\end{array}$ For the second inequality, interchange the finite sums: for fixed $j$, ${\sum }_{i=j}^{t-1}{3}^{t-1-i}<(1\mathrm{/}2)3^{t-j}$, so its coefficient becomes less than $12\cdot 3^{j-1}\cdot 3^{t-j}\mathrm{/}2=2\cdot 3^t$. For the last inequality, $3^t{\varphi }_0<3\pi \mathrm{/}4$ by minimality and ${\sum }_j{\beta }_j\le \gamma \mathrm{/}8$ by the telescoping bound in step 3.1.

Therefore at the unknown successful level $t$, the retained-state wrapper's marked amplitude is at least $1\mathrm{/}\sqrt{2}-\gamma -{\mathrm{\Delta }}_t\ge 1\mathrm{/}\sqrt{2}-\pi \mathrm{/}8-7\gamma \mathrm{/}4$. Since $1\mathrm{/}\sqrt{2}>7\mathrm{/}10$, $\pi <7\mathrm{/}2$ by [F11], and $\gamma =1\mathrm{/}120$, this lower bound exceeds $119\mathrm{/}480$, whose square exceeds $1\mathrm{/}20$. By [F16], the next projective marked measurement succeeds with probability at least $1\mathrm{/}20$ without resetting after earlier failed measurements.

If $\mathcal{M}=\mathrm{\varnothing }$, every verified marked-output branch is impossible, so the algorithm never returns a false marked label. For $0<{\epsilon }_0<1\mathrm{/}2$, the least $t_{\max }$ in the wrapper satisfies $3^{t_{\max }}=O(1\mathrm{/}\sqrt{{\epsilon }_0})$: minimality gives $3^{t_{\max }-1}\arcsin \sqrt{{\epsilon }_0}<\pi \mathrm{/}4$, and [F12, F15] imply $\arcsin x\ge x$ for $x\in [0,1]$ because $x=\sin (\arcsin x)\le \arcsin x$. For any nonempty instance with $p\ge {\epsilon }_0$, monotonicity of $\arcsin$ gives $t(p)\le t_{\max }$. When $0<p<1\mathrm{/}2$, the initial stationary sample succeeds with probability $p$; after its failure, the fresh stationary walk state in step 2 gives conditional success probability at least $1\mathrm{/}20$ by step 5.1. Hence the whole trial succeeds with probability at least $p+(1-p)\mathrm{/}20\ge 1\mathrm{/}20$. If $p\ge 1\mathrm{/}2$, the first sample alone succeeds with probability at least $1\mathrm{/}2$. Thus each outer trial succeeds with probability at least $1\mathrm{/}20$, so the exact rational-power definition of $n_{\mathrm{o}\mathrm{u}\mathrm{t}}$ gives $(19\mathrm{/}20{)}^{n_{\mathrm{o}\mathrm{u}\mathrm{t}}}\le \rho$ and the independent trials fail with probability at most $\rho$. If ${\epsilon }_0\ge 1\mathrm{/}2$, each direct stationary sample succeeds with probability at least $1\mathrm{/}2$ by [F1, F16], and the exact rational-power definition of $n_s$ gives $2^{-n_s}\le \rho$. Thus the error is one-sided and at most $\rho$.

At level $i$, the reflection $R({\beta }_i)$ uses $k_i=O(\log (i+1))$ QPE copies and $Q=O(1\mathrm{/}\sqrt{{\delta }_0})$ controlled $W$ steps per copy by [F9]; its query/update cost is $O((U_0\mathrm{/}\sqrt{{\delta }_0})\log (i+1)+C)$ including the marked phase flip. Each wrapper marked/unmarked test has the $O(C)$ compute/readout/uncompute cost in step 1.3. The recursion satisfies $C_i=3C_{i-1}+O((U_0\mathrm{/}\sqrt{{\delta }_0})\log (i+1)+C)$, so $C_i=O(3^i(U_0\mathrm{/}\sqrt{{\delta }_0}+C))$ because ${\sum }_{j\ge 1}{3}^{-j}\log (j+1)<\mathrm{\infty }$. Summing $C_i$ for $i\le t_{\max }$ is geometric. The first stationary sample can be prepared by one call to $A_{\pi }$ and testing its first label, at setup cost at most $S_0$; if that test fails, step 2 makes one further fresh stationary edge-state preparation at cost $S_0$. Since $A_0=I$ and the recursive $A_i$ and their actual adjoints contain only checks, walk reflections and controlled updates, they make no stationary-state preparation calls. Thus one outer trial uses at most two preparations, with both occurring on the empty-marked-set branch, and costs $2S_0+O(3^{t_{\max }}(U_0\mathrm{/}\sqrt{{\delta }_0}+C))=2S_0+O({\epsilon }_0^{-1\mathrm{/}2}(U_0\mathrm{/}\sqrt{{\delta }_0}+C))$. Multiplying by the $O(1+\ln (1\mathrm{/}\rho ))$ outer cap gives the low-mass statement; the direct-sampling branch costs $O((S_0+C)(1+\ln (1\mathrm{/}\rho )))$. For other resource coordinates, [F9] separately charges QPE phase gates and registers, while the procedure separately charges $R_A$, comparisons, coefficient precision, and classical arithmetic.