In this entry, I present you the method to implement the numerical integration using quantum computer presented by the group of Dr. Abrams[1]. Quantum Amplitude Amplification(QAA) algorithm is normalized form of Grover's search algorithm. QAA can be used for various types of algorithms. Numerical Integration is one of them. Therefore, I will present you the essence of QAA.

Required knowledge:

Basic knowledge of controlled-NOT, Pauli gates and rotation gates are required. Ability to make the quantum circuit. Familiarity with Dirac notation.

Quantum Amplitude Amplification Algorithm

QAA algorithm acts the appended oracle gate and repeater gate one after another while aimed state is amplified at a maximum. The mainframe of this algorithm is as follows.

1, Prepare n working bits and 1 ancilla bits.

2, Assume aimed state $\mid \Psi_0 \rangle$ and other states $\mid \Psi_1 \rangle$ , act $A∣0⟩_{n+1} =sinθ∣Ψ _0 ⟩+cosθ∣Ψ _1 ⟩$ on n+1 qubit initial state $\mid 0 \rangle_{n+1}$ .

3, Act appended oracle $G_{\Psi_0}=A^{\dagger}OA$ and repeater $G_A=A^{\dagger}(2\mid 0 \rangle_n ~_n\langle 0 \mid - I)A$ one after another times.

4, Measure $\mid \Psi_0 \rangle$ .

Quantum Circuit is as Fig. 1. Both appended oracle and repeater are similar to those of Grover's search algorithm.

Fig. 1 Quantum circuit of QAA algorithm.

Numerical integration on classical computers

Classical computers can only deal with discrete data. Hence, integration must be treated by sequential mensuration. Sequential mensuration is the method to derive the value of finite-bound integration by separating the boundary of integration and sum up the each area as shown in Fig. 2. It can be expressed as,

-(1)

in case x has only one dimension. This can be derived by also quantum computers.

Fig. 2 Image of sequential mensuration.

Numerical integration using quantum computers

In this chapter I describe the method to derive the sequential mensuration $S(f)$ by QAA algorithm. The method for this are presented by three groups. The oldest the group of Dr. Abrams presented uses QAA algorithm. I implemented the method and calculated the value of $S(f)$ . This method calculates the estimated value of $S(f)$ and deviation realm. After that, estimated value of $S(f)$ is refined by calculating the refining value by QAA method in deviation realm as shown in Fig. 3.

Fig. 3 The method of numerical integration using QAA proposed by Dr. Abram's group.

The deviation realm on k-th calculation is $S_{k-1}(f)-\epsilon_{k-1}/2<S(f)<S_{k-1}(f)-\epsilon_{k-1}/2$ .

$B=(P^\dagger \otimes I)R(P\otimes I)$

$P\mid 0 \rangle = \sum_{x=0}^{2^n - 1}\sqrt{p(x)}\mid x \rangle$ }-(2)

$R\mid x \rangle \mid 0 \rangle = \mid x \rangle (\sqrt{f(x)}\mid 0 \rangle + \sqrt{1 - f^2(x)}\mid 1 \rangle)$

Then, f(x) is the f(x) in eq.(1). By act $B$ on $\mid 0 \rangle_{n+1}$ , the state becomes,

$B\mid 0 \rangle_{n+1}=\sum_{x=0}^{2^n-1}p(x)f(x)\mid 0 \rangle + \cdots$ . -(3)

The value of $S_1(f)$ can be obtained by measurement of state $\mid 0 \rangle$ . $f_2(x)$ and $D_2(f)$ are calculated complying,

$f_k(x)=f(x)-(S_{k-1}(f)-\epsilon_{k-1}/2)$

$D_k(f)=\sum_{x=0}^{2^n-1}p(x)f_k(x)$ . }-(4)

Then, $$ $\epsilon_{k-1}$ is deviation realm on k-th calculation. Using, $A=B_k$ refinement gate $B_k(f)$ is derived by QAA that the number of acting $G_{\Psi_0}G_A$ is $j_k$ that follows,

$(2j_k + 1)sin^{-1}\epsilon_k = \pi / 2$ . -(5)

Hence, $S_k(f)$ for $k\geq 2$ is,.

$S_k(f)=S_{k-1}(f)+\epsilon_k(D_k(f)-\frac{1}{2})$ . -(6)

For example of $S(f)=sin^2\theta$ , f(x) is $sin2/(2^n - 1)x\theta$ . $f_k(x)$ can be represented as,

$2\delta_k = sin^{-1}(\epsilon_{k-1}/2 - S_{k-1}(f))$

$f_k(x)=2sin(\frac{1}{2^n-1}x\theta + \delta_k)cos(\frac{1}{2^n-1}x\theta - \delta_k)$ . -(7)

Then, $\epsilon_k = 1/(2(2(j_k + 1)\sqrt{N_1})$ for the number of shot of quantum circuit $N_1$ same as paper [1]. $B_k$ can be implemented by the circuit on Fig. 4.

Fig. 4 Quantum circuit that implements $B$ . As for $B_k$ , $R_y$ gates for cos are added.

Fig. 5 shows the result of calculation in case $\theta=\pi/2$ and $N_1=25$ . $S_k(f)$ can be close to exact value. However, deviation realm drops the exact value in case $k \geq 3$ . It must include the exact value while $S_k(f)$ converges in exact one.

Fig. 5 The value of $S_k$ for k. $\epsilon_d$ and $\epsilon_u$ indicate the lower and upper bound of deviation realm, respectively. "exact" indicates the exact value obtained by sequential mensuration on classical computer.

This algorithm can increase the number of sequence in $2^n$ order by increasing the number of qubits. Though, the function to be integrated must be represented by the product of periodic functions, the calculation accuracy can be far higher than that of classical computers. The functions those have been studied intensively are periodic and insolvable by classical computers in the times of polynomial order. Hence, this method have the potential to solve them.

[1] D. S. Abrams and C. P. Williams. Fast quantum algorithms for numerical integrals and stochastic processes. arXiv:quant-ph/990808(1999)

Quantum Numerical Integration using Quantum Amplitude Amplification.

Hikaru Wakaura