Walk detection correctness and cost

If $\mathrm{\mid }X\mathrm{\mid }=1$, the supplied predicate is evaluated on the sole label and the procedure returns the exact answer. Assume henceforth $\mathrm{\mid }X\mathrm{\mid }\ge 2$. In the empty case $U=X$, $P^{\mathrm{\prime }}=P$, and the prepared row state is $T^{\mathrm{\prime }}\mathrm{\mid }s⟩$, where $\mathrm{\mid }s⟩=\mathrm{\mid }X{\mathrm{\mid }}^{-1\mathrm{/}2}{\sum }_{x\in X}\mathrm{\mid }x⟩$. Symmetry of $P$ gives $T^{\mathrm{\prime }}\mathrm{\mid }s⟩=S{T}^{\mathrm{\prime }}\mathrm{\mid }s⟩$, so [F3] places it on the $+1$ eigenline and its phase is exactly zero. The first marked check cannot accept, and [F6] makes QPE output $y=0$, for which the strict cutoff fails. Thus neither branch falsely accepts.

In a nonempty instance write $\epsilon =\mathrm{\mid }\mathcal{M}\mathrm{\mid }\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$. The first-register check measures a uniformly distributed label; if it is marked, the algorithm accepts immediately, including the endpoint $\mathcal{M}=X$. Otherwise $U=X\setminus \mathcal{M}$ is nonempty and the conditional row state is $T^{\mathrm{\prime }}\mathrm{\mid }{s}_U⟩$, with $\mathrm{\mid }{s}_U⟩=\mathrm{\mid }U{\mathrm{\mid }}^{-1\mathrm{/}2}{\sum }_{x\in U}\mathrm{\mid }x⟩$. By [F10], each first-register outcome has squared norm $1\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$ under $T^{\mathrm{\prime }}$, and [F12] projects onto the sum of exactly the $\mathrm{\mid }U\mathrm{\mid }$ unmarked row vectors and normalizes it.

On $U$, [F1] and the promises give $0\le \lambda (P_{UU})\le 1-\underset{‾}{\delta }\underset{‾}{\epsilon }$. Hence its eigenvalues are at most $1-\underset{‾}{\delta }\underset{‾}{\epsilon }<1$ and their one-reflection phases have circular distance from zero at least ${\gamma }_0\mathrm{/}(2\pi )$. The state $T^{\mathrm{\prime }}\mathrm{\mid }{s}_U⟩$ lies in $\mathrm{ran}{T}^{\mathrm{\prime }}$ and is orthogonal to every marked row vector $T^{\mathrm{\prime }}\mathrm{\mid }x⟩$, $x\in \mathcal{M}$, because those vectors have a distinct first-register label; the orthogonality also follows from the isometry [F10]. It therefore has no marked $\lambda =1$ component and no component in $(\mathrm{ran}{T}^{\mathrm{\prime }}+\mathrm{ran}(S{T}^{\mathrm{\prime }}){)}^{\perp }$. The decomposition [F2] and spectral mapping [F3] show that all its spectral components are the nonzero-phase signal components just bounded.

The choice of $m$ gives $1-\underset{‾}{\delta }\underset{‾}{\epsilon }\le \cos (\pi 2^{5-m})$. By [F13], $\cos {\gamma }_0=1-\underset{‾}{\delta }\underset{‾}{\epsilon }$, and [F14] with ${\gamma }_0\in [0,\pi ]$ and $\pi 2^{5-m}\in [0,\pi ]$ therefore gives ${\gamma }_0\ge \pi 2^{5-m}$, or $Q\ge 32\pi \mathrm{/}{\gamma }_0$. Also $0<\underset{‾}{\delta }\underset{‾}{\epsilon }\le 1$, so $\cos {\gamma }_0\ge 0=\cos (\pi \mathrm{/}2)$ by [F13] and [F17]; [F14] gives $0<{\gamma }_0\le \pi \mathrm{/}2$. Thus the branch comparison in algorithm step 5 is exact: $d(y)>1\mathrm{/}8$ implies $d(y)>{\gamma }_0\mathrm{/}(4\pi )$, while for $d(y)\le 1\mathrm{/}8$ both angles lie in $[0,\pi \mathrm{/}2]$ and strict decrease of cosine makes $d(y)>{\gamma }_0\mathrm{/}(4\pi )$ equivalent to $\cos (4\pi d(y))<1-\underset{‾}{\delta }\underset{‾}{\epsilon }$; equality takes the rejected branch. Set $\eta ={\gamma }_0\mathrm{/}(8\pi )$. Then $K=\lfloor Q\eta \rfloor \ge 4$, so [F4] bounds the probability of a circular QPE error at least $\eta$ by $1\mathrm{/}6$. To justify the needed distance comparison from the definition [F11], take $u=\theta -y\mathrm{/}Q\in (-1,1)$ and $v=y\mathrm{/}Q\in [0,1)$. Choose nearest integers $a,b$ to $u,v$, respectively, so $\mathrm{\mid }u-a\mathrm{\mid }=d_{\mathbb{T}}(u)$ and $\mathrm{\mid }v-b\mathrm{\mid }=d_{\mathbb{T}}(v)$. Since $\theta =u+v\in [0,1)$, its distance to the nearest integer is at most its distance to the particular integer $a+b$; hence $d_{\mathbb{T}}(\theta )\le \mathrm{\mid }\theta -(a+b)\mathrm{\mid }=\mathrm{\mid }(u-a)+(v-b)\mathrm{\mid }\le d_{\mathbb{T}}(u)+d_{\mathbb{T}}(v)\mathrm{.}$ Thus $d(y):=d_{\mathbb{T}}(y\mathrm{/}Q)\ge d_{\mathbb{T}}(\theta )-d_{\mathbb{T}}(\theta -y\mathrm{/}Q)$. On every outcome with estimation error $d_{\mathbb{T}}(\theta -y\mathrm{/}Q)<\eta$, step 2.1 gives $d(y)>\frac{{\gamma }_0}{2\pi }-\frac{{\gamma }_0}{8\pi }=\frac{3{\gamma }_0}{8\pi }>\frac{{\gamma }_0}{4\pi }\mathrm{.}$ Thus the algorithm accepts on that outcome. By [F5] the same failure bound holds for the whole conditional state, so a phase-test run accepts with probability at least $5\mathrm{/}6$. Including the initial marked-label branch can only raise its success probability.

Each fresh run therefore misses a promised nonempty set with probability at most $1\mathrm{/}6$. Independent fresh preparations make the probability that all $k$ runs miss at most $(1\mathrm{/}6{)}^k\le \underset{‾}{\beta }\le \beta$ by the definition of $k$ and the certified bracket. The empty case remains exact by step 1.1. The output relation only asserts the decision bit, since the phase-test branch measured no marked label.

For $\mathrm{\mid }X\mathrm{\mid }\ge 2$, a run makes one supplied uniform-state preparation, one row preparation, one initial marked check, one $m$-bit QPE, and then at most $Q-1$ controlled $U^{\mathrm{\prime }}$ calls by [F7]. If each controlled walk is expanded factorwise, [F8] supplies its four separately charged calls. Multiplying this worst-case per-run sum by $k$ proves the cost upper bound; early stopping only reduces it. For $\mathrm{\mid }X\mathrm{\mid }=1$, the exact branch uses only the sole-label predicate check. The named gate, query, synthesis, precision and bit coordinates are not combined, by the stated input accounting. To relate the finite parameters to the real promises, put $x=\underset{‾}{\delta }\underset{‾}{\epsilon }$. Then $x=1-\cos {\gamma }_0=2{\sin }^2({\gamma }_0\mathrm{/}2)\le {\gamma }_0^2\mathrm{/}2$ by [F15]–[F16], so ${\gamma }_0\ge \sqrt{2x}$. The least-power-of-two choice gives $Q<64\pi \mathrm{/}{\gamma }_0=O(x^{-1\mathrm{/}2})$; since $x\ge {\delta }_0{\epsilon }_0\mathrm{/}4$, $Q=O(({\delta }_0{\epsilon }_0{)}^{-1\mathrm{/}2})$. Also $\underset{‾}{\beta }\ge \beta \mathrm{/}2$, so $k=O(1+\ln (1\mathrm{/}\beta ))$.