M.F. Ablayeva,b∗ , N.M. Salikhovab∗∗
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
- Kitaev A., Shen’ A., Vyalyi M. Klassicheskie i kvantovye vychisleniya [Classical and Quantum Computation]. Moscow, MTsNMO, 1999. 192 p. (In Russian)
- 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.
- Gilliam A., Pistoia M., Gonciulea C. Optimizing quantum search using a generalized version of Grover’s algorithm. 2020, arXiv:2005.06468.
- 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.
- Reitzner D., Nagaj D., Buzek V. Quantum walks. 2012, arXiv:1207.7283.
- 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.
- 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.
- 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.
- 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.
Ambainis A. Understanding quantum algorithms via query complexity. Proc. Int. Congr. of Mathematicians (ICM 2018), 2019, pp. 3265–3285. doi: 10.1142/9789813272880 0181.
- 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.
- 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.
- 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.
- Stinson D.R. Universal hashing and authentication codes. Des. Codes Cryptogr., 1994, vol. 4, pp. 369–380. doi: 10.1007/BF01388651.
- 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.
- 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.
- 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.
- 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)
- Macaluso A., Clissa L., Lodi St., Sartori C. Quantum Ensemble for Classification. 2020, arXiv:2007.01028.
![](http://kpfu.ru/docs/F46869432187/img608337246.jpg)
The content is available under the license Creative Commons Attribution 4.0 License.