DESIGN OF GROVER'S QUANTUM SEARCH ALGORITHM FOR 2-KBIT STATES

ABSTRACT

Quantum theory explains this behavior and gives us a more complete picture of our universe. We have realized we can use this previously unexplained behavior to perform certain computations that we previously did not believe possible. We call this quantum computing. You have likely heard that one of the many advantages a quantum computer has over a classical computer is its superior speed searching databases. Grover's algorithm demonstrates this capability. This algorithm can speed up an unstructured search problem quadratically, but its uses extend beyond that; it can serve as a general trick or subroutine to obtain quadratic run time improvements for a variety of other algorithms.

АННОТАЦИЯ

Квантовая теория объясняет такое поведение и дает нам более полную картину нашей Вселенной. Мы поняли, что можем использовать это ранее необъяснимое поведение для выполнения определенных вычислений, которые раньше мы считали невозможными. Мы называем это квантовыми вычислениями. Вы, вероятно, слышали, что одним из многих преимуществ квантового компьютера перед классическим компьютером является его превосходная скорость поиска в базах данных. Алгоритм Гровера демонстрирует эту возможность. Этот алгоритм может квадратично ускорить задачу неструктурированного поиска, но его возможности выходят за рамки этого; он может служить общим трюком или подпрограммой для получения квадратичного улучшения времени выполнения для множества других алгоритмов.

Keywords: Grover's quantum search algorithm, Quantum search, Oracle, Qubit, Adamar transform, Phase shift.

Ключевые слова: алгоритм квантового поиска Гровера, квантовый поиск, оракул, кубит, преобразование Адамара, фазовый сдвиг.

Quantum search algorithms are the algorithms that may be applied to speed up the majority of classical searching algorithms. Grover’s search algorithm completes general searching to find a potential solution to a very wide range of problems [1-2]. In other words, it is the algorithm that search the results until the simple strategy for uncomplicated states is found. In a classical way, the solution of this problem demands to complete  operations, but Grover’s search algorithm does it by completing  operations, where state probability is

Grover’s algorithm begins with quantum register of the qubits , here  - the number of qubits that are needed to represent a search space of size , all starting from :

                                                                  (1)

The first step is to place the process states in an equal superposition, which is done by using the Hadamard conversion, where the operations ,  practical initial Hadamard gate, i.e. it appears in the form of equation (2):

                                                      (2)

The following series of transforms are usually called Grover’s iteration and the abovementioned amplitude amplifier carries out the main part of algorithm. In Grover’s algorithm the iteration iterates  times. According to this algorithm, because the observed state is true, in order to reach an optimal probability the total rotation of the space   happens after average rotation so that the former becomes radian [5-6].

The first step in Grover's iteration is an appeal to the quantum oracle , which modifies the system depending on the configuration it is looking for. An oracle is basically a black box function, and it's a quantum black box, which means it can observe and change the system without falling into a classical state that admits that the system is in the right state. If the system is indeed in the correct state, then the oracle rotates the space by radians , otherwise it does not anything and effectively defines the correct state for further modification by subsequent processes. It is important to remember that such kind of a spatial shift conducts no changes in the correct state probability of the system leaving it the same, even though the amplitude is negated.  Oracle's quantum programs often use an extra drawing qubit, but this extra qubit is unnecessary, so the effect of the oracle on  can simply be written in the form of (3), i.e.:

                                                            (3)

here, if  , then , otherwise . The exact implementation of  depends on a particular search problem [8].

Implementation process with 2 qubits. Imagine that , possible states are  and the solution is in 3-index, i.e. let’s say it is found in state , then we acquire the following state:

                                                       (7)

By doing so, the impact of oracle operator on state  changes its amplitude. When Hadamard conversion  is applied through these indexes the result will be as the following:

                                                   (8)

Now, in each calculation state except from it, a conditional phase shift  is implemented. By doing so, we will get the following form:

                                                    (9)

Hadamard conversion  is again applied to the acquired superposition states, then the value corresponding to the index is acquired, and it will be as following for our task:

                                                                            (10)

By doing so, when for state , we reached a necessary search with one iteration of Grover’s algorithm. In figure 1, a quantum scheme is presented for a 2-qubit system with 22 gates. The scheme of the 2-qubit system never leads to an error. The vector expression and measurement probability for the 2-qubit state are shown in Figure 2 and Figure 3, respectively [6-7].

Figure 1. Quantum scheme

Figure 2. A vector expression for a 2-qubit state

Figure 3. The chart of measurement probability for a 2-qubit state

Conclusion

In conclusion, it was considered to what extend given information about object of the research is used purposefully in the modeling process, as a result of mathematical analysis of Grover’s method of the quantum algorithm, i.e. it is important to provide the adequacy of the model. The results of the optimization performed with the quantum algorithm based on Grover's method are presented [9].

It is important to use the Grover quantum search algorithm, which works faster than classical computing, in solving the listed problems. We have reviewed Grover's quantum search algorithm on the example of designing 2- and 3-qubit systems and provided analysis of the number of gates used in the implementation, vector representation, and measurement probability. We used QCAD tool to solve this problem. In addition, we presented operational steps of the algorithm in 2- and 3-qubit systems as a theoretical recommendation. In the future, we have planned to design the scenario of using search algorithm for real time systems [10].

References:

1. Priya R. P. Baradeswaran A. “An efficient simulation of quantum error correction Codes”, Alexandria Engineering Journal, Vol. 57, pp. 2167–2175, 2018. [in English].
2. Chen G. Fulling S. A.and Scully M. O. “Grover’s Algorithm for Multiobject Search in Quantum Computing”, Article in Lecture Notes in Physics, pp. 1-12, 1999. [in English].
3. Hahanov V., Miz V. “Quantum computing approach for shortest route finding”, East-West Design & Test Symposium (EWDTS 2013), Rostov-on-Don, Russia, pp. 27-30, 2013. [in English].
4. Kaye P., Laflamme R., Mosca M. “An Introduction to Quantum Computing”, Oxford University Press Inc., New York, pp. 1-276, 2007. [in English].
5. Nielsen M. A. and Chuang I. L. “Quantum Computation and Quantum Information”, Cambridge University Press, New York, pp. 1-676, 2010. [in English].
6. Mandviwalla A., Ohshiro K., Ji B. “Implementing Grover’s Algorithm on the IBM Quantum Computers”, 2018 IEEE Int. Conf. on Big Data, 2018. [in English].
7. Samsonov E., Kiselev F., Shmelev Y., Egorov V., Goncharov R., Santev A., Pervushin B. and Gleim A., “Modeling two-qubit Grover's algorithm implementation in a linear optical chip”, PhysicaScripta, vol. 95, no. 4, 2020. [in English].
8. Toirov Sh., Narmuradov U. Processes of applying of quantum genetic algorithm in function optimization // American Institute of Physics: Conference Proceedings. -USA-Vol. 2365. -P.1-6, 2021. [in English].
9. Sh. A. Toirov, I. M. Boynazarov, Sh. A. Abatov, B. M. Mirsaidov, Z. Ruziyeva Optimization with quantum algorithm that is based on grover’s method. Communications in computer and information science journal. (CCIS, volume 1821), pp 76–86. [in English].