Квантовые онлайн-алгоритмы для модели игры запрос-ответ с буфером
Институты и факультеты
Главная \ Наука \ Научные издания КФУ \ Ученые записки Казанского университета \ Ученые записки Казанского университета. Серия Физико-математические науки \ Архив

Квантовые онлайн-алгоритмы для модели игры запрос-ответ с буфером

К.Р. Хадиев1,2 , Д.И. Лин2,3

1ООО «Квантовые интеллектуальные технологии», г. Казань, 420111, Россия

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

3Компания АО «Барс Груп», г. Казань, 420012, Россия

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

Для цитирования: Хадиев К.Р., Лин Д.И. Квантовые онлайн-алгоритмы для модели игры запрос-ответ с буфером // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 3. – С. 367–382. – doi: 10.26907/2541-7746.2020.3.367-382.

For citation: Khadiev K.R., Lin D.I. Quantum online algorithms for a model of the request-answer game with a buffer. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 367–382. doi: 10.26907/2541-7746.2020.3.367-382. (In Russian)

Аннотация

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

Специально была сконструирована задача, для которой квантовый алгоритм работает эффективнее, чем любой классический. Эффективность алгоритмов в работе рассматривается с точки зрения конкурентного соотношения. Заметим, что при рассмотрении классических алгоритмов стандартная модель онлайн-алгоритмов эквивалентна расширенной модели с буфером.

Ключевые слова: квантовые вычисления, онлайн-алгоритмы, игра запрос-ответ, задача онлайн-минимизации, вычисления с буфером

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

Авторы выражают благодарность Аблаеву Фариду Мансуровичу и Хадиевой Алие Ихсановне (Казанский федеральный университет) за полезные советы при обсуждении задачи.

Литература

  1. Komm D. An Introduction to Online Computation: Determinism, Randomization, Advice. – Springer, 2016. – XV, 349 p. – doi: 10.1007/978-3-319-42749-2.
  2. Sleator D.D., Tarjan R.E. Amortized efficiency of list update and paging rules // Communications of the ACM. – 1985. – V. 28, No 2. – P. 202–208. – doi: 10.1145/2786.2793.
  3. Karlin A.R., Manasse M.S., Rudolph L., Sleator D.D. Competitive snoopy caching // 27th Annual Symposium on Foundations of Computer Science. – Toronto, Ont., Canada, 1986. – P. 244–254. – doi: 10.1109/SFCS.1986.14.
  4. Albers S. Competitive Online Algorithms: A BRICS Mini-Course. – 1996. – URL: https://www.brics.dk/LS/96/2/.
  5. Java Platform SE 8 documentation. – URL: https://docs.oracle.com/javase/8/docs/api/java/io/BufferedReader.html.
  6. Lippman S.B., Lajoie J. C++ Primer. – Massachusetts: Addison-Wesley, 1998. – 1264 p.
  7. Nielsen M.A., Chuang I.L. Quantum Computation and Quantum Information. – Cambridge Univ. Press, 2010. – 702 p. – doi: 10.1017/CBO9780511976667.
  8. Ambainis A. Understanding quantum algorithms via query complexity // Proc. Int. Congr. of Mathematicians (ICM 2018). – 2019. – P. 3265–3285. – doi: 10.1142/9789813272880_0181.
  9. 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 Mining and Analytics. – 2019. – V. 3, No 1. – P. 41–55. – doi: 10.26599/BDMA.2019.9020016.
  10. Kapralov R., Khadiev K., Mokut J., Shen Y., Yagafarov M. Fast classical and quantum algorithms for online k-server problem on trees. – 2020. – arXiv:2008.00270.
  11. Wolf de R. Quantum computing and communication complexity: Acad. Proefschrift. – 2001. – 225 p. – URL: https://homepages.cwi.nl/~rdewolf/publ/qc/phd.pdf.
  12. Jordan St. Quantum Algorithm Zoo. – URL: https://quantumalgorithmzoo.org/.
  13. Khadiev K., Safina L. Quantum algorithm for dynamic programming approach for DAGs. Applications for Zhegalkin polynomial evaluation and some problems on DAGs // McQuillan I., Seki S. (Eds.) Unconventional Computation and Natural Computation. UCNC 2019. Lecture Notes in Computer Science, V. 11493. – Cham: Springer, 2019. – P. 150–163. – doi: 10.1007/978-3-030-19311-9_13.
  14. Khadiev K., Kravchenko D., Serov D. On the quantum and classical complexity of solving subtraction games // van Bevern R., Kucherov G. (Eds.) Computer Science – Theory and Applications. CSR 2019. Lecture Notes in Computer Science, V. 11532. – Cham: Springer, 2019. – P. 228–236. – doi: 10.1007/978-3-030-19955-5_20.
  15. Khadiev K., Mannapov I., Safina L. The quantum version of classification decision tree constructing algorithm C5.0 // H¨olldobler S., Malikov A. (eds.) Proc. YSIP-3 Workshop. – 2019. – URL: http://ceur-ws.org/Vol-2500/paper_6.pdf.
  16. Ambainis A., Nahimovs N. Improved constructions of quantum automata // Theor. Comput. Sci. – 2009. – V. 410, No 20. – P. 1916–1922. – doi: 10.1016/j.tcs.2009.01.027.
  17. Ablayev F.M., Vasilyev A.V. On quantum realisation of Boolean functions by the finger- printing technique // Discrete Math. Appl. – 2009. – V. 19, No 6. – P. 555–572. – doi: 10.1515/DMA.2009.037.
  18. Ablayev F., Gainutdinova A., Khadiev K., Yakaryilmaz A. Very narrow quantum OBDDs and width hierarchies for classical OBDDs //Ju¨rgensen H., Karhuma¨ki J., Okhotin A. (Eds.) Descriptional Complexity of Formal Systems. DCFS 2014. Lecture Notes in Computer Science, V. 8614. – Cham: Springer, 2014. – P. 53–64. – doi: 10.1007/978-3-319-09704-6_6.
  19. Ablayev F. Gainutdinova A., Khadiev K., Yakaryilmaz A. Very narrow quantum OBDDs and width hierarchies for classical OBDDs // Lobachevskii J. Math. – 2016. – V. 37, No 6. – P. 670–682. – doi: 10.1134/S199508021606007X.
  20. Ablayev F., Ambainis A., Khadiev K., Khadieva A. Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test // Tjoa A., Bellatreche L., Biffl S., van Leeuwen J., Wiedermann J. (Eds.) SOFSEM 2018: Theory and Practice of Computer Science. SOFSEM 2018. Lecture Notes in Computer Science, V. 10706. – Cham: Edizioni della Normale, 2018. – P. 197–211. – doi: 10.1007/978-3-319-73117-9_14.
  21. Ablayev F., Ablayev M., Khadiev K., Vasiliev A. Classical and quantum computations with restricted memory // B¨ockenhauer H.J., Komm D., Unger W. (Eds.) Adventures Between Lower Bounds and Higher Altitudes. Lecture Notes in Computer Science, V. 11011. – Cham: Springer, 2018. – P. 129–155. – doi: 10.1007/978-3-319-98355-4_9.
  22. Khadiev K., Khadieva A., Mannapov I. Quantum online algorithms with respect to space and advice complexity // Lobachevskii J. Math. – 2018. – V. 39, No 9. – P. 1377–1387. – doi: 10.1134/S1995080218090421.
  23. Khadiev K., Khadieva A. Reordering method and hierarchies for quantum and classical ordered binary decision diagrams // Weil P. (Ed.) Computer Science – Theory and Applications. CSR 2017. Lecture Notes in Computer Science, V. 10304. – Cham: Springer, 2017. – P. 162–175. – doi: 10.1007/978-3-319-58747-9_16.
  24. Ibrahimov R., Khadiev K., Pru¯sis K., Yakaryilmaz A. Error-free affine, unitary, and probabilistic OBDDs // Konstantinidis S., Pighizzini G. (Eds.) Descriptional Complexity of Formal Systems. DCFS 2018. Lecture Notes in Computer Science, V. 10952. – Cham: Springer, 2018. – P. 175–187. – doi: 10.1007/978-3-319-94631-3_15.
  25. Le Gall F. Exponential separation of quantum and classical online space complexity // Theory Comput. Syst. – 2009. – V. 45, No 2. – P. 188–202. – doi: 10.1007/s00224-007-9097-3.
  26. Khadiev K., Ilikaev A. Quantum algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems // Mart´ın-Vide C., Pond G., Vega-Rodr´ıguez M. (Eds.) Theory and Practice of Natural Computing. TPNC 2019. Lecture Notes in Computer Science, V. 11934. – Cham: Springer, 2019. – P. 234– 245. – doi: 10.1007/978-3-030-34500-6_17.
  27. Khadiev K., Khadieva A., Kravchenko D., Rivosh A., Yamilov A., Mannapov I. Quantum versus classical online streaming algorithms with logarithmic size of memory. – 2019. – arXiv:1710.09595v3.
  28. Khadiev K., Khadieva A. Quantum online streaming algorithms with logarithmic memory // Int. J. Theor. Phys. – 2019. – doi: 10.1007/s10773-019-04209-1. – URL: https://link.springer.com/article/10.1007%2Fs10773-019-04209-1.
  29. Khadiev K., Khadieva A. Two-way quantum and classical machines with small memory for online minimization problems // Proc. SPIE V. 11022: International Conference on Micro- and Nano-Electronics 2018. – 2019. – Art. 110222T, P. 1–9. – doi: 10.1117/12.2522462.
  30. Yuan Q. Quantum online algorithms: PhD Thesis. – Santa Barbara, US: University of California at Santa Barbara, 2009. – 88 p.
  31. Cormode Gr., Hadjieleftheriou M. Finding frequent items in data streams // Proc. VLDB Endowment. – 2008. – V. 1, No 2. – P. 1530–1541. – doi: 10.14778/1454159.1454225.
  32. Muthukrishnan S. Data streams: Algorithms and applications // Foundations and Trends in Theoretical Computer Science. – 2005. – V. 1, No 2. – P. 117–236.
  33. Aggarwal Ch.C. Data Streams: Models and Algorithms. – Springer US, 2007. – XVIII, 354 p. – doi: 10.1007/978-0-387-47534-9.
  34. Becchetti L., Chatzigiannakis I., Giannakopoulos Y. Streaming techniques and data aggregation in networks of tiny artefacts // Comput. Sci. Rev. – 2011. – V. 5, No 1. – P. 27–46. – doi: 10.1016/j.cosrev.2010.09.007.
  35. Boyar J., Larsen K.S., Maiti A. The frequent items problem in online streaming under various performance measures // Int. J. Found. Comput. Sci. – 2015. – V. 26, No 4. – P. 413–439. – doi: 10.1142/S0129054115500239.
  36. Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организации информации // Докл. АН СССР. – 1962. Т. 146, № 2. – С. 263–266.
  37. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. – Cambridge, Mass.: MIT Press, 2001. – 1180 p.
  38. Guibas L. J, Sedgewick R. A dichromatic framework for balanced trees // 19th Annu. Symp. on Foundations of Computer Science – IEEE, 1978. – P. 8–21. – doi: 10.1109/SFCS.1978.3.
  39. Bennett Ch.H., Bernstein E., Brassard G., Vazirani U. Strengths and weaknesses of quantum computing // SIAM J. Comput. – 1997. – V. 26, No 5. – P. 1510–1523. – doi: 10.1137/S0097539796300933.

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

 

Хадиев Камиль Равилевич, кандидат физико-математических наук, научный сотрудник; старший научный сотрудник лаборатории «Квантовые методы обработки информации»

ООО «Квантовые интеллектуальные технологии»

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

ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail: kamilhadi@gmail.com

Лин Дмитрий Игоревич, студент Института вычислительной математики и информационных технологий; разработчик

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

Компания АО «Барс Груп»

ул. Некрасова, д. 9, г. Казань, 420012, Россия

E-mail: dmitrijlin9@gmail.com

 

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

 


Версия для печати Версия для печати
Ключевые слова: Хадиев, Ученые записки
Вход в личный кабинет
Ваш логин
Ваш пароль
Забыли пароль? Регистрация