Quantum search for a given substring in the text using a hashing technique

M.F. Ablayev^a,b∗ , N.M. Salikhova^b∗∗

^aZavoisky Physical-Technical Institute, FRC Kazan Scientific Center, Russian Academy of Sciences, Kazan, 420029 Russia

^bKazan Federal University, Kazan, 420008 Russia

E-mail: ^∗mablayev@gmail.com, ^∗∗nailyasalikhova66@gmail.com

Received July 23, 2020

Full text PDF

DOI: 10.26907/2541-7746.2020.3.241-258

For citation: Ablayev M.F., Salikhova N.M. Quantum search for a given substring in the text using a hashing technique. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 241–258. doi: 10.26907/2541-7746.2020.3.241-258. (In Russian)

Abstract

The problem of searching for a given substring in the text was considered. It is known that classical algorithms solve this problem in a linear time depending on the length of the text and the specified template. Quantum algorithms speed up the search by “square root times”.

In this paper, we proposed a quantum algorithm that solves the search problem a) with a high probability of getting the correct result and b) with the same acceleration (by “square root times”) as compared with the classical one, but it c) requires much less memory (based on the number of qubits used) than the previously known quantum algorithms.

Keywords: quantum algorithms, string search, quantum search

Acknowledgments. The study was supported by the Russian Science Foundation (project no. 19-19-00656).

References

1. Kitaev A., Shen’ A., Vyalyi M. Klassicheskie i kvantovye vychisleniya [Classical and Quantum Computation]. Moscow, MTsNMO, 1999. 192 p. (In Russian)
2. Grover L.K. A fast quantum mechanical algorithm for database search. Proc. 28th Annu. ACM Symp. on Theory of Computing, 1996, pp. 212–219. doi: 10.1145/237814.237866.
3. Gilliam A., Pistoia M., Gonciulea C. Optimizing quantum search using a generalized version of Grover’s algorithm. 2020, arXiv:2005.06468.
4. Brassard G., Hoyer P., Mosca M., Tapp A. Quantum amplitude amplification and estimation. In: Samuel J. Lomonaco Jr. (Eds.) AMS Contemporary Mathematics. 2002, vol. 305, pp. 53–74.
5. Reitzner D., Nagaj D., Buzek V. Quantum walks. 2012, arXiv:1207.7283.
6. Ablayev F., Ablayev M., Huang J.Zh., Khadiev K., Salikhova N., Wu D. On quantum methods for machine learning problems part I: Quantum tools. Big Data Min. Anal., 2019, vol. 3, no. 1, pp. 41–55. doi: 10.26599/BDMA.2019.9020016.
7. Ablayev F., Ablayev M., Huang J.Zh., Khadiev K., Salikhova N., Wu D. On quantum methods for machine learning problems part II: Quantum classification algorithms. Big Data Min. Anal., 2019, vol. 3, no. 1, pp. 56–67. doi: 10.26599/BDMA.2019.9020018.
8. Knuth D.E., Morris J.H. Jr., Pratt V.R. Fast pattern matching in strings. SIAM J. Comput., 1977, vol. 6, no. 2, pp. 323–350. doi: 10.1137/0206024.
9. Ramesh H., Vinay V. String matching in Õ(√n+√m) quantum time. J. Discrete Algorithms, 2003, vol. 1, no. 1, pp. 103–110. doi: 10.1016/S1570-8667(03)00010-8.
10. Ambainis A. Understanding quantum algorithms via query complexity. Proc. Int. Congr. of Mathematicians (ICM 2018), 2019, pp. 3265–3285. doi: 10.1142/9789813272880 0181.
11. Boyer M., Brassard G., Høyer P., Tapp A. Tight bounds on quantum searching. Fortschr. Phys.: Prog. Phys., 1998, vol. 46, nos. 4–5, pp. 493–505. doi: 10.1002/(SICI)1521-3978(199806)46:4/5¡493::AID-PROP493¿3.0.CO;2-P.
12. Zhang K., Korepin V.E. Examples on quantum search algorithm with optimized depth. Phys. Rev. A., 2020, vol. 101, no. 3, art. 032346, pp. 1–12. doi: 10.1103/Phys-RevA.101.032346.
13. Carter J.L., Wegman M.N. Universal classes of hash functions. J. Comput. Syst. Sci., 1979, vol. 18, no. 2, pp. 143–154. doi: 10.1016/0022-0000(79)90044-8.
14. Stinson D.R. Universal hashing and authentication codes. Des. Codes Cryptogr., 1994, vol. 4, pp. 369–380. doi: 10.1007/BF01388651.
15. Stinson D.R. Combinatorial techniques for universal hashing. J. Comput. Syst. Sci., 1994, vol. 48, no. 2, pp. 337–346. doi: 10.1016/S0022-0000(05)80007-8.
16. Ablayev F.M., Vasiliev A.V. Cryptographic quantum hashing. Laser Phys. Lett., 2013, vol. 11, no. 2, art. 025202, pp. 1–4. doi: 10.1088/1612-2011/11/2/025202.
17. Ablayev F., Ablayev M. On the concept of cryptographic quantum hashing. Laser Phys. Lett., 2015, vol. 12, no. 12, art. 125204, pp. 1–5. doi: 10.1088/1612-2011/12/12/125204.
18. Ablayev F.M., Ablayev M.F., Vasilev A.V. Universal quantum hashing. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2014, vol. 156, no. 3, pp. 7–18. (In Russian)
19. Macaluso A., Clissa L., Lodi St., Sartori C. Quantum Ensemble for Classification. 2020, arXiv:2007.01028.

The content is available under the license Creative Commons Attribution 4.0 License.