Quantum and classical nondeterministic OBDDs

A. F. Gainutdinova

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 166 (2024) no. 4, pp. 470-484

Résumé

A model of nondeterministic ordered binary decision diagrams (NOBDDs) was analyzed. A method for proving a lower bound on the complexity of quantum NOBDDs was developed. Two functions were introduced: one function has linear complexity in the quantum NOBDD but constant complexity in the classical NOBDD, while the other function demonstrates the same complexity in both quantum and classical NOBDD models. The relationships among the complexity classes specific to the OBDD model were described.

Détail

Keywords: branching program, ordered binary decision diagram, OBDD, complexity, quantum algorithm, nondeterminism, hierarchy of complexity classes.

Bibliographie

[1] Wegener I., Branching Programs and Binary Decision Diagrams: Theory and Applications, Discrete Mathematics and Applications, ed. Hammer P.L., Soc. Ind. Appl. Math., Philadelphia, PA, 2000, 396 pp. | DOI

[2] Nakanishi M., Hamaguchi K., Kashiwabara T., “Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction”, Computing and Combinatorics (COCOON 2000), Proc. 6th Annu. Int. Conf., Lecture Notes in Computer Science, 1858, eds. Du D.-Z., Eades P., Estivill-Castro V., Lin X., Sharma A., Springer, Berlin–Heidelberg, 2000, 467–476 | DOI

[3] Sauerhoff M., Sieling D., “Quantum branching programs and space-bounded nonuniform quantum complexity”, Theor. Comput. Sci., 334:1–3 (2005), 177–225 | DOI

[4] Ablayev F.M., Karpinski M., “On the power of randomized branching programs”, Automata, Languages and Programming (ICALP' 96), Proc. 23rd Int. Colloq., Lecture Notes in Computer Science, 1099, eds. Meyer F., Monien B., Springer, Berlin–Heidelberg, 1996, 348–356 | DOI

[5] Ablayev F., Gainutdinova A., Karpinski M., Moore C., Pollette C., “On the computational power of probabilistic and quantum branching program”, Inf. Comput., 203:2 (2005), 145–162 | DOI

[6] Ablayev F., Gainutdinova A., Khadiev K., Yakary{\i}lmaz A., “Very narrow quantum OBDDs and width hierarchies for classical OBDDs”, Lobachevskii J. Math., 37:6 (2016), 670–682 | DOI

[7] Gainutdinova A., Yakary{\i}lmaz A., “Nondeterministic unitary OBDDs”, Computer Science – Theory and Applications (CSR 2017), Proc. 12th Int. Comput. Sci. Symp. in Russia, Lecture Notes in Computer Science, 10304, ed. Weil P., Springer, Cham, 2017, 126–140 | DOI

[8] Gainutdinova A.F., “Comparative complexity of quantum and classical OBDDs for total and partial functions”, Russ. Math., 59:11 (2015), 26–35 | DOI

[9] Ablayev F., Gainutdinova A., “Complexity of quantum uniform and nonuniform automata”, Developments in Language Theory (DLT 2005), Proc. 9th Int. Conf., Lecture Notes in Computer Science, 3572, eds. De Felice C., Restivo A., Springer, Berlin–Heidelberg, 2005, 78–87 | DOI

[10] Nielsen M.A., Chuang I., Quantum Computation and Quantum Information, v. 2, Cambridge Series on Information and the Natural Sciences, Cambridge Univ. Press, Cambridge, 2000, 676 pp.

[11] Kostrikin A.I., Introduction to Algebra, v. 2, Linear algebra, MtsNMO, M., 2020, 368 pp. (In Russian)

[12] Ablayev F., Gainutdinova A., Khadiev K., Yakary{\i}lmaz A., “Very narrow quantum OBDDs and width hierarchies for classical OBDDs”, Descriptional Complexity of Formal Systems (DCFS 2014), Proc. 16th Int. Wokshop, Lecture Notes in Computer Science, 8614, eds. Jürgensen H., Karhumäki J., Okhotin A., Springer, Cham, 2014, 53–64 | DOI