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

K. R. Khadiev ; D. I. Lin

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 367-382

Résumé

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.

Détail

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

Bibliographie

[1] Komm D., An Introduction to Online Computation: Determinism, Randomization, Advice, Springer, 2016, xv+349 pp. | DOI | MR

[2] Sleator D. D., Tarjan R. E., “Amortized efficiency of list update and paging rules”, Communications of the ACM, 28:2 (1985), 202–208 | DOI | MR

[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), 244–254 | DOI | MR

[4] Albers S., Competitive Online Algorithms: A BRICS Mini-Course, 1996 https://www.brics.dk/LS/96/2/

[5] Java Platform SE 8 documentation, https://docs.oracle.com/javase/8/docs/api/java/io/BufferedReader.html

[6] Lippman S. B., Lajoie J., C++ Primer, Addison-Wesley, Massachusetts, 1998, 1264 pp.

[7] Nielsen M. A., Chuang I. L., Quantum Computation and Quantum Information, Cambridge Univ. Press, 2010, 702 pp. | DOI | MR | Zbl

[8] Ambainis A., “Understanding quantum algorithms via query complexity”, Proc. Int. Congr. of Mathematicians, ICM 2018, 2019, 3265–3285 | DOI | MR

[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, 3:1 (2019), 41–55 | DOI

[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 pp. https://homepages.cwi.nl/r̃dewolf/publ/qc/phd.pdf

[12] Jordan St., Quantum Algorithm Zoo, 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”, Unconventional Computation and Natural Computation, UCNC 2019, Lecture Notes in Computer Science, 11493, eds. McQuillan I., Seki S., Springer, Cham, 2019, 150–163 | DOI | MR | Zbl

[14] Khadiev K., Kravchenko D., Serov D., “On the quantum and classical complexity of solving subtraction games”, Computer Science – Theory and Applications, CSR 2019, Lecture Notes in Computer Science, 11532, eds. van Bevern R., Kucherov G., Springer, Cham, 2019, 228–236 | DOI | MR | Zbl

[15] Khadiev K., Mannapov I., Safina L., “The quantum version of classification decision tree constructing algorithm C5.0”, Proc. YSIP-3 Workshop, eds. Hölldobler S., Malikov A., 2019 http://ceur-ws.org/Vol-2500/paper_6.pdf

[16] Ambainis A., Nahimovs N., “Improved constructions of quantum automata”, Theor. Comput. Sci., 410:20 (2009), 1916–1922 | DOI | MR | Zbl

[17] Ablayev F. M., Vasilyev A. V., “On quantum realisation of Boolean functions by the fingerprinting technique”, Discrete Math. Appl., 19:6 (2009), 555–572 | DOI | MR | Zbl

[18] Ablayev F., Gainutdinova A., Khadiev K., Yakaryilmaz A., “Very narrow quantum OBDDs and width hierarchies for classical OBDDs”, Descriptional Complexity of Formal Systems, DCFS 2014, Lecture Notes in Computer Science, 8614, eds. Jürgensen H., Karhumäki J., Okhotin A., Springer, Cham, 2014, 53–64 | DOI | MR | Zbl

[19] Ablayev F. Gainutdinova A., Khadiev K., Yakaryilmaz A., “Very narrow quantum OBDDs and width hierarchies for classical OBDDs”, Lobachevskii J. Math., 37:6 (2016), 670–682 | DOI | MR | Zbl

[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”, SOFSEM 2018: Theory and Practice of Computer Science, Lecture Notes in Computer Science, 10706, eds. Tjoa A., Bellatreche L., Biffl S., van Leeuwen J., Wiedermann J., Edizioni della Normale, Cham, 2018, 197–211 | DOI | MR

[21] Ablayev F., Ablayev M., Khadiev K., Vasiliev A., “Classical and quantum computations with restricted memory”, Adventures Between Lower Bounds and Higher Altitudes, Lecture Notes in Computer Science, 11011, eds. Böckenhauer H. J., Komm D., Unger W., Springer, Cham, 2018, 129–155 | DOI | MR

[22] Khadiev K., Khadieva A., Mannapov I., “Quantum online algorithms with respect to space and advice complexity”, Lobachevskii J. Math., 39:9 (2018), 1377–1387 | DOI | MR | Zbl

[23] Khadiev K., Khadieva A., “Reordering method and hierarchies for quantum and classical ordered binary decision diagrams”, Computer Science – Theory and Applications, CSR 2017, Lecture Notes in Computer Science, 10304, ed. Weil P., Springer, Cham, 2017, 162–175 | DOI | MR | Zbl

[24] Ibrahimov R., Khadiev K., Prūsis K., Yakaryilmaz A., “Error-free affine, unitary, and probabilistic OBDDs”, Descriptional Complexity of Formal Systems, DCFS 2018, Lecture Notes in Computer Science, 10952, eds. Konstantinidis S., Pighizzini G., Springer, Cham, 2018, 175–187 | DOI | MR | Zbl

[25] Le Gall F., “Exponential separation of quantum and classical online space complexity”, Theory Comput. Syst., 45:2 (2009), 188–202 | DOI | MR | Zbl

[26] Khadiev K., Ilikaev A., “Quantum algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems”, Theory and Practice of Natural Computing, TPNC 2019, Lecture Notes in Computer Science, 11934, eds. Martín-Vide C., Pond G., Vega-Rodríguez M., Springer, Cham, 2019, 234–245 | DOI | MR

[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 | MR

[28] Khadiev K., Khadieva A., “Quantum online streaming algorithms with logarithmic memory”, Int. J. Theor. Phys., 2019 | DOI | MR

[29] Khadiev K., Khadieva A., “Two-way quantum and classical machines with small memory for online minimization problems”, International Conference on Micro- and Nano-Electronics 2018, Proc. SPIE, 11022, 2019, 110222T, 1–9 | DOI

[30] Yuan Q., Quantum online algorithms, PhD Thesis, University of California at Santa Barbara, Santa Barbara, US, 2009, 88 pp.

[31] Cormode Gr., Hadjieleftheriou M., “Finding frequent items in data streams”, Proc. VLDB Endowment, 1:2 (2008), 1530–1541 | DOI

[32] Muthukrishnan S., “Data streams: Algorithms and applications”, Foundations and Trends in Theoretical Computer Science, 1:2 (2005), 117–236 | DOI | MR

[33] Aggarwal Ch.C., Data Streams: Models and Algorithms, Springer US, 2007, xviii+354 pp. | DOI | MR | Zbl

[34] Becchetti L., Chatzigiannakis I., Giannakopoulos Y., “Streaming techniques and data aggregation in networks of tiny artefacts”, Comput. Sci. Rev., 5:1 (2011), 27–46 | DOI | Zbl

[35] Boyar J., Larsen K. S., Maiti A., “The frequent items problem in online streaming under various performance measures”, Int. J. Found. Comput. Sci., 26:4 (2015), 413–439 | DOI | MR | Zbl

[36] Adel'son-Vel'skii G. M., Landis E. M., “An algorithm for organization of information”, Dokl. Akad. Nauk SSSR, 146:2 (1962), 263–266 (In Russian) | MR

[37] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to Algorithms, MIT Press, Cambridge, Mass., 2001, 1180 pp. | MR | Zbl

[38] Guibas L. J, Sedgewick R., “A dichromatic framework for balanced trees”, 19th Annu. Symp. on Foundations of Computer Science, IEEE, 1978, 8–21 | DOI | MR

[39] Bennett Ch.H., Bernstein E., Brassard G., Vazirani U., “Strengths and weaknesses of quantum computing”, SIAM J. Comput., 26:5 (1997), 1510–1523 | DOI | MR | Zbl