Quantum Amplitude Estimation

Rag9704 May 24

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

Suppose given a unitary transformation, AA , which is a quantum algorithm, unlike making measurement in the case of classical PP algorithm, this produces a quantum superposition state of the “desired” result that X(x,P(x))=1X (x,P(x)) = 1 X and “undesired” result that X(x,P(x))1X (x,P(x)) \neq 1. Then amplitude estimation is the problem of estimating aa , the probability that a measurement of Ψi\ket{\Psi_{i}} yields a good solution. It is sufficient to evaluate AA and XX in an expected number of times that is proportional to 1/a1/\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_{-} :

A0=ψ=i2(\eiθaψ++\eiθaψ)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 “aa ” is converted to the solution of angle θa\theta_{a} that decides the eigenvalue for unitary transformation AA

Apply an operator QQ to AA

Q=AS0ASψ0Q = AS_{0}\dagger{A}S_{\psi 0}

where S0=1200S_{0} = 1 - 2\ket{0}\bra{0} , and Sψ0=12ψ00ψ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ψ0S_{\psi 0} , and then rotates along ψ+\psi_{+} by the operator S0S_{0}. Therefore, the angle between the arbitrarily set initial state and the final state after the operator QQ becomes 2θa2\theta_{a} . In this case, when the initial state is AA , operator QQ just shifts from ψ\ket{\psi} for 2θa2\theta_{a}

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

Firstly, the Hamamard gates prepare the mm qubits in the uniform superposition:

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

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


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


By taking measurement on the register of mm qubits, we can get the approximation of θa\theta_{a}. This is done by obtaining the measured integery0,1,2,...,2m1y \rightarrow {0,1,2,..., 2^{m}-1} . TakingM=2mM = 2^{m} , then θa\theta_{a} can be approximated as θa~=yπ/M\tilde{\theta_{a}} = y\pi /M , which yields a~\tilde{a} , the approximation of the aforementioned probability aa :

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

satisfying the following inequality:

aa~πM+π2\M2=O(M1)|a - \tilde{a}| \leq \frac{\pi}{M} + \frac{\pi^{2}}{\M^{2}} = O(M^{-1})

with probability at least 8M2\frac{8}{M^2} . Comparing with the O(M12)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.

Related posts

blueqat Inc.

Shibuya Scramble Square 39F 2-24-12, Shibuya, Shibuya-ku, Tokyo
Contact: info@blueqat.com