Quantum search in a dictionary using fingerprinting function
https://doi.org/10.26907/2541-7746.2025.1.115-124
Abstract
The problem of searching for an element within a dictionary was considered. Over the past decades, various approaches, including classical and quantum algorithms, have been proposed to solve it. One possible solution is the method of quantum amplitude amplification, which underpins the well-known Grover algorithm and enables a quadratic speedup in the search process.
In this article, a new approach to searching for an element w of length m in a dictionary V of size n with the use of the quantum fingerprinting function was introduced. The developed algorithm has a query complexity of O(√n) and requires O(logn+logm) qubits.
About the Author
N. M. Salikhova
Kazan Federal University
Russian Federation
Russian Federation
Nailya M. Salikhova, Postgraduate Student
Kazan
References
1. Grover L.K. A fast quantum mechanical algorithm for database search. STOC’96: Proc. 28th Annu. ACM Symp. on Theory of Computing. Philadelphia, PA, ACM, 1996, pp. 212–219. https://doi.org/10.1145/237814.237866.
2. Brassard G., Høyer P., Mosca M., Tapp A. Quantum amplitude amplification and estimation. In: Quantum Computation and Information. Ser.: Contemporary Mathematics. Vol. 305. Providence, RI, Am. Math. Soc., 2002, pp. 53–74. http://dx.doi.org/10.1090/conm/305/05215.
3. Kaye P., Laflamme R., Mosca M. An Introduction to Quantum Computing. New York, NY, Oxford Univ. Press, 2007. 274 p.
4. Ablayev F., Ablayev M., Huang J.Z., Khadiev K., Salikhova N., Wu D. On quantum methods for machine learning problems. Part I: Quantum tools. Big Data Min. Anal., 2020, vol. 3, no. 1, pp. 41–55. https://doi.org/10.26599/BDMA.2019.9020016.
5. Ablayev F., Ablayev M., Huang J.Z., Khadiev K., Salikhova N., Wu D. On quantum methods for machine learning problems. Part II: Quantum classification algorithms. Big Data Min. Anal., 2020, vol. 3, no. 1, pp. 56–67. https://doi.org/10.26599/BDMA.2019.9020018.
6. Ablayev F., Salikhova N., Ablayev M. Hybrid classical–quantum text search based on hashing. Mathematics, 2024, vol. 12, no. 12, art. 1858. https://doi.org/10.3390/math12121858.
7. Buhrman H., Cleve R., Watrous J., de Wolf R. Quantum fingerprinting. Phys. Rev. Lett., 2001, vol. 87, no. 16, art. 167902. https://doi.org/10.1103/PhysRevLett.87.167902.
Review
For citations:
Salikhova N.M. Quantum search in a dictionary using fingerprinting function. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2025;167(1):115-124. (In Russ.) https://doi.org/10.26907/2541-7746.2025.1.115-124
Views:
106
Email this article 