Analysis of grover’s quantum search algorithm on a classical computer: Identifying opportunities for improvement

Year 2024, Volume: 42 Issue: 4, 1039 - 1049, 01.08.2024

Necati Çelik , Özkan Bingöl

Abstract

In this paper, Grover’s quantum search algorithm is analyzed using a classical computer by calculating the amplitudes and the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, and 27 qubit states. The calculations show that the marked state can be found in iterations, where N = 2n is the number of items. The possibility of improving Grover’s search algorithm to find a single item in N search elements is discussed by calculating the amplitudes and hence the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, 30, 35, 40, 45, and 50 qubit states. The calculations showed that the marked state could be found with sufficiently high probability in (ln(N)) iterations. This is quite a remarkable speed-up that can be achieved to find a single marked element in an unsorted N search element.

Keywords

Grover’s Search Algorithm, Quantum Information Processing, Quantum Information, Qubit, State Vector

References

• [1] Grover LK. Quantum mechanics helps in searching for a needle in a haystack. Phys Rev Lett 1997;79:325. [CrosssRef]
• [2] Biham E, Biham O, Biron D, Grassl M, Lidar DA, Shapira D. Analysis of generalized Grover quantum search algorithms using recursion equations. Phys Rev A 2000;63:012310. [CrosssRef]
• [3] Arqub OA, Abo-Hammour Z. Numerical solution of systems of second-order boundary value problems using continuous genetic algorithm. Inf Sci 2014;279:396415. [CrosssRef]
• [4] Abo-Hammour ZE, Alsmadi O, Momani S, Abu Arqub O. A genetic algorithm approach for prediction of linear dynamical systems. Math Probl Eng 2013;2013:831657. [CrosssRef]
• [5] Abo-Hammour Z, Abu Arqub O, Momani S, Shawagfeh N. Optimization solution of Troesch’s and Bratu’s problems of ordinary type using novel continuous genetic algorithm. Discrete Dyn Nat Soc 2014;2014:401696. [CrosssRef]
• [6] Abu Arqub O, Abo-Hammour Z, Momani S, Shawagfeh N. Solving singular two-point boundary value problems using continuous genetic algorithm. Abstr Appl Anal 2012;2012:205391. [CrosssRef]
• [7] Kelleche A, Tatar NE. Control and exponential stabilization for the equation of an axially moving viscoelastic strip. Math Meth Appl Sci 2017;40:62396253. [CrosssRef]
• [8] Kelleche A, Tatar NE. Adaptive Stabilization of a Kirchhoff moving string. J Dyn Control Syst 2020;26:255263. [CrosssRef]
• [9] Kelleche A, Tatar NE. Existence and stabilization of a Kirchhoff moving string with a distributed delay in the boundary feedback. Math Model Nat Phenom 2017;12:106117. [CrosssRef]
• [10] Kaye P, Laflamme R, Mosca M. An Introduction to Quantum Computing. Oxford, London: OUP; 2006.
• [11] Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev 1999;41:303332. [CrosssRef]
• [12] Qiu D, Zheng S. Revisiting Deutsch-Jozsa algorithm. Inf Comput. 2020;275:104605.
• [13] Deutsch D, Jozsa R. Rapid solution of problems by quantum computation. Proc R Soc Lond A Math Phys Sci 1992;439:553558. [CrosssRef]
• [14] Kiktenko EO, Fedorov AK, Strakhov AA, Man'Ko VI. Single qudit realization of the Deutsch algorithm using superconducting many-level quantum circuits. Phys Lett A 2015;379:14091413. [CrosssRef]
• [15] Chuang IL, Gershenfeld N, Kubinec M. Experimental implementation of fast quantum searching. Phys Rev Lett 1998;80:3408. [CrosssRef]
• [16] Chuang IL, Vandersypen LM, Zhou X, Leung DW, Lloyd S. Experimental realization of a quantum algorithm. Nature 1998;393:143146. [CrosssRef]
• [17] Feng M. Grover search with pairs of trapped ions. Phys Rev A 2001;63:052308. [CrosssRef]
• [18] Brickman KA, Haljan PC, Lee PJ, Acton M, Deslauriers L, Monroe C. Implementation of Grover’s quantum search algorithm in a scalable system. Phys Rev A 2005;72:050306. [CrosssRef]
• [19] Xu ZY, Feng M. Addendum to “Grover search with pairs of trapped ions”. Phys Rev A 2008;78:014301.
• [20] Yang WL, Wei H, Zhou F, Chang WL, Feng M. Solution to the satisfiability problem using a complete Grover search with trapped ions. J Phys B At Mol Opt Phys 2009;42:145503. [CrosssRef]
• [21] Dewes A, Lauro R, Ong FR, Schmitt V, Milman P, Bertet P, et al. Quantum speeding-up of computation demonstrated in a superconducting two-qubit processor. Phys Rev B 2012;85:140503. [CrosssRef]
• [22] Dewes A, Ong FR, Schmitt V, Lauro R, Boulant N, Bertet P, et al. Characterization of a two-transmon processor with individual single-shot qubit readout. Phys Rev Lett 2012;108:057002. [CrosssRef]
• [23] Filipp S, Maurer P, Leek PJ, Baur M, Bianchetti R, Fink JM, et al. Two-qubit state tomography using a joint dispersive readout. Phys Rev Lett 2009;102:200402. [CrosssRef]
• [24] Yamaguchi F, Milman P, Brune M, Raimond JM, Haroche S. Quantum search with two-atom collisions in cavity QED. Phys Rev A 2002;66:010302. [CrosssRef]
• [25] Wang H, Zhang S, Yeon KH. Implementation of Grover quantum search via cavity quantum electrodynamics. J Korean Phys Soc 2008;53:3144150. [CrosssRef]
• [26] Yang WL, Chen CY, Feng M. Implementation of three-qubit Grover search in cavity quantum electrodynamics. Phys Rev A 2007;76:054301. [CrosssRef]
• [27] Hua M, Tao MJ, Deng FG. Fast universal quantum gates on microwave photons with all-resonance operations in circuit QED. Sci Rep 2015;5:18.
• [28] Szabłowski PJ. Understanding mathematics of Grover’s algorithm. Quantum Inf Process 2021;20:121. [CrosssRef]
• [29] Han Q. Several remarks on Grover's quantum search algorithm with a single marked element. Sch J Phys Math Stat 2021;3:6267. [CrosssRef]
• [30] Cohn I, De Oliveira ALF, Buksman E, De Lacalle JG. Grover’s search with local and total depolarizing channel errors: Complexity analysis. Int J Quantum Inf 2016;14:1650009. [CrosssRef]
• [31] Xiao H, Huang WH, Zhou M. An efficient quantum private query protocol based on Oracle and Grover iteration. Int J Theor Phys 2019;58:30253035. [CrosssRef]
• [32] Nielsen MA, Chuang I. Quantum Computation and Quantum İnformation. Cambridge: Cambridge University Press; 2002. [CrosssRef]
• [33] Get a Trial of MATLAB and Simulink Product. Accessed onJul 12, 2024. Available at: https://uk.mathworks.com/
• [34] D'Errico J. HPF - a big decimal class. MATLAB Central File Exchange. Accessed on Jan 10, 2022. Available at: https://www.mathworks.com/matlabcentral/fileexchange/36534-hpf-a-big-decimal-class