Grover’s algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grover’s algorithm is T = O(
). This paper introduces two new algorithms for Amplitude Amplification in Grover’s algorithm with a time complexity of T = O(logN), aiming to improve efficiency in quantum computing. The difference between Grover’s algorithm and our first algorithm is that the Amplitude Amplification ratio in Grover’s algorithm is an arithmetic series and ours, a geometric one. Because our Amplitude Amplification ratios converge much faster, the time complexity is improved significantly. In our second algorithm, we introduced a new concept, Amplitude Transfer where the marked state is transferred to a new set of qubits such that the new qubit state is an eigenstate of measurable variables. When the new qubit quantum state is measured, with high probability, the correct solution will be obtained.
References
[1]
Nielsen, M.A. and Chuang, I.L. (2010) Quantum Computation and Quantum Information. Cambridge University Press, Cambridge.
[2]
Rieffel, E. and Polak, W. (2011) Quantum Computing: A Gentle Introduction. The MIT Press, Cambridge.
[3]
Johnston, E.R., Harrigan, N. and Gimeno-Segovia, M. (2019) Programming Quantum Computers: Essential Algorithms and Code Samples. O’Reilly Media, Sebastopol.
Aaronson, S. (2013) Quantum Computing Since Democritus. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511979309
[6]
Grover, L.K. (1996) A Fast Quantum Mechanical Algorithm for Database Search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC ‘96), 212-219. https://doi.org/10.1145/237814.237866
[7]
Berti, A. (2022) Behind Oracles: Grover’s Algorithm. https://towardsdatascience.com/behind-oracles-grovers-algorithm-amplitude-amplification-46b928b46f1e
[8]
Shirgure, S. (2024) Solving the Subset Sum Problem on a Quantum Computer. https://sumeetshirgure.github.io/assets/pdfs/presentations/ee_520.pdf
[9]
Arora, S. and Barak, B. (2009) Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511804090
Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York.
[12]
Sipser, M. (2012) Introduction to the Theory of Computation. Cengage Learning, Boston.
[13]
Liu, Y. (2024) Time Complexity of the Oracle Phase in Grover’s Algorithm. American Journal of Computational Mathematics, 14, 1-10. https://doi.org/10.4236/ajcm.2024.141001
[14]
Nield, D. (2024) Google Quantum Computer Is ‘47 Years’ Faster Than #1 Supercomputer. Science Alert. https://www.sciencealert.com/google-quantum-computer-is-47-years-faster-than-1-supercomputer