Circular-distance tail bound in phase estimation

For an outcome $y$, put $x=\theta -y\mathrm{/}Q$ and $d=d_{\mathbb{T}}(x)$. If $d>0$, then $x\mathrm{\notin }\mathbb{Z}$; write $x=\mathrm{\ell }+\epsilon d$ with $\mathrm{\ell }\in \{-1,0,1\}$ and $\epsilon \in \{-1,1\}$. By [F4] and [F1], $P_{\theta }(y)=Q^{-2}\mathrm{\mid }1-\exp (2\pi iQx){\mathrm{\mid }}^2\mathrm{/}\mathrm{\mid }1-\exp (2\pi ix){\mathrm{\mid }}^2$. By [F6], integer shifts do not change these exponentials. For $d\in [0,1\mathrm{/}2]$, Euler's formula gives $1-\exp (2\pi id)=\exp (\pi id)(\exp (-\pi id)-\exp (\pi id))=-2i\exp (\pi id)\sin (\pi d)$. Since $\mathrm{\mid }\exp (\pi id)\mathrm{\mid }=1$ and $\sin (\pi d)\ge 2d$ by [F5], the denominator modulus is at least $4d$; if $\epsilon =-1$, Euler's formula and the evenness of cosine and oddness of sine in [F8] give $\exp (-2\pi id)=\overline{\exp (2\pi id)}$, so [F7] gives the same modulus. The numerator is at most $2$ by [F6]–[F7]. Hence $P_{\theta }(y)\le 1\mathrm{/}(4Q^2{d}^2)$. If $d=0$, this outcome is not in the tail event because $Q\eta \ge K\ge 2$.

For an outcome in the tail, let $k=\lfloor Qd\rfloor$. If $k<K$, then $Qd<k+1\le K\le Q\eta \le Qd$, a contradiction; hence $k\ge K$. Also $k\le Q\mathrm{/}2$ by [F2], since $Qd\le Q\mathrm{/}2$. If $K>Q\mathrm{/}2$, there are no tail outcomes.

Suppose $K\le Q\mathrm{/}2$. For each label $y$, choose ${\mathrm{\ell }}_y=0$ if $\mathrm{\mid }x\mathrm{\mid }\le 1\mathrm{/}2$, ${\mathrm{\ell }}_y=1$ if $x>1\mathrm{/}2$, and ${\mathrm{\ell }}_y=-1$ if $x<-1\mathrm{/}2$, where $x=\theta -y\mathrm{/}Q$. Then ${\delta }_y=Q(x-{\mathrm{\ell }}_y)\in Q\theta +\mathbb{Z}$ and $\mathrm{\mid }{\delta }_y\mathrm{\mid }=Qd$. Distinct labels give distinct lifts: equality would make their difference a multiple of $Q$, while their label difference has magnitude less than $Q$. For an annulus $k\le Qd<k+1$, the lift lies in $[k,k+1)$ or $(-(k+1),-k]$. Each half-open interval of length $1$ contains at most one element of the integer translate $Q\theta +\mathbb{Z}$, because distinct elements differ by a nonzero integer. Thus at most two labels lie in this annulus.

Every such label has $d\ge k\mathrm{/}Q$, so step 1.1 bounds its probability by $1\mathrm{/}(4k^2)$. The total tail probability is therefore at most $\frac{1}{2}{\sum }_{k=K}^{Q\mathrm{/}2}{k}^{-2}$. For $k\ge K\ge 2$, $k^{-2}\le [k(k-1){]}^{-1}=(k-1{)}^{-1}-k^{-1}$. The finite sum telescopes to at most $1\mathrm{/}(K-1)$, so the tail is at most $1\mathrm{/}(2(K-1))$. Together with the empty-tail case in step 1.2 this proves the claim.