Large Width Nondeterministic Quantum OBDDs
DOI:
https://doi.org/10.17072/1993-0550-2024-4-117-131Keywords:
branching program, ordered binary decision diagram, nondeterminism, quantum algorithm, complexity, complexity class, computational model, hierarchy of complexity classes, lower bound, upper boundAbstract
In this paper we investigate ordered binary decision diagrams (OBDD) – a model for computing Boolean functions. The aim of this work is a comparative complexity analysis of quantum and classical nondeterministic OBDDs of large width. We study the complexity of computing the Boolean function "Equality" in nondeterministic quantum OBDDs for different order of reading variables in comparison with the classical complexity. We show that when using the order of reading for which the width of the classical nondeterministic OBDD is constant, the width of the quantum model is linear and the proved lower bound is tight. We define a Boolean function for which the width of nondeterministic quantum OBDD is exponential for any order of reading variables. We construct a quantum algorithm for computing this function with zero error. We present a result on the relationship between complexity classes for quantum and classical nondeterministic OBDDs of large width.References
Манин Ю.И. Вычислимое и невычислимое. М.: Сов. Радио. 1980. 128 с.
Feynman R. Simulating physics with computers // International Journal of Theoretical Physics. 1982. Vol. 21, № 6, 7. С. 467−488.
Wegener I. Branching programs and binary decision diagrams: theory and applications. Society for Industrial and Applied Mathematics. 2000. 408 p.
Cobham A. The recognition problem for the set of perfect squares // Proc. of the 7th Symposium on Switching an Automata Theory (SWAT). 1996. P. 78−87.
Pudlak P., Zak S. Space complexity of computations. Technical report, Univ. Prague. 1983.
Ablayev F., Gainutdinova A., Karpinski M. On Computational Power of Quantum Branching Programs // Proc. of the 13th Intern. Symposium, Fundamentals of Computation Theory, FCT2001. 2001. Vol. 2138. P. 59−70.
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: 6th Annual Intern. Conference, COCOON 2000, Proc. 2000. Vol. 2138. P. 467−476.
Sauerhoff M., Sieling D. Quantum branching programs and space-bounded nonuniform quantum complexity // Theoretical Computer Science. 2005. Vol. 334. № 1–3. P. 177–225.
Ablayev F., Karpinski M. On the power of randomized branching programs // Proc. ICALP96. 1996. Vol. 1099. P. 348–356.
Ablayev F., Gainutdinova A., Karpinski M., Moore C., Pollette C. On the computational power of probabilistic and quantum branching program // Information and Computation. 2005. Vol. 203, № 2. P. 145–162.
Ablayev F., Gainutdinova A., Khadiev K., Yakaryılmaz A. Very narrow quantum OB-DDs and width hierarchies for classical OBDDs // Lobachevskii Journal of Mathematics. 2016. Vol. 37. P. 670–682.
Gainutdinova A., Yakaryılmaz A. Nondeterministic unitary OBDDs // Computer Science – Theory and Applications: 12th Intern. Computer Science Symposium in Russia, CSR2017, Proceedings. 2017. P. 126–140.
Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD-foundations and applications. Springer Science & Business Media, 1998. 279 p.
Ablayev F., Gainutdinova A. Complexity of quantum uniform and nonuniform automata // Developments in Language Theory: 9th Intern. Conference, DLT2005, Proceedings. 2005. P. 78–87.
Nielsen M. A., Chuang I. L. Quantum computation and quantum information. Cambridge university press, 2010. 710 p.
Кострикин А.И. Введение в алгебру: учебник: в 3 частях. Часть II: Линейная алгебра. М.: МЦНМО, 2020. 367 с.
Ablayev F., Gainutdinova A., Khadiev K., Yakaryılmaz A. Very narrow quantum OB-DDs and width hierarchies for classical OBDDs // Descriptional Complexity of Formal Systems: 16th Intern. Workshop DCFS2014, Proceedings. 2014. P. 53–64.
Khadiev K., Khadieva A. Reordering method and hierarchies for quantum and classical ordered binary decision diagrams // International computer science symposium in Russia, Springer International Publishing, 2017. P. 162–175.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Аида Фаритовна Гайнутдинова
This work is licensed under a Creative Commons Attribution 4.0 International License.
Articles are published under license Creative Commons Attribution 4.0 International (CC BY 4.0).
