# Quantum Amplitude Estimation

Given a Boolean function $f$: to find an $x$ $\in$ $X$ where $X$ $\rightarrow$ {0,1} such that $f(x) = 1$ , we can denote $N$ as the number of inouts on which \f takes the value 1, and it can written as$N = |{x \in (X|f(x)=1)}|$ . If we have a classical probabilistic algorithm $P$ that outputs a guess on input $x$ , the solution to instance $x$ can be found by repeatedly calling $P$ and $X$ . If $X$ $(x,P(x)) =1$ with probability $p>0$ , we have to repeat the process $1/p$ times on average.

Suppose given a unitary transformation, $A$ , which is a quantum algorithm, unlike making measurement in the case of classical $P$ algorithm, this produces a quantum superposition state of the “desired” result that $X (x,P(x)) = 1$ X and “undesired” result that $X (x,P(x)) \neq 1$. Then amplitude estimation is the problem of estimating $a$ , the probability that a measurement of $\ket{\Psi_{i}}$ yields a good solution. It is sufficient to evaluate $A$ and $X$ in an expected number of times that is proportional to $1/\sqrt{a}$ .

To explain amplitude estimation, the quantum state after unitary transformation A can be expressed as a linear combination of $\Psi_{+}$ and the orthogonal $\Psi_{-}$ :

$A\ket{0} = \ket{\psi} = -\frac{i}{\sqrt{2}}(\e^{i\theta_{a}}\ket{\psi_{+}}+\e^{-i\theta_{a}}\ket{\psi_{-}})$

so the success probability “$a$ ” is converted to the solution of angle $\theta_{a}$ that decides the eigenvalue for unitary transformation $A$

Apply an operator $Q$ to $A$

$Q = AS_{0}\dagger{A}S_{\psi 0}$

where $S_{0} = 1 - 2\ket{0}\bra{0}$ , and $S_{\psi 0} = 1 - 2\ket{\psi}\ket{0}\bra{0}\bra{\psi}$ . As illustrated in Fig.1, an initial state first rotates along $\psi$ by the operator $S_{\psi 0}$ , and then rotates along $\psi_{+}$ by the operator $S_{0}$. Therefore, the angle between the arbitrarily set initial state and the final state after the operator $Q$ becomes $2\theta_{a}$ . In this case, when the initial state is $A$ , operator $Q$ just shifts from $\ket{\psi}$ for $2\theta_{a}$

The task of finding the eigenvalue for quantum state $\ket{\Psi}$ of the unitary transformation $A$ can be fulfilled by Quantum Phase Estimation that requires another register with $m$ additional qubits. As shown in Fig.2, the phase estimation quantum circuit comprises Hadamard gates, controlled-rotation operators and an inverse quantum Fourier transform ($QFT^{-1}$ ) operation.

Firstly, the Hamamard gates prepare the $m$ qubits in the uniform superposition:

$\ket{0}^{\otimes m}\ket{\psi} \rightarrow \sum_{j=0}^{2^{m}-1}\ket{j}\ket{\psi}$

As has been mentioned, the operator $Q$ essentially causes a $Y$-rotation of angle $2\theta_{a}$ , i.e., $Q = R_{y}(2\theta_{a})$ . In this phase estimation circuit, the many controlled-rotation operators $Q_{j}$ satisfies $Q_{j} = R_{y}(2j\theta_{a})$ , and they turn the above equation into:

$\frac{1}{\sqrt{2^{m}}}\sum_{j=0}^{2^{m}-1}\e^{2i\theta_{a}j}\ket{j}\ket{\psi}$

Applying the $QFT^{-1}$ operation, we can reverse the action on vector $\ket{j}$ to that on $\ket{\theta_{a}}$ :

$QFT^{-1}(\frac{1}{\sqrt{2^{m}}}\sum_{j=0}^{2^{m}-1}\exp{2i\theta_{a}j}\ket{j}\ket{\psi})=\frac{1}{\pi}\ket{\theta_{a}}\ket{\psi}$

By taking measurement on the register of $m$ qubits, we can get the approximation of $\theta_{a}$. This is done by obtaining the measured integer$y \rightarrow {0,1,2,..., 2^{m}-1}$ . Taking$M = 2^{m}$ , then $\theta_{a}$ can be approximated as $\tilde{\theta_{a}} = y\pi /M$ , which yields $\tilde{a}$ , the approximation of the aforementioned probability $a$ :

$\tilde{a} = sin^{2}(\frac{y\pi}{M}) \in [0,1]$

satisfying the following inequality:

$|a - \tilde{a}| \leq \frac{\pi}{M} + \frac{\pi^{2}}{\M^{2}} = O(M^{-1})$

with probability at least $\frac{8}{M^2}$ . Comparing with the $O(M^{\frac{-1}{2}})$ convergence rate of the classical Monte Carlo method, the quantum amplitude estimation method converges faster with a quadratic speed-up.