Success bound under an explicit amplitude-amplification phase mismatch

By the addition and quarter-turn identities [F5], [F9], [F15], $e^{i(\alpha +2\pi )}=e^{i\alpha }$, so the canonical inputs specified in the Statement implement exactly the operators with the signed labels, and $e^{i\phi }=e^{i{\phi }_0}$. In the ordered $(\mathrm{\mid }G⟩,\mathrm{\mid }B⟩)$ basis, set $u=e^{i\varphi }$ and $v=e^{i\phi }$. Since $\mathrm{\mid }u\mathrm{\mid }=\mathrm{\mid }v\mathrm{\mid }=1$ by [F5], the phase operations act by unit-modulus scalars on orthogonal subspaces and are unitary. From $A\mathrm{\mid }0⟩=\mathrm{\mid }\psi ⟩$ and the supplied phase operators, the iterate has matrix $Q=-\left(\begin{array}{cc}v((1-a)+au)& (u-1)\sqrt{a(1-a)}\\ v(u-1)\sqrt{a(1-a)}& a+(1-a)u\end{array}\right)\mathrm{.}$ The diagonal entries coincide by [F1] and $e^{i\phi }=e^{i{\phi }_0}$. The common diagonal is nonzero because the imaginary part of $(1-a)+a{e}^{i\varphi }$ is $a\sin \varphi >0$. The lower-left entry has modulus $2\sin (\varphi \mathrm{/}2)\sqrt{a(1-a)}=\sin (\varphi \mathrm{/}2)\sin (2\theta )=\sin \vartheta$. Thus the matched and implemented iterates are unitary and the matched matrix has equal diagonal entries.

Write the common diagonal as $d$ and the lower-left entry as $c$. Unitarity gives $\mathrm{\mid }d{\mathrm{\mid }}^2+\mathrm{\mid }c{\mathrm{\mid }}^2=1$, so $\mathrm{\mid }d\mathrm{\mid }=\cos \vartheta$ because $\mathrm{\mid }c\mathrm{\mid }=\sin \vartheta$ and $\vartheta \in (0,\pi \mathrm{/}2]$. Since $d,c\mathrm{\ne }0$, put $\eta =d\mathrm{/}\mathrm{\mid }d\mathrm{\mid }$ and $\zeta =(c\mathrm{/}\mathrm{\mid }c\mathrm{\mid })\bar{\eta }$; both have modulus one, and $d=\eta \cos \vartheta$, $c=\eta \zeta \sin \vartheta$. If $b$ is the upper-right entry, column orthogonality $\bar{d}b+\bar{c}d=0$ gives $b=-\eta \bar{\zeta }\sin \vartheta$. Hence $Q=\eta DR(\vartheta )D^{-1}$, with $D=\mathrm{diag}(1,\zeta )$ and $R(t)=\left(\begin{array}{cc}\cos t& -\sin t\\ \sin t& \cos t\end{array}\right)$.

Write $m\vartheta =\pi \mathrm{/}2+t$. From $m=\lceil \pi \mathrm{/}(2\vartheta )-1\mathrm{/}2\rceil$ we get $\mathrm{\mid }t\mathrm{\mid }\le \vartheta \mathrm{/}2$. Quarter-turn, parity, and monotonicity identities give $\sin (m\vartheta )=\cos t\ge \cos (\vartheta \mathrm{/}2)$ and $\mathrm{\mid }\cos (m\vartheta )\mathrm{\mid }=\mathrm{\mid }\sin t\mathrm{\mid }\le \sin (\vartheta \mathrm{/}2)$. If $a\ge 1\mathrm{/}4$, failure is at most $1\le 4a$. If $a<1\mathrm{/}4$, put $c=\cos (\pi \mathrm{/}3)=\sin (\pi \mathrm{/}6)$ by [F13]. Since $0<\pi \mathrm{/}6<\pi$, [F13] gives $c>0$, while the double-angle and supplementary identities give $2c^2-1=\cos (2\pi \mathrm{/}3)=-c$. Thus $(2c-1)(c+1)=0$, and positivity yields $c=1\mathrm{/}2$. Hence $\sin \theta =\sqrt{a}<\sin (\pi \mathrm{/}6)$, so $\theta <\pi \mathrm{/}6$ by [F14]. Because $\sin \vartheta =\sin (\varphi \mathrm{/}2)\sin (2\theta )\le \sin (2\theta )$ and both angles lie in $[0,\pi \mathrm{/}2]$, [F14] gives $\vartheta \le 2\theta$. The addition formulas [F9] and induction give $R(\vartheta {)}^m=R(m\vartheta )$. The initial coordinates are $(\sqrt{a},\sqrt{1-a})$, so the first coordinate of ${\eta }^{m}DR(m\vartheta )D^{-1}(\sqrt{a},\sqrt{1-a})$ has modulus [given, F2, F7, F9, F13, F14, F15, step 2.1, algebra] $\mid \sqrt{a}\cos (m\vartheta )-\bar{\zeta }\sqrt{1-a}\sin (m\vartheta )\mid \ge \sqrt{1-a}\mathrm{\mid }\sin (m\vartheta )\mathrm{\mid }-\sqrt{a}\mathrm{\mid }\cos (m\vartheta )\mathrm{\mid }\ge \sqrt{1-a}\cos (\vartheta \mathrm{/}2)-\sqrt{a}\sin (\vartheta \mathrm{/}2)\ge (1-a)-a=1-2a\mathrm{.}$ The last inequality uses $\vartheta \mathrm{/}2\le \theta$, cosine decreasing and sine increasing on $[0,\pi \mathrm{/}2]$, and $\cos \theta =\sqrt{1-a}$, $\sin \theta =\sqrt{a}$. The scalar ${\eta }^m$ has modulus one and $D$ leaves the good coordinate unchanged. By [F7], the matched failure probability is therefore at most $1-(1-2a{)}^2\le 4a$.

Let $Q^{\mathrm{\prime }}$ be the iterate with phase ${\phi }^{\mathrm{\prime }}$. The arbitrary-phase definition gives [given, F3, F4, F5, F6, F7, step 3.1, algebra] $Q^{\mathrm{\prime }}-Q=-A{S}_0(\varphi )A^{†}(e^{i{\phi }^{\mathrm{\prime }}}-e^{i\phi }){\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\mathrm{.}$ For every unit vector $x$, the projection contraction in [F6] and unitarity give $\mathrm{\parallel }(Q^{\mathrm{\prime }}-Q)x\mathrm{\parallel }\le \mathrm{\mid }{e}^{i{\phi }^{\mathrm{\prime }}}-e^{i\phi }\mathrm{\mid }\le \delta$ by [F5], hence $\mathrm{\parallel }{Q}^{\mathrm{\prime }}-Q\mathrm{\parallel }\le \delta$. Telescoping yields $Q^{\mathrm{\prime }m}-Q^m={\sum }_{r=0}^{m-1}{Q}^{\mathrm{\prime }m-1-r}(Q^{\mathrm{\prime }}-Q)Q^r,$ so unitarity gives $\mathrm{\parallel }{Q}^{\mathrm{\prime }m}-Q^m\mathrm{\parallel }\le m\delta$. Set $x=Q^m\mathrm{\mid }\psi ⟩$ and $y=Q^{\mathrm{\prime }m}\mathrm{\mid }\psi ⟩$ for $\mathrm{\mid }\psi ⟩=A\mathrm{\mid }0⟩$. Then $\mathrm{\parallel }x-y\mathrm{\parallel }\le \mathrm{\parallel }{Q}^{\mathrm{\prime }m}-Q^m\mathrm{\parallel }\le m\delta$. By [F7], the failure probabilities are $\mathrm{\parallel }{\mathrm{\Pi }}_{\mathrm{b}\mathrm{a}\mathrm{d}}x{\mathrm{\parallel }}^2$ and $\mathrm{\parallel }{\mathrm{\Pi }}_{\mathrm{b}\mathrm{a}\mathrm{d}}y{\mathrm{\parallel }}^2$. Contraction of ${\mathrm{\Pi }}_{\mathrm{b}\mathrm{a}\mathrm{d}}$ and reverse triangle give $\mid \mathrm{\parallel }{\mathrm{\Pi }}_{\mathrm{b}\mathrm{a}\mathrm{d}}x{\mathrm{\parallel }}^2-\mathrm{\parallel }{\mathrm{\Pi }}_{\mathrm{b}\mathrm{a}\mathrm{d}}y{\mathrm{\parallel }}^2\mid \le (\mathrm{\parallel }{\mathrm{\Pi }}_{\mathrm{b}\mathrm{a}\mathrm{d}}x\mathrm{\parallel }+\mathrm{\parallel }{\mathrm{\Pi }}_{\mathrm{b}\mathrm{a}\mathrm{d}}y\mathrm{\parallel })\mathrm{\parallel }x-y\mathrm{\parallel }\le 2\mathrm{\parallel }x-y\mathrm{\parallel }\le 2m\delta \mathrm{.}$ Thus implemented failure is at most $4a+2m\delta$ by step 3.1.

For $a<1\mathrm{/}4$, $\sin (2\theta )=2\sqrt{a(1-a)}\ge \sqrt{3}\sqrt{a}$. Set $x=\varphi \mathrm{/}2\in (0,\pi \mathrm{/}2)$ and $g(x)=\sin x-2x\mathrm{/}\pi$. By [F8], [F15], $g(0)=g(\pi \mathrm{/}2)=0$; by [F14], $g^{\mathrm{\prime }\mathrm{\prime }}(x)=-\sin x\le 0$. The derivatives in [F8], [F11] make $g^{\mathrm{\prime }}$ differentiable, hence continuous by [F16]; the mean value theorem [F10] applied to $g^{\mathrm{\prime }}$ gives $g^{\mathrm{\prime }}(t)\le g^{\mathrm{\prime }}(s)$ for $0\le s<t\le \pi \mathrm{/}2$. The same facts make $g$ continuous and differentiable, so [F10] on $[0,x]$ and $[x,\pi \mathrm{/}2]$ gives slopes $g(x)\mathrm{/}x$ and $-g(x)\mathrm{/}(\pi \mathrm{/}2-x)$; the first is at least the second, so $g(x)\ge 0$. Therefore $\sin (\varphi \mathrm{/}2)\ge \varphi \mathrm{/}\pi$, $\sin \vartheta \ge \sqrt{3}\varphi \sqrt{a}\mathrm{/}\pi$, and $\vartheta \ge \sin \vartheta$ by [F5], [F8]. Also $1=\sin (\pi \mathrm{/}2)\le \pi \mathrm{/}2$ by [F5], [F8], so $1\mathrm{/}(2\pi )\le 1$. The ceiling gives [given, F5, F8, F10, F11, F14, F15, F16, step 4.1, algebra] $m\le \frac{\pi }{2\vartheta }+\frac{1}{2}\le \frac{{\pi }^2}{2\sqrt{3}\varphi \sqrt{a}}+\frac{1}{2}\le \frac{\pi (\pi +\sqrt{3})}{2\sqrt{3}\varphi \sqrt{a}},$ where the last inequality uses $\varphi \sqrt{a}\le \pi$. Under $\delta \le Cϵ\varphi \sqrt{a}$ with $C=\sqrt{3}\mathrm{/}(2{\pi }^2(\sqrt{3}+\pi ))$, we obtain $2m\delta \le ϵ\mathrm{/}(2\pi )\le ϵ$. Step 4.1 gives failure at most $4a+ϵ$; when $a\ge 1\mathrm{/}4$, the same bound is automatic since failure is at most $1\le 4a$.

In the equal-phase case with $a\le 1\mathrm{/}4$, put $T=\tan (\varphi \mathrm{/}2)>0$ and $r=1-2a\in [1\mathrm{/}2,1]$. The matching condition [F1] and the principal inverse tangent [F12] give $\phi ={\phi }_0=2\arctan (rT)$ and $\delta =2(\arctan T-\arctan (rT))$. Let $f(s)=\arctan (sT)$. By [F11], [F12], $f^{\mathrm{\prime }\mathrm{\prime }}(s)=-2s{T}^3\mathrm{/}(1+s^2{T}^2{)}^2\le 0$; differentiability and [F16] give the continuity needed to apply [F10] to $f^{\mathrm{\prime }}$, so $f^{\mathrm{\prime }}$ is nonincreasing. Applying [F10] to $f$ on $[0,r]$ and $[r,1]$, the early secant slope is at least the late one; the secant slope on $[0,1]$, their weighted average, is therefore at least the late slope. Thus $f(1)-f(r)\le (1-r)(f(1)-f(0))\le (1-r)\pi \mathrm{/}2$, so $\delta \le \pi (1-r)=2\pi a$. If $\delta >0$, apply step 5.1 with $ϵ=\delta \mathrm{/}(C\varphi \sqrt{a})$; if $\delta =0$, step 3.1 gives the matched bound. The resulting failure is at most $4a+(2\pi \mathrm{/}C)\sqrt{a}\mathrm{/}\varphi \le (4\pi +2\pi \mathrm{/}C)\sqrt{a}\mathrm{/}\varphi$. For $a\ge 1\mathrm{/}4$, $1\le 2\pi \sqrt{a}\mathrm{/}\varphi$, so the same big-O bound holds on the full range.