Quantum Online Algorithms with Respect to Space and Advice Complexity
Tóm tắt
Từ khóa
Tài liệu tham khảo
J. Boyar, S. Irani, and K. S. Larsen, “A comparison of performance measures for online algorithms,” in Proceedings of the Workshop on Algorithms and Data Structures (Springer, 2009), pp. 119–130.
J. Boyar, S. Irani, and K. S. Larsen, “A comparison of performance measures for online algorithms,” Algorithmica 72, 969–994 (2015).
R. Dorrigiv and A. Lуpez-Ortiz, “A survey of performance measures for on-line algorithms,” SIGACT News 36 (3), 67–81 (2005).
A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator, “Competitive snoopy caching,” in Proceedings of the 27th Annual Symposium on Foundations of Computer Science, Oct. 27–29, 1986, pp. 244–254.
D. D. Sleator and R. E. Tarjan, “Amortized efficiency of list update and paging rules,” Commun. ACM 28, 202–208 (1985).
Q. Yuan, “Quantum online algorithms,” PhD Thesis (UC Santa Barbara, 2009).
L. Becchetti and E. Koutsoupias, “Competitive analysis of aggregate max in windowed streaming,” in Proceedings of the 36th International Colloquium on Automata, Languages and Programming ICALP 2009, Rhodes, Greece, July 5–12. 2009 (2009). Part 1, pp. 156–170.
Y. Giannakopoulos and E. Koutsoupias, “Competitive analysis of maintaining frequent items of a stream,” Theor. Comput. Sci. 562, 23–32 (2015).
J. Boyar, K. S. Larsen, and A. Maiti, “The frequent items problem in online streaming under various performance measures,” Int. J. Found. Comput. Sci. 26, 413–439 (2015).
H. Klauck, “Quantum communication complexity,” in Proceedings of the 27th International Colloquium on Automata, Languages and Programming 2000, Workshop on Boolean Functions and Applications, 2000.
M. Sauerhoff and D. Sieling, “Quantum branching programs and space-bounded nonuniform quantum complexity,” Theor. Comput. Sci. 334, 177–225 (2005).
F. le Gall, “Exponential separation of quantum and classical online space complexity,” in Proceedings of the Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (ACM, 2006), pp. 67–73.
D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. deWolf, “Exponential separations for one-way quantum communication complexity, with applications to cryptography,” in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (ACM, 2007), pp. 516–525.
F. Ablayev and K. Khadiev, “Extension of the hierarchy for k-OBDDs of small width,” Russ. Math. 57 (3), 46–50 (2013).
K. Khadiev, “On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs,” Lobachevskii J. Math. 37, 683–704 (2016).
A. Ambainis and A. Yakaryılmaz, “Superiority of exact quantum automata for promise problems,” Inform. Proces. Lett. 112, 289–291 (2012).
A. Ambainis and A. Yakaryılmaz, “Automata and quantum computing,” arXiv:1507. 01988 (2015).
R. Ibrahimov, K. Khadiev, and A. Yakaryılmaz, “New size hierarchies for two way automata,” Lobachevskii J. Math. 39, 997–1009 (2018).
M. Nakanishi, K. Khadiev, K. Prusis, J. Vihrov, and A. Yakaryılmaz, “Exact affine counter automata,” Electron. Proc. Theor. Comput. Sci. 252, 205–218 (2017).
F. Ablayev, F. Ablayev, K. Khadiev, and A. Vasilyev, “Classical and quantum computations with restricted memory,” Lect. Not. Comput. Sci. 11011, 129–155 (2018).
F. Ablayev, A. Gainutdinova, M. Karpinski, C. Moore, and C. Pollett, “On the computational power of probabilistic and quantum branching program,” Inform. Comput. 203, 145–162 (2005).
F. Ablayev, A. Gainutdinova, K. Khadiev, and A. Yakaryılmaz, “Very narrow quantum obdds and width hierarchies for classical obdds,” Lect. NotesComput. Sci. 8614, 53–64 (2014).
F. Ablayev, A. Gainutdinova, K. Khadiev, and A. Yakaryılmaz, “Very narrow quantum obdds and width hierarchies for classical obdds,” Lobachevskii J. Math. 37, 670–682 (2016).
A. F. Gainutdinova, “Comparative complexity of quantum and classical obdds for total and partial functions,” Russ. Math. 59 (11), 26–35 (2015).
K. Khadiev and A. Khadieva, “Reordering method and hierarchies for quantum and classical ordered binary decision diagrams,” Lect. Notes Comput. Sci. 10304, 162–175 (2017).
F. Ablayev, A. Ambainis, K. Khadiev, and A. Khadieva, “Lower bounds and hierarchies for quantum automata communication protocols and quantum ordered binary decision diagrams with repeated test,” Lect. Notes Comput. Sci. 10706, 197–211 (2018).
R. Ibrahimov, K. Khadiev, K. Prūsis, and A. Yakaryılmaz, “Error-free affine, unitary and probabilistic OBDDs,” Lect. NotesComput. Sci. 10952, 175–187 (2018).
D. Komm, An Introduction to Online Computation: Determinism, Randomization, Advice (Springer, New York, 2016).
J. Boyar, L. M. Favrholdt, C. Kudahl, K. S. Larsen, and J. W. Mikkelsen, “Online algorithms with advice: a survey,” ACMSigact News 47 (3), 93–129 (2016).
J. Boyar, L. M. Favrholdt, C. Kudahl, K. S. Larsen, and J. W. Mikkelsen, “Online algorithms with advice: a survey,” ACMComput. Surv. 50 (2), 19 (2017).
J. Hromkovich and I. Zбmecnikovб, Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms, Texts in Theoretical Computer Science (Springer, Berlin, Heidelberg, 2005).
J. Kleinberg and E. Tardos, Algorithm Design (Pearson Education, India, 2006).
R. Motwani and P. Raghavan, Randomized Algorithms (Chapman Hall/CRC, Boca Raton, 2010).
C. H. Bennett and S. J. Wiesner, “Communication via one-and two-particle operators on einstein-podolskyrosen states,” Phys. Rev. Lett. 69, 2881 (1992).
A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis (Cambridge Univ. Press, Cambridge, 2005).
S. Albers, BRICS, Mini-Course on Competitive Online Algorithms (Aarhus Univ., 1996).
F. Ablayev and A. Vasilyev, “On quantum realisation of boolean functions by the fingerprinting technique,” DiscreteMath. Appl. 19, 555–572 (2009).
F. Ablayev and A. Vasiliev, “On the computation of boolean functions by quantum branching programs via fingerprinting,” Electron. Colloq. Comput. Complexit. 15 (2008).
F. Ablayev, A. Khasianov, and A. Vasiliev, “On complexity of quantum branching programs computing equality-like boolean functions,” Electron. Colloq. Comput. Complexity (2010).
A. Ambainis and N. Nahimovs, “Improved constructions of quantum automata,” in Proceedings of the Conference on Quantum Computation, Communication, and Cryptography TQC, 2008, pp. 47–56.
A. Ambainis and N. Nahimovs, “Improved constructions of quantum automata,” Theor. Comput. Sci. 410, 1916–1922 (2009).
A. Ambainis and R. Freivalds, “1-way quantum finite automata: strengths, weaknesses and generalizations,” in Proceedings of the 39th Annual Symposium on Foundations of Computer Science FOCS’98 (1998), pp. 332–341.