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

Necati Çelik; Özkan Bingöl

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

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

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

Details

Primary Language

English

Subjects

Structural Biology

Journal Section

Research Article

Authors

Necati Çelik ^*
0000-0002-8270-9288
Türkiye

Özkan Bingöl
Türkiye

Publication Date

August 1, 2024

Submission Date

February 4, 2023

Acceptance Date

May 30, 2023

Published in Issue

Year 2024 Volume: 42 Number: 4

IZ

https://izlik.org/JA88WE22BS

Cite

RIS / Bibtex

APA

Çelik, N., & Bingöl, Ö. (2024). Analysis of grover’s quantum search algorithm on a classical computer: Identifying opportunities for improvement. Sigma Journal of Engineering and Natural Sciences, 42(4), 1039-1049. https://izlik.org/JA88WE22BS

AMA

1.Çelik N, Bingöl Ö. Analysis of grover’s quantum search algorithm on a classical computer: Identifying opportunities for improvement. SIGMA. 2024;42(4):1039-1049. https://izlik.org/JA88WE22BS

Chicago

Çelik, Necati, and Özkan Bingöl. 2024. “Analysis of Grover’s Quantum Search Algorithm on a Classical Computer: Identifying Opportunities for Improvement”. Sigma Journal of Engineering and Natural Sciences 42 (4): 1039-49. https://izlik.org/JA88WE22BS.

EndNote

Çelik N, Bingöl Ö (August 1, 2024) Analysis of grover’s quantum search algorithm on a classical computer: Identifying opportunities for improvement. Sigma Journal of Engineering and Natural Sciences 42 4 1039–1049.

IEEE

[1]N. Çelik and Ö. Bingöl, “Analysis of grover’s quantum search algorithm on a classical computer: Identifying opportunities for improvement”, SIGMA, vol. 42, no. 4, pp. 1039–1049, Aug. 2024, [Online]. Available: https://izlik.org/JA88WE22BS

ISNAD

Çelik, Necati - Bingöl, Özkan. “Analysis of Grover’s Quantum Search Algorithm on a Classical Computer: Identifying Opportunities for Improvement”. Sigma Journal of Engineering and Natural Sciences 42/4 (August 1, 2024): 1039-1049. https://izlik.org/JA88WE22BS.

JAMA

1.Çelik N, Bingöl Ö. Analysis of grover’s quantum search algorithm on a classical computer: Identifying opportunities for improvement. SIGMA. 2024;42:1039–1049.

MLA

Çelik, Necati, and Özkan Bingöl. “Analysis of Grover’s Quantum Search Algorithm on a Classical Computer: Identifying Opportunities for Improvement”. Sigma Journal of Engineering and Natural Sciences, vol. 42, no. 4, Aug. 2024, pp. 1039-4, https://izlik.org/JA88WE22BS.

Vancouver

1.Necati Çelik, Özkan Bingöl. Analysis of grover’s quantum search algorithm on a classical computer: Identifying opportunities for improvement. SIGMA [Internet]. 2024 Aug. 1;42(4):1039-4. Available from: https://izlik.org/JA88WE22BS