Introduction:

Research on the NISQ algorithm has died down around the world, and the development of the Fault-Tolerant-Quantum-Computer (FTQC) has started at IBM and Ion-Q, and research on algorithms in it, which was active in the 1990s, is becoming active again. Among the algorithms is quantum adiabatic computation. There are three types of Hamiltonians and eigenstates in the Schrodinger equation describing quantum systems: 1) when the Hamiltonian is time-independent and commutative, the solution is the product of the state and the time evolution operator; 2) when the Hamiltonian is time-dependent and commutative, the solution is the product of the state and the time evolution 3) If the Hamiltonian is time-dependent and non-commutative with respect to time, the solution is the product of the time evolution term and the Dyson series. The adiabatic quantum calculation deals with the case 2. In this article, I will explain the adiabatic quantum calculation.

Method:

If some coefficient changes with time, including the case where the Hamiltonian is time-dependent, the order of the levels may be reversed. In this case, the superposition of states occurs between the crossed states depending on the speed at which the levels cross. It has been proven that this does not happen if the speed of crossing is infinitely slow (quasi-static). This is the quantum adiabatic theorem. As shown in Fig. 1, in a quasistatic process, only the state changes in the master state, the energy levels starting from the ground state do not change, and if the state is in the first excited state, it settles to the ground state without superposition. In quantum adiabatic calculations, this is used to prepare Hamiltonian sums of the starting and final states, and the coefficients between them are varied quasi-statically, and the algorithm calculates the time variation of the state and the final state and eigenstates.

$H_{tot}=(1-t/T)H_{i}+t/T H_{f}$ -(1)

Since this is an algorithm that is possible with both quantum annealing and gates, there are many different ways to implement it for a single problem. In this article, we will implement Grover's algorithm in adiabatic quantum computation and show the results and the problems involved.

Fig. 1: Time evolution in adiabatic quantum computation. Where level crossing occurs, no state crossing occurs, and no superposition of existence probabilities occurs.

Adiabatic Grover's Algorithm:

Grover's algorithm is a fast and searchable algorithm that uses quantum superposition. It uses oracle operators in its original implementation in gates, but is not needed in quantum adiabatic calculations. Therefore, $H_{i}$ and $H_{f}$ are as follows

$H_{i}=I-\mid \psi \rangle \langle \psi \mid$

$H_{f}=I-\mid m \rangle \langle m \mid$ }-(2)

where $\mid \psi\rangle=\sum_{j=0}1/\sqrt{2^n}\mid j\rangle$ is the superposition of all states, and $\mid m\rangle=\sum_{j=0,j\neq i}1/\sqrt{2^n-1}\mid j\rangle$ is the superposition of all states except $\mid i\rangle$ . However, we need to be a little creative. The following operators

$Auu=\frac{1}{2}(I+Z),Add=\frac{1}{2}(I-Z),Aud=\frac{1}{2}(X-iY),Adu=\frac{1}{2}(X+iY)$ -(3)

will be used for calculation on $H_{f}$ . Using them, in case $\mid 0100 \rangle$ is the correct state,

$H_{f}=\frac{1}{2^n-1}[\prod_{j=0}^{n-1}X_j-({(Auu_0+Adu_{0})(Aud_{1}+Add_{1})(Auu_{2}+Adu_{2})(Auu_{3}+Adu_{3})+(Auu_0+Aud_0)(Adu_1+Add_1)(Auu_2+Adu_2)(Auu_3+Aud_3)})+Auu_0 Add_1 Auu_2 Auu_3]$ -(4).

The first of these terms is the same as $H_{i}$ . The second term is to cancel out the solution state, and the third term is to adjust. Since the Hamiltonian is expressed as a sum, the Trotter expansion decomposes the time evolution operator $exp(-iH_{tot}(s)t)$ into a product of each term. In addition, I assume t as an technic in paper [1],

$t=\frac{1}{2\epsilon}\frac{N}{\sqrt{N-1}}(tan^{-1}(\sqrt{N-1}(N-1))+tan^{-1}\sqrt{N-1})$ -(5).

Thus, based on the equation (2), we can change the value of s from 0 to 1 and run the time evolution circuit (see this blog) to perform the calculation.

Result:

This time, s was varied in increments of 0.01, the error tolerance ϵ was set to 0.01, 0100 was used as the solution, and the depth of the Trotter-expanded Hamiltonian was calculated as 1. The calculation results are shown in Figs. 2 and 3. The probability of existence in the solution state increases from uniform superposition to 1 at s=0.6 and 0.9. The existence probabilities in the other states are correspondingly small. However, the energy level in the ground state increased with increasing s from about 0.93. This is because all the states except ground and first excited states degenerate, which means that it has mixed with the ground state to become more than one. The reason it is not linearly increasing is because the rate of change of t changes. In the usual Grover algorithm, if you multiply the Grover operator too much, the existence probability of the solution state will decrease. In the same way, the existence probability of the solution state will decrease if we vary it for too long. However, it is expected that the existence probability of the solution state will become 1 in a certain period of time.

Fig. 2: Time evolution of existence probability in each state.

Fig. 3: Time evolution of energy in the ground state.

In quantum adiabatic calculation, the number of applied gates increases as s increases, which makes the calculation more susceptible to errors. In the worst case, the computation time will be as long as that of a classical computer, even if it is used in FTQC. However, adiabatic quantum computation is interesting from an academic point of view and has the potential to be developed.

Contest Blog: Adiabatic Grover's Algorithm[Supplemental Information] by Hikaru Wakaura | blueqat

Contest Blog: Adiabatic Grover's Algorithm[source] by Hikaru Wakaura | blueqat

[1] Jelemie Roland and Nicholas J. Chef, arXiv[quant-ph], 010701v1(2001)