Abstract
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata versions of these models.
Part of the research work was done while Ibrahimov was visiting University of Latvia in February 2017.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It evolves linearly but a non-linear operator is applied when we retrieve information from the state vector.
- 2.
Suppose we have \(w_i\le m\) nodes on a level i; then the node \(u_j\) of this level corresponds to the state \(s_j\), for \(j\in \{1,\dots ,w_i\}\).
References
Ablayev, F., Gainutdinova, A.: Complexity of quantum uniform and nonuniform automata. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 78–87. Springer, Heidelberg (2005). https://doi.org/10.1007/11505877_7
Ablayev, F., Gainutdinova, A., Khadiev, K., Yakaryılmaz, A.: Very narrow quantum OBDDs and width hierarchies for classical OBDDs. Lobachevskii J. Math. 37(6), 670–682 (2016)
Ablayev, F.: Randomization and nondeterminism are incomparable for ordered read-once branching programs. In: ECCC (021) (1997)
Ablayev, F., Gainutdinova, A., Karpinski, M., Moore, C., Pollett, C.: On the computational power of probabilistic and quantum branching program. Inf. Comput. 203(2), 145–162 (2005)
Ablayev, F., Gainutdinova, A., Khadiev, K., Yakaryılmaz, A.: Very narrow quantum OBDDs and width hierarchies for classical OBDDs. In: Jürgensen, H., Karhumäki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 53–64. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09704-6_6
Ablayev, F., Karpinski, M.: On the power of randomized branching programs. In: Meyer, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 348–356. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61440-0_141
Ambainis, A., Watrous, J.: Two-way finite automata with quantum and classical states. Theor. Comput. Sci. 287(1), 299–311 (2002)
Ambainis, A., Yakaryılmaz, A.: Automata and quantum computing. Technical report 1507.01988, arXiv (2015)
Belovs, A., Montoya, J.A., Yakaryılmaz, A.: On a conjecture by Christian Choffrut. Int. J. Found. Comput. Sci. 28(5), 483–502 (2017)
Díaz-Caro, A., Yakaryılmaz, A.: Affine computation and affine automaton. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 146–160. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-34171-2_11
\(\check{\rm D}\)uriš, P., Hromkovič, J., Rolim, J.D.P., Schnitger, G.: Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 117–128. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0023453
Gainutdinova, A.F.: Comparative complexity of quantum and classical OBDDs for total and partial functions. Russ. Math. 59(11), 26–35 (2015)
Gainutdinova, A., Yakaryılmaz, A.: Nondeterministic unitary OBDDs. In: Weil, P. (ed.) CSR 2017. LNCS, vol. 10304, pp. 126–140. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58747-9_13
Hirvensalo, M., Moutot, E., Yakaryılmaz, A.: On the computational power of affine automata. In: Drewes, F., Martín-Vide, C., Truthe, B. (eds.) LATA 2017. LNCS, vol. 10168, pp. 405–417. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-53733-7_30
Hirvensalo, M., Seibert, S.: Lower bounds for Las Vegas automata by information theory. RAIRO Theor. Inform. Appl. 37(1), 39–49 (2003)
Hromkovič, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inf. Comput. 169(2), 284–296 (2001)
Khadiev, K.: On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs. Lobachevskii J. Math. 37(6), 682–703 (2016)
Khadiev, K., Khadieva, A.: Reordering method and hierarchies for quantum and classical ordered binary decision diagrams. In: Weil, P. (ed.) CSR 2017. LNCS, vol. 10304, pp. 162–175. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58747-9_16
Klauck, H.: On quantum and probabilistic communication: Las Vegas and one-way protocols. In: STOC 2000, pp. 644–651 (2000)
Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997)
Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theor. Comput. Sci. 237(1–2), 275–306 (2000)
Sauerhoff, M.: Quantum vs. classical read-once branching programs. In: Complexity of Boolean Functions, vol. 06111, Dagstuhl Seminar Proceedings, Internationales Begegnungs und Forschungszentrum für Informatik (2006)
Sauerhoff, M., Sieling, D.: Quantum branching programs and space-bounded nonuniform quantum complexity. Theor. Comput. Sci. 334(1), 177–225 (2005)
Savickỳ, P., Žák, S.: A read-once lower bound and a (1,+ \(k\))-hierarchy for branching programs. Theor. Comput. Sci. 238(1), 347–362 (2000)
Say, A.C.C., Yakaryılmaz, A.: Quantum finite automata: a modern introduction. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Computing with New Resources. LNCS, vol. 8808, pp. 208–222. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13350-8_16
Villagra, M., Yakaryılmaz, A.: Language recognition power and succinctness of affine automata. Nat. Comput. 17(2), 283–293 (2018). https://doi.org/10.1007/s11047-017-9652-z
Villagra, M., Yakaryılmaz, A.: Language recognition power and succinctness of affine automata. In: Amos, M., Condon, A. (eds.) UCNC 2016. LNCS, vol. 9726, pp. 116–129. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41312-9_10
Wegener, I.: Branching Programs and Binary Decision Diagrams: Theory and Applications. SIAM, Philadelphia (2000)
Nakanishi, M., Khadiev, K., Prusis, K., Vihrovs, J., Yakaryilmaz, A.: Exact affine counter automata. Electron. Proc. Theoret. Comput. Sci. (EPTCS) 252, 205–218 (2017). https://doi.org/10.4204/EPTCS.252.20
Acknowledgements
We thank Evgenijs Vihrovs (University of Latvia) for his helpful discussions and anonymous reviewers for their very helpful comments.
The work is partially supported by ERC Advanced Grant MQC, Latvian State Research Programme NeXIT project No. 1. The work is also performed according to the Russian Government Program of Competitive Growth of Kazan Federal University. The research on Las-Vegas OBDDs (Sect. 5) is supported by Russian Science Foundation Grant 17-71-10152
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 IFIP International Federation for Information Processing
About this paper
Cite this paper
Ibrahimov, R., Khadiev, K., Prūsis, K., Yakaryılmaz, A. (2018). Error-Free Affine, Unitary, and Probabilistic OBDDs. In: Konstantinidis, S., Pighizzini, G. (eds) Descriptional Complexity of Formal Systems. DCFS 2018. Lecture Notes in Computer Science(), vol 10952. Springer, Cham. https://doi.org/10.1007/978-3-319-94631-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-94631-3_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-94630-6
Online ISBN: 978-3-319-94631-3
eBook Packages: Computer ScienceComputer Science (R0)