Quantum and classical nondeterministic OBDDs
https://doi.org/10.26907/2541-7746.2024.4.470-484
Abstract
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.
Keywords
branching program,
ordered binary decision diagram,
OBDD,
complexity,
quantum algorithm,
nondeterminism,
hierarchy of complexity classes
Supporting agencies: The research has been supported by the Kazan Federal University Strategic Academic Leadership Program («PRIORITY-2030»)
References
1. Wegener I. Branching Programs and Binary Decision Diagrams: Theory and Applications. Ser.: Discrete Mathematics and Applications. Hammer P.L. (Ed.). Philadelphia, PA, Soc. Ind. Appl. Math., 2000. 396 p. doi: 10.1137/1.9780898719789.
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. 6<sup>th</sup> Annu. Int. Conf. Du D.-Z., Eades P., Estivill-Castro V., Lin X., Sharma A. (Eds.). Ser.: Lecture Notes in Computer Science. Vol. 1858. Berlin, Heidelberg, Springer, 2000, pp. 467–476. doi: 10.1007/3-540-44968-X_46.
3. Sauerhoff M., Sieling D. Quantum branching programs and space-bounded nonuniform quantum complexity. Theor. Comput. Sci., 2005, vol. 334. nos. 1–3, pp. 177–225. doi: 10.1016/j.tcs.2004.12.031.
4. Ablayev F.M., Karpinski M. On the power of randomized branching programs. Automata, Languages and Programming (ICALP’ 96): Proc. 23<sup>rd</sup> Int. Colloq. Meyer F., Monien B. (Eds.). Ser.: Lecture Notes in Computer Science. Vol. 1099. Berlin, Heidelberg, Springer, 1996, pp. 348–356. doi: 10.1007/3-540-61440-0_141.
5. Ablayev F., Gainutdinova A., Karpinski M., Moore C., Pollette C. On the computational power of probabilistic and quantum branching program. Inf. Comput., 2005, vol. 203, no. 2, pp. 145–162. doi: 10.1016/j.ic.2005.04.003. 6. Ablayev F., Gainutdinova A., Khadiev K., Yakaryılmaz 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.
6. Gainutdinova A., Yakaryılmaz A. Nondeterministic unitary OBDDs. Computer Science – Theory and Applications (CSR 2017): Proc. 12<sup>th</sup> Int. Comput. Sci. Symp. in Russia. Weil P. (Ed.). Ser.: Lecture Notes in Computer Science. Vol. 10304. Cham, Springer, 2017, pp. 126–140. doi: 10.1007/978-3-319-58747-9_13.
7. Gainutdinova A.F. Comparative complexity of quantum and classical OBDDs for total and partial functions. Russ. Math., 2015, vol. 59, no. 11, pp. 26–35. doi: 10.3103/S1066369X15110031.
8. Ablayev F., Gainutdinova A. Complexity of quantum uniform and nonuniform automata. Developments in Language Theory (DLT 2005): Proc. 9<sup>th</sup> Int. Conf. De Felice C.,
9. Restivo A. (Eds.). Ser.: Lecture Notes in Computer Science. Vol. 3572. Berlin, Heidelberg, Springer, 2005, pp. 78–87. doi: 10.1007/11505877_7.
10. Nielsen M.A., Chuang I.L. Quantum Computation and Quantum Information. Ser.: Cambridge Series on Information and the Natural Sciences. Vol. 2. Cambridge, Cambridge Univ. Press, 2000. 676 p.
11. Kostrikin A.I. Vvedenie v algebru [Introduction to Algebra]. Pt. 2: Linear algebra. Moscow, MtsNMO, 2020. 368 p. (In Russian)
12. Ablayev F., Gainutdinova A., Khadiev K., Yakaryılmaz A. Very narrow quantum OBDDs and width hierarchies for classical OBDDs. Descriptional Complexity of Formal Systems (DCFS 2014): Proc. 16<sup>th</sup> Int. Wokshop. J¨urgensen H., Karhum¨aki J., Okhotin A. (Eds.). Ser.: Lecture Notes in Computer Science. Vol. 8614. Cham, Springer, 2014, pp. 53–64. doi: 10.1007/978-3-319-09704-6_6.
Review
For citations:
Gainutdinova A.F. Quantum and classical nondeterministic OBDDs. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2024;166(4):470-484. (In Russ.) https://doi.org/10.26907/2541-7746.2024.4.470-484
Views:
126
Email this article 