Given a Boolean function fff: to find an xxx ∈\in∈ XXX where XXX →\rightarrow→ {0,1} such that f(x)=1f(x) = 1f(x)=1 , we can denote NNN as the number of inouts on which \f takes the value 1, and it can written asN=∣x∈(X∣f(x)=1)∣N = |{x \in (X|f(x)=1)}|N=∣x∈(X∣f(x)=1)∣ . If we have a classical probabilistic algorithm PPP that outputs a guess on input xxx , the solution to instance xxx can be found by repeatedly calling PPP and XXX . If XXX (x,P(x))=1(x,P(x)) =1(x,P(x))=1 with probability p>0p>0p>0 , we have to repeat the process 1/p1/p1/p times on average.
Suppose given a unitary transformation, AAA , which is a quantum algorithm, unlike making measurement in the case of classical PPP algorithm, this produces a quantum superposition state of the “desired” result that X(x,P(x))=1X (x,P(x)) = 1X(x,P(x))=1 X and “undesired” result that X(x,P(x))≠1X (x,P(x)) \neq 1X(x,P(x))=1. Then amplitude estimation is the problem of estimating aaa , the probability that a measurement of ∣Ψi⟩\ket{\Psi_{i}}∣Ψi⟩ yields a good solution. It is sufficient to evaluate AAA and XXX in an expected number of times that is proportional to 1/a1/\sqrt{a}1/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∣0⟩=∣ψ⟩=−i2(\eiθa∣ψ+⟩+\e−iθa∣ψ−⟩)A\ket{0} = \ket{\psi} = -\frac{i}{\sqrt{2}}(\e^{i\theta_{a}}\ket{\psi_{+}}+\e^{-i\theta_{a}}\ket{\psi_{-}})A∣0⟩=∣ψ⟩=−2i(\eiθa∣ψ+⟩+\e−iθa∣ψ−⟩)
so the success probability “aaa ” is converted to the solution of angle θa\theta_{a}θa that decides the eigenvalue for unitary transformation AAA
Apply an operator QQQ to AAA
Q=AS0†ASψ0Q = AS_{0}\dagger{A}S_{\psi 0}Q=AS0†ASψ0
where S0=1−2∣0⟩⟨0∣S_{0} = 1 - 2\ket{0}\bra{0}S0=1−2∣0⟩⟨0∣ , and Sψ0=1−2∣ψ⟩∣0⟩⟨0∣⟨ψ∣S_{\psi 0} = 1 - 2\ket{\psi}\ket{0}\bra{0}\bra{\psi}Sψ0=1−2∣ψ⟩∣0⟩⟨0∣⟨ψ∣ . As illustrated in Fig.1, an initial state first rotates along ψ\psiψ by the operator Sψ0S_{\psi 0}Sψ0 , and then rotates along ψ+\psi_{+}ψ+ by the operator S0S_{0}S0. Therefore, the angle between the arbitrarily set initial state and the final state after the operator QQQ becomes 2θa2\theta_{a}2θa . In this case, when the initial state is AAA , operator QQQ just shifts from ∣ψ⟩\ket{\psi}∣ψ⟩ for 2θa2\theta_{a}2θa
The task of finding the eigenvalue for quantum state ∣Ψ⟩\ket{\Psi}∣Ψ⟩ of the unitary transformation AAA can be fulfilled by Quantum Phase Estimation that requires another register with mmm 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−1QFT^{-1}QFT−1 ) operation.
Firstly, the Hamamard gates prepare the mmm qubits in the uniform superposition:
∣0⟩⊗m∣ψ⟩→∑j=02m−1∣j⟩∣ψ⟩\ket{0}^{\otimes m}\ket{\psi} \rightarrow \sum_{j=0}^{2^{m}-1}\ket{j}\ket{\psi}∣0⟩⊗m∣ψ⟩→∑j=02m−1∣j⟩∣ψ⟩
As has been mentioned, the operator QQQ essentially causes a YYY-rotation of angle 2θa2\theta_{a}2θa , i.e., Q=Ry(2θa)Q = R_{y}(2\theta_{a})Q=Ry(2θa) . In this phase estimation circuit, the many controlled-rotation operators QjQ_{j}Qj satisfies Qj=Ry(2jθa)Q_{j} = R_{y}(2j\theta_{a})Qj=Ry(2jθa) , and they turn the above equation into:
12m∑j=02m−1\e2iθaj∣j⟩∣ψ⟩\frac{1}{\sqrt{2^{m}}}\sum_{j=0}^{2^{m}-1}\e^{2i\theta_{a}j}\ket{j}\ket{\psi}2m1∑j=02m−1\e2iθaj∣j⟩∣ψ⟩
Applying the QFT−1QFT^{-1}QFT−1 operation, we can reverse the action on vector ∣j⟩\ket{j}∣j⟩ to that on ∣θa⟩\ket{\theta_{a}}∣θa⟩ :
QFT−1(12m∑j=02m−1exp2iθaj∣j⟩∣ψ⟩)=1π∣θ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}QFT−1(2m1∑j=02m−1exp2iθaj∣j⟩∣ψ⟩)=π1∣θa⟩∣ψ⟩
By taking measurement on the register of mmm qubits, we can get the approximation of θa\theta_{a}θa. This is done by obtaining the measured integery→0,1,2,...,2m−1y \rightarrow {0,1,2,..., 2^{m}-1}y→0,1,2,...,2m−1 . TakingM=2mM = 2^{m}M=2m , then θa\theta_{a}θa can be approximated as θa~=yπ/M\tilde{\theta_{a}} = y\pi /Mθa~=yπ/M , which yields a~\tilde{a}a~ , the approximation of the aforementioned probability aaa :
a~=sin2(yπM)∈[0,1]\tilde{a} = sin^{2}(\frac{y\pi}{M}) \in [0,1]a~=sin2(Myπ)∈[0,1]
satisfying the following inequality:
∣a−a~∣≤πM+π2\M2=O(M−1)|a - \tilde{a}| \leq \frac{\pi}{M} + \frac{\pi^{2}}{\M^{2}} = O(M^{-1})∣a−a~∣≤Mπ+\M2π2=O(M−1)
with probability at least 8M2\frac{8}{M^2}M28 . Comparing with the O(M−12)O(M^{\frac{-1}{2}})O(M2−1) convergence rate of the classical Monte Carlo method, the quantum amplitude estimation method converges faster with a quadratic speed-up.
