Quantum online algorithms for a model of the request-answer game with a buffer

K.R. Khadieva,b∗ , D.I. Linb,c∗∗

aOOO Kvantovye intellektual’nye tekhnologii, Kazan, 420111 Russia

bKazan Federal University, Kazan, 420008 Russia

cAO Bars Grup, Kazan, 420012 Russia

E-mail: ∗kamilhadi@gmail.com, ∗∗dmitrijlin9@gmail.com

Received August 4, 2020

Full text PDF

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)

 

Abstract

In this paper, we considered online algorithms as a request-answer game between two players: an adversary that generates input requests and an online algorithm that answers them. A generalized version of the game that has a buffer of limited size was studied. The adversary loads data to the buffer, while the algorithm has random access to elements of the buffer. For the model, quantum and classical (deterministic or randomized) algorithms were a focus of attention. A specific problem and a quantum algorithm that works better than any classical (deterministic or randomized) algorithm, in terms of competitive ratio, were provided. At the same time, for the problem, classical online algorithms in the standard model are equivalent to the classical algorithms in the request-answer game with a buffer model.

Keywords: quantum computation, online algorithms, request-answer game, online minimization problem, computation with buffer

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

We are grateful to Farid Mansurovich Ablaev and Aliya Ikhsanovna Khadieva (Kazan Federal University) for their valuable advice during the discussion of the problem under consideration.

References

  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. Commun. ACM, 1985, vol. 28, no. 2, pp. 202–208. doi: 10.1145/2786.2793.
  3. Karlin A.R., Manasse M.S., Rudolph L., Sleator D.D. Competitive snoopy caching. Proc. 27th Annu. Symp. on Foundations of Computer Science. Toronto, Ont., Canada, 1986, pp. 244–254. doi: 10.1109/SFCS.1986.14.
  4. Albers S. Competitive Online Algorithms: A BRICS Mini-Course. 1996. Available at: https://www.brics.dk/LS/96/2/.
  5. Java Platform SE 8 documentation. Available at: 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, pp. 3265–3285. doi: 10.1142/9-789813272880 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 Min. Anal., 2019, vol. 3, no. 1, pp. 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. Available at: https://homepages.cwi.nl/~rdewolf/publ/qc/phd.pdf.
  12. Jordan St. Quantum Algorithm Zoo. Available at: 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. In: McQuillan I., Seki S. (Eds.) Unconventional Computation and Natural Computation. UCNC 2019. Lecture Notes in Computer Science. Cham, Springer, 2019, vol. 11493, pp. 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. In: van Bevern R., Kucherov G. (Eds.) Computer Science – Theory and Applications. CSR 2019. Lecture Notes in Computer Science. Cham, Springer, 2019, vol. 11532, pp. 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. In: H¨olldobler S., Malikov A. (Eds.) Proc. YSIP-3 Workshop, 2019. Available at: http://ceur-ws.org/Vol-2500/paper6.pdf.
  16. Ambainis A., Nahimovs N. Improved constructions of quantum automata. Theor. Comput. Sci., 2009, vol. 410, no. 20, pp. 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 fingerprinting technique. Discrete Math. Appl., 2009, vol. 19, no. 6, pp. 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. In: Ju¨rgensen H., Karhuma¨ki J., Okhotin A. (Eds.) Descriptional Complexity of Formal Systems. DCFS 2014. Lecture Notes in Computer Science. Cham, Springer, 2014, vol. 8614, pp. 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, vol. 37, no. 6, pp. 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. In: 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. Cham, Edizioni della Normale, 2018, vol. 10706, pp. 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. In: B¨ockenhauer H.J., Komm D., Unger W. (Eds.) Adventures Between Lower Bounds and Higher Altitudes. Lecture Notes in Computer Science. Cham, Springer, 2018, vol. 11011, pp. 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, vol. 39, no. 9, pp. 1377–1387. doi: 10.1134/S1995080218090421.
  23. Khadiev K., Khadieva A. Reordering method and hierarchies for quantum and classical ordered binary decision diagrams. In: Weil P. (Ed.) Computer Science – Theory and Applications. CSR 2017. Lecture Notes in Computer Science. Cham, Springer, 2017, vol. 10304, pp. 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. In: Konstantinidis S., Pighizzini G. (Eds.) Descriptional Complexity of Formal Systems. DCFS 2018. Lecture Notes in Computer Science. Cham, Springer, 2018, vol. 10952, pp. 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, vol. 45, no. 2, pp. 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. In: Mart´ın-Vide C., Pond G., Vega-Rodr´ıguez M. (Eds.) Theory and Practice of Natural Computing. TPNC 2019. Lecture Notes in Computer Science. Cham, Springer, 2019, vol. 11934, pp. 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. Available at: 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, Vol. 11022: Int. Conf. on Microand Nano-Electronics 2018, 2019, art. 110222T, pp. 1–9. doi: 10.1117/12.2522462.
  30. Yuan Q. Quantum online algorithms. PhD Thesis. Santa Barbara, US, Univ. Calif. at Santa Barbara, 2009. 88 p.
  31. Cormode Gr., Hadjieleftheriou M. Finding frequent items in data streams. Proc. VLDB Endowment, 2008, vol. 1, no. 2, pp. 1530–1541. doi: 10.14778/1454159.1454225.
  32. Muthukrishnan S. Data streams: Algorithms and applications. Found. Trends Theor. Comput. Sci., 2005, vol. 1, no. 2, pp. 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, vol. 5, no. 1, pp. 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, vol. 26, no. 4, pp. 413– 439. doi: 10.1142/S0129054115500239.
  36. Adel’son-Vel’skii G.M., Landis E.M. An algorithm for organization of information. Dokl. Akad. Nauk SSSR, 1962, vol. 146, no. 2, pp. 263–266. (In Russian)
  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. Proc. 19th Annu. Symp. on Foundations of Computer Science. IEEE, 1978, pp. 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, vol. 26, no. 5, pp. 1510–1523. doi: 10.1137/S0097539796300933.

 

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