Quantum Amplitude Estimation

Rag9704 May 24

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.