Quantum Phase Estimation

At $n=0$, the sum is empty, so $(1-z)S_0(z)=0=1-z^0$ by [F1] and [F2].

Fix $n\in \mathbb{N}$ and assume $(1-z)S_n(z)=1-z^n$; this is the induction hypothesis.

By [F1] and [F2], $(1-z)S_{n+1}=(1-z)S_n+(1-z)z^n=(1-z^n)+(z^n-z^{n+1})=1-z^{n+1}$, using distributivity in [F3] and the induction hypothesis [step 1.2]. Thus [F5] proves $(1-z)S_n(z)=1-z^n$ for every $n$.

If $z=1$, every summand is $1$, so [F1] gives $S_0(1)=0$ and $S_{n+1}(1)=S_n(1)+1$. At $n=0$, this equals ${\iota }_{\mathbb{C}}(0)=0$ by [F4]; if $S_n(1)={\iota }_{\mathbb{C}}(n)$, the two successor recursions give $S_{n+1}(1)=S_n(1)+1={\iota }_{\mathbb{C}}(n)+1={\iota }_{\mathbb{C}}(n+1)$. Induction [F5] proves $S_n(1)={\iota }_{\mathbb{C}}(n)$ for every $n$. If $z\mathrm{\ne }1$, then $1-z\mathrm{\ne }0$, so divide the identity from step 2.1 by $1-z$ in the field [F3] to obtain $S_n(z)=(1-z^n)\mathrm{/}(1-z)$.

In the QPE specialization, repeated use of [F6] and the power recursion [F2] gives $z^Q=\exp (2\pi iQ(\theta -y\mathrm{/}Q))=\exp (2\pi i(Q\theta -y))$. Since $y\in \mathbb{Z}$, [F6] gives $\exp (-2\pi iy)=1$, hence $z^Q=\exp (2\pi iQ\theta )$. The same kernel statement gives $z=1$ exactly when $2\pi i(\theta -y\mathrm{/}Q)\in 2\pi i\mathbb{Z}$, equivalently $\theta -y\mathrm{/}Q\in \mathbb{Z}$, or $Q\theta -y\in Q\mathbb{Z}$.

Define $g(t)=\sin t-2t\mathrm{/}\pi$ on $[0,\pi \mathrm{/}2]$. By [F1], [F3], and [F4], $g(0)=g(\pi \mathrm{/}2)=0$ and $g^{\mathrm{\prime }}(t)=\cos t-2\mathrm{/}\pi$ on the interior.

By [F2], $g^{\mathrm{\prime }}$ is nonincreasing: if $s<t$, then $\cos s\ge \cos t$, so $g^{\mathrm{\prime }}(s)\ge g^{\mathrm{\prime }}(t)$.

Fix $t\in (0,\pi \mathrm{/}2)$. Apply [F5] on $[0,t]$ and $[t,\pi \mathrm{/}2]$ to obtain $a\in (0,t)$ and $b\in (t,\pi \mathrm{/}2)$ with $g(t)=t{g}^{\mathrm{\prime }}(a)$ and $-g(t)=(\pi \mathrm{/}2-t)g^{\mathrm{\prime }}(b)$. Since $a<b$, step 2.1 gives $g^{\mathrm{\prime }}(a)\ge g^{\mathrm{\prime }}(b)$. Dividing by the positive numbers $t$ and $\pi \mathrm{/}2-t$, then multiplying by their product, gives $g(t)\pi \mathrm{/}2\ge 0$; as $\pi >0$, $g(t)\ge 0$.

If $0<u<1\mathrm{/}2$, take $t=\pi u\in (0,\pi \mathrm{/}2)$ in step 3.1 to get $\sin (\pi u)\ge 2u$. At $u=0$ and $u=1\mathrm{/}2$, the same inequality is equality by [F1].

For $v\ge 0$, [F6] and $\sin 0=0$ give $\sin v=\sin v-\sin 0\le \mathrm{\mid }\sin v-\sin 0\mathrm{\mid }\le v$. Thus both stated inequalities hold.

Before the controlled powers, the state is $Q^{-1\mathrm{/}2}{\sum }_{x=0}^{Q-1}\mathrm{\mid }x⟩\otimes \psi$ by [F2]. Write $x={\sum }_j{c}_j{2}^j$, where $c_j$ is the bit at wire $q_{m-1-j}$ by [F1]. The controlled operation on that wire applies $U^{2^j}$ exactly when $c_j=1$; multiplying the eigenvalues gives ${\prod }_j\exp (2\pi i\theta c_j{2}^j)=\exp (2\pi i\theta x)$. Hence the state after the controlled-power stage is $Q^{-1\mathrm{/}2}{\sum }_x\exp (2\pi i\theta x)\mathrm{\mid }x⟩\otimes \psi$. Reading this gate sequence as an operator on the ordered register uses [F9].

The inverse QFT matrix coefficient from input $x$ to output $y$ is $Q^{-1\mathrm{/}2}\exp (-2\pi ixy\mathrm{/}Q)$, by [F3] and the adjoint convention. Applying it to step 1.1 gives $\chi ={\sum }_{y=0}^{Q-1}{a}_y\mathrm{\mid }y⟩\otimes \psi$, where $a_y=Q^{-1}{\sum }_{x=0}^{Q-1}\exp (2\pi ix(\theta -y\mathrm{/}Q))$. The sign is positive in the eigenphase and negative in the inverse-QFT coefficient, yielding the displayed difference $\theta -y\mathrm{/}Q$. The operator ordering is the one in [F9].

The vector $\chi$ is normalized. Expand the finite squared moduli using [F7]. For every real $t$, [F10] gives $\overline{\exp (it)}=\exp (-it)$, and the exponential addition law combines each conjugate pair of phases; interchanging the finite sums then gives ${\sum }_y\mathrm{\mid }{a}_y{\mathrm{\mid }}^2=Q^{-2}{\sum }_{x,x^{\mathrm{\prime }}}\exp (2\pi i(x-x^{\mathrm{\prime }})\theta ){\sum }_y\exp (-2\pi i(x-x^{\mathrm{\prime }})y\mathrm{/}Q)$. By [F6], the inner sum is $Q$ when $x=x^{\mathrm{\prime }}$ and $0$ otherwise, because $0\le x,x^{\mathrm{\prime }}<Q$; therefore ${\sum }_y\mathrm{\mid }{a}_y{\mathrm{\mid }}^2=Q^{-2}Q\cdot Q=1$. Since $\mathrm{\parallel }\psi \mathrm{\parallel }=1$ and the $\mathrm{\mid }y⟩$ are orthonormal, $\mathrm{\parallel }\chi \mathrm{\parallel }=1$.

The ray-projector theorem [F5] makes $\rho =\mathrm{\mid }\chi ⟩⟨\chi \mathrm{\mid }$ a density operator. The phase-register projective outcome has projector $P_y$ from [F4], so it extracts $a_y\mathrm{\mid }y⟩\otimes \psi$. By [F5] and [F8], $\mathrm{tr}(\rho P_y)=\mathrm{tr}(P_y\rho )=\mathrm{tr}(\mathrm{\mid }{P}_y\chi ⟩⟨\chi \mathrm{\mid })=⟨P_y\chi ,\chi {⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}=\mathrm{\parallel }{P}_y\chi {\mathrm{\parallel }}^2=\mathrm{\mid }{a}_y{\mathrm{\mid }}^2$, where the penultimate equality uses $P_y=P_y^{\ast }=P_y^2$. The outcome law in [F4] therefore gives this probability to the classical label $y$. Substituting the value of $a_y$ from step 2.1 gives exactly the displayed $P_{\theta }(y)$.

The finite sum in the displayed law is defined for every $y,\theta$, including when $Q\theta$ is an integer. For its geometric-sum specialization, the denominator is zero exactly when $z=\exp (2\pi i(\theta -y\mathrm{/}Q))=1$, equivalently $Q\theta -y\in Q\mathbb{Z}$; in every other case Finite geometric sum for phase-estimation amplitudes gives the nonzero-denominator quotient. Thus the stated squared-sum law handles all phases without an undefined quotient.

Under controlled-power access, the loop in [F1] invokes exactly one supplied operation for each of the $m$ indices $j=0,\dots ,m-1$, hence exactly $m$ controlled-power queries.

Under single controlled-unitary access, the repeated implementation specified by the procedure uses $2^j$ sequential calls to $C(U)$ for the controlled power at index $j$ [F2], so the total query count is the natural sum $S_m$. To identify this natural-valued sum, prove $S_n+1=2^n$ by induction. At $n=0$, $S_0+1=0+1=1=2^0$. If $S_n+1=2^n$, then [F4, F6, F7] give $S_{n+1}+1=(S_n+2^n)+1=(S_n+1)+2^n=2^n+2^n=2^n\cdot 2=2^{n+1}$. Hence $S_m+1=2^m=Q$; by the defining truncated difference in [F4]'s source and commutativity of addition, $S_m=Q-1$.

The supplied power circuits contribute ${\sum }_j{C}_j$ ordinary gates. Phase-register preparation contributes $m$ Hadamards, and the inverse QFT contributes the count in [F3]. Adding gives the displayed unitary gate count; reversing the QFT circuit changes neither its count nor the query count.

Measurement outputs one $m$-bit label. The operation model [F5] keeps query, ordinary-gate, and classical-bit costs separate; the input eigenstate's preparation is outside the theorem's stated count. Therefore the displayed formula asserts only the stated gate profile and does not infer an implementation of powers from a black-box $U$.

Put $n=\lfloor Q\theta \rfloor$ and $r=Q\theta -n$, so $n\in \{0,\dots ,Q-1\}$ and $0\le r<1$ by [F1]. If $r\le 1\mathrm{/}2$, choose $y=n$; if $r>1\mathrm{/}2$ and $n+1<Q$, choose $y=n+1$; if $r>1\mathrm{/}2$ and $n+1=Q$, choose $y=0$. The resulting circular distance is respectively $r\mathrm{/}Q$ or $(1-r)\mathrm{/}Q$, at most $1\mathrm{/}(2Q)$.

Every integer $k$ has a lift representation $k=y+sQ$ with $s\in \mathbb{Z}$ and $y\in \{0,\dots ,Q-1\}$: apply [F1] to $k\mathrm{/}Q$ and set $s=\lfloor k\mathrm{/}Q\rfloor$, $y=k-sQ$, so $0\le y<Q$. Thus grid labels and their lifts range over all integers, and minimizing circular phase distance is the same as choosing an integer nearest to $Q\theta =n+r$. If $r\le 1\mathrm{/}2$, every integer $k\le n$ is at distance at least $r$ and every $k\ge n+1$ is at distance at least $1-r\ge r$, so $n$ is nearest; when $r=1\mathrm{/}2$, $n+1$ is also nearest. If $r>1\mathrm{/}2$, every integer $k\le n$ is at distance at least $r>1-r$ and every $k\ge n+1$ is at distance at least $1-r$, so $n+1$ is nearest. If a nearest integer is $Q$, its label is $0$: this is the wrap-around choice in step 1.1 when $r>1\mathrm{/}2$, and the tied wrap-around label when $r=1\mathrm{/}2$. Thus every nearest label has distance $d\le 1\mathrm{/}(2Q)$.

Fix a nearest label and set $x=\theta -y\mathrm{/}Q$, $d=d_{\mathbb{T}}(x)$. Since $x\in (-1,1)$, the definition of $d$ gives an integer $\mathrm{\ell }\in \{-1,0,1\}$ and sign $\epsilon \in \{-1,1\}$ with $x=\mathrm{\ell }+\epsilon d$. By [F6], $\exp (2\pi ix)=\exp (2\pi i\epsilon d)$. 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] shows its distance from $1$ has the same modulus as for $d$. 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\ge 0$ by [F5], $\mathrm{\mid }1-\exp (2\pi ix)\mathrm{\mid }=2\sin (\pi d)$. The same calculation with $Qx=Q\mathrm{\ell }+\epsilon Qd$ gives $\mathrm{\mid }1-\exp (2\pi iQx)\mathrm{\mid }=2\sin (\pi Qd)$ when $d>0$, because $Qd\le 1\mathrm{/}2$.

When $d>0$, [F4] and step 3.1 yield $P_{\theta }(y)=Q^{-2}(\sin (\pi Qd)\mathrm{/}\sin (\pi d){)}^2$. If $d=0$, then $x=0$ and [F3] gives $P_{\theta }(y)=1$.

If $d>0$, step 2.1 gives $0<Qd\le 1\mathrm{/}2$. By [F5], $\sin (\pi Qd)\ge 2Qd$ and $0<\sin (\pi d)\le \pi d$; hence step 4.1 gives $P_{\theta }(y)\ge Q^{-2}(2Qd\mathrm{/}(\pi d){)}^2=4\mathrm{/}{\pi }^2$. If $d=0$, step 4.1 gives $P_{\theta }(y)=1\ge 4\mathrm{/}{\pi }^2$. Thus every nearest label, including either label at a tie, has the claimed probability.

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$.