Amplitude-estimation additive error and success probability

By [F21], the input state lies in the span of eigenvectors of $Q$ with phases $\theta \mathrm{/}\pi$ and $1-\theta \mathrm{/}\pi$; the endpoint cases are single eigenphases. QPE is therefore applied to its finite eigenphase decomposition, and the projective measurement returns a label in the finite set $\{0,\dots ,M-1\}$ by [F22].

In repeated-unitary mode, the task contract expands each controlled $Q$ as $C(-I)C(A)C(S_0)C(A^{\ast })C(S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}})$, with every factor supplied or implemented and charged. In power-query mode the estimator instead uses the supplied controlled powers as declared queries, each with its own cost vector; it does not require separately supplied controlled $A$ or $A^{\ast }$. The scalar minus is invisible only in an uncontrolled call by [F24], while under control it is retained as a relative phase. The reflection factors are unitary by [F25]. Thus the circuit instructions are well-defined under either declared access mode.

For ${\zeta }_M=e^{2\pi i\mathrm{/}M}$, Euler's formula gives ${\sin }^2(\pi y\mathrm{/}M)=(1-\cos (2\pi y\mathrm{/}M))\mathrm{/}2=(2-{\zeta }_M^y-{\zeta }_M^{-y})\mathrm{/}4$. This is a real algebraic element of the cyclotomic field, so the stated output is exactly encoded; query counts are those in [F26] and decimal/bit processing is charged under [F27].

Let $f(x)={\sin }^{2}x$ and first suppose $0<a<1$. Fix one Grover eigenphase $\varphi \in \{\theta \mathrm{/}\pi ,1-\theta \mathrm{/}\pi \}$, put $x=\pi \varphi$, and let $d=d_{\mathbb{T}}(\varphi -y\mathrm{/}M)$. The difference belongs to $(-1,1)$, so there are an integer $q$ and $\sigma \in \{-1,1\}$ with $\varphi -y\mathrm{/}M=q+\sigma d$. Hence $\pi y\mathrm{/}M=x-q\pi -\sigma \pi d$. By the integer $\pi$-shift identity [F18], the estimator output is ${\sin }^2(\pi y\mathrm{/}M)=f(x+h)$ for $h=-\sigma \pi d$. On either eigenphase, $f(x)=a$: the first has $x=\theta$, and the second has $x=\pi -\theta$ and uses the supplementary identity [F18]. Also $f^{\mathrm{\prime }}(x)=\sin (2x)$ by [F5], and $\mathrm{\mid }{f}^{\mathrm{\prime }}(x)\mathrm{\mid }=2\sqrt{a(1-a)}$ on both branches: the second branch has $\sin (2\pi -2\theta )=-\sin (2\theta )$ by [F14] and [F18], while ${\sin }^2\theta =a$ and ${\cos }^2\theta =1-a$ by [F14]. For any real $x,h$, [F5] and [F7] give $f(x+h)-f(x)-h{f}^{\mathrm{\prime }}(x)={\int }_0^h(\sin (2x+2u)-\sin (2x))du$. By [F6], the integrand has absolute value at most $2\mathrm{\mid }u\mathrm{\mid }$, so either orientation gives absolute remainder at most $h^2$. On the phase-success event $d\le k\mathrm{/}M$, hence $\mathrm{\mid }h\mathrm{\mid }\le \pi k\mathrm{/}M$, and the displayed error bound follows.

Let $k\ge 2$ and fix one Grover eigenphase $\varphi$. For a tail outcome at distance $d>0$, write $x=\varphi -y\mathrm{/}M=\mathrm{\ell }\pm d$ by [F10]. Integer periodicity [F17] and sine parity [F14] reduce the denominator to $\mathrm{\mid }1-e^{2\pi id}\mathrm{\mid }=2\sin (\pi d)$ by Euler [F12] and the sine addition formula. Thus [F8]–[F9] and [F12]–[F14] give $P_{\varphi }(y)=M^{-2}\mathrm{\mid }1-e^{2\pi iM(\varphi -y\mathrm{/}M)}{\mathrm{\mid }}^2\mathrm{/}\mathrm{\mid }1-e^{2\pi i(\varphi -y\mathrm{/}M)}{\mathrm{\mid }}^2\le 1\mathrm{/}(4M^2{d}^2)$, since the numerator modulus is at most $2$ and the denominator is $2\sin (\pi d)\ge 4d$ by [F10]–[F11]. In the tail $d\ge k\mathrm{/}M$, put $j=\lfloor Md\rfloor$; [F15] gives $k\le j\le \lfloor M\mathrm{/}2\rfloor$. Each annulus $j\le Md<j+1$ has at most two arcs of length $1\mathrm{/}M$, each containing at most one label on the $1\mathrm{/}M$ grid. Thus the tail probability is at most $\frac{1}{2}{\sum }_{j=k}^{\lfloor M\mathrm{/}2\rfloor }{j}^{-2}<\frac{1}{2}{\sum }_{j=k}^{\lfloor M\mathrm{/}2\rfloor }[j(j-1){]}^{-1}\le 1\mathrm{/}[2(k-1)]$. An empty tail has probability zero, also strictly below this positive bound. This strengthens [F4], so success is strictly greater than $1-1\mathrm{/}[2(k-1)]$ for each phase and hence for their mixture.

For $k=1$, both labels from [F3] have circular distance at most $1\mathrm{/}M$ from the relevant Grover phase. Off-grid, floor and ceiling labels have distances strictly below $1\mathrm{/}M$; on-grid the distance is zero. Thus the event used in step 1.4 has probability at least $8\mathrm{/}{\pi }^2$.

At $a=0$ the Grover phase is the exact grid phase $0$; at $a=1$ it is $1\mathrm{/}2$, whose label $M\mathrm{/}2$ is integral because $M$ is even. Exact-grid recovery [F4] gives outputs $0$ and $1$. Finally $2\sqrt{a(1-a)}\le 1$ gives the stated $k=1$ simplification.