Квантовый поиск заданной подстроки в тексте на основе техники хеширования

М.Ф. Аблаев1,2 , Н.М. Салихова2

1Казанский физико-технический институт им. Е.К. Завойского ФИЦ Казанский научный центр РАН, г. Казань, 420029, Россия

2Казанский ( Приволжский ) федеральный университет, г. Казань, 420008, Россия

Полный текст PDF
DOI: 10.26907/2541-7746.2020.3.241-258

Для цитирования: Аблаев М.Ф., Салихова Н.М. Квантовый поиск заданной под строки в тексте на основе техники хеширования // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 3. – С. 241–258. – 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)

Аннотация

Рассмотрена задача поиска в тексте заданной подстроки. Известно, что классические алгоритмы решают эту задачу за линейное от длины текста и заданного шаблона время. Квантовые алгоритмы позволяют ускорить поиск в «корень квадратный раз».

В работе предложен квантовый алгоритм, решающий задачу поиска а) с высокой вероятностью получения правильного результата, б) с таким же ускорением («корень квадратный раз») по сравнению с классическим, но в) гораздо более экономный по памяти (по числу используемых кубит) по сравнению с ранее известными квантовыми алгоритмами.

Продемонстрировано применение универсального хеширования и техники квантового хеширования для задачи поиска в тексте заданной подстроки.

Ключевые слова: квантовые алгоритмы, поиск строки, квантовый поиск

Благодарности. Исследование выполнено за счет гранта Российского научного фонда (проект № 19-19-00656).

Литература

  1. Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. – М.: МЦНМО, 1999. – 192 с.
  2. Grover L.K. A fast quantum mechanical algorithm for database search // Proc. 28th Annu. ACM Symp. on Theory of Computing. – 1996. – P. 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 // Samuel J. Lomonaco Jr. (Eds.) AMS Contemporary Mathematics. – 2002. – V. 305. – P. 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. – V. 3, No 1. – P. 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. – V. 3, No 1. – P. 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. – V. 6, No 2. – P. 323–350. – doi: 10.1137/0206024.
  9. Ramesh H., Vinay V. String matching in Õ(√n+√m) quantum time // J. Discrete Algorithms. – 2003. – V. 1, No 1. – P. 103–110. – doi: 10.1016/S1570-8667(03)00010-8.
  10. Ambainis A. Understanding quantum algorithms via query complexity // Proc. Int. Congress of Mathematicians (ICM 2018). – 2019. – P. 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. – V. 46, No 4–5. – P. 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. – V. 101, No 3. – Art. 032346, P. 1–12. – doi: 10.1103/PhysRevA.101.032346.
  13. Carter J.L., Wegman M.N. Universal classes of hash functions // J. Comput. System Sci. – 1979. – V. 18, No 2. – P. 143–154. – doi: 10.1016/0022-0000(79)90044-8.
  14. Stinson D.R. Universal hashing and authentication codes // Des. Codes Cryptogr. – 1994. – V. 4. – P. 369–380. – doi: 10.1007/BF01388651.
  15. Stinson D.R. Combinatorial techniques for universal hashing // J. Comput. Syst. Sci. – 1994. – V. 48, No 2. – P. 337–346. – doi: 10.1016/S0022-0000(05)80007-8.
  16. Ablayev F.M., Vasiliev A.V. Cryptographic quantum hashing // Laser Phys. Lett. – 2013. – V. 11, No 2. – Art. 025202, P. 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. – V. 12, No 12. – Art. 125204, P. 1–5. – doi: 10.1088/1612-2011/12/12/125204.
  18. Аблаев Ф.М., Аблаев М.Ф., Васильев А.В. Универсальное квантовое хеширование // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2014. – Т. 156, кн. 3. – C. 7–18.
  19. Macaluso A., Clissa L., Lodi St., Sartori C. Quantum Ensemble for Classification. – 2020. – arXiv:2007.01028.

Поступила в редакцию 23.07.2020

 

Аблаев Марат Фаридович, младший научный сотрудник лаборатории нелинейной оптики; научный сотрудник лаборатории «Квантовые методы обработки информации»

Казанский физико-технический институт им. Е.К. Завойского ФИЦ Казанский научный центр РАН

ул. Сибирский тракт, д. 10/7, г. Казань, 420029, Россия

Казанский (Приволжский) федеральный университет ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail: mablayev@gmail.com

Салихова Наиля Маратовна, младший научный сотрудник лаборатории «Квантовые методы обработки информации»

Казанский (Приволжский) федеральный университет ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail: nailyasalikhova66@gmail.com

 

Контент доступен под лицензией Creative Commons Attribution 4.0 License.