×

Nondeterministic unitary OBDDs. (English) Zbl 1489.68060

Weil, Pascal (ed.), Computer science – theory and applications. 12th international computer science symposium in Russia, CSR 2017, Kazan, Russia, June 8–12, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10304, 126-140 (2017).
Summary: We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling sets. Then, we present classically “cheap” functions that are “expensive” for NUOBDDs and vice versa by improving the previous gap. We also present a function for which neither classical nor unitary nondeterminism does help. Moreover, based on our results, we present a width hierarchy for NUOBDDs. Lastly, we provide the bounds on the widths of NUOBDDs for the basic Boolean operations negation, union, and intersection.
For the entire collection see [Zbl 1362.68016].

MSC:

68P05 Data structures
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ablayev, F., Gainutdinova, A.: Complexity of quantum uniform and nonuniform automata. In: Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 78–87. Springer, Heidelberg (2005). doi: 10.1007/11505877_7 · Zbl 1132.68433 · doi:10.1007/11505877_7
[2] Ablayev, F., Gainutdinova, A., Karpinski, M.: On computational power of quantum branching programs. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol. 2138, pp. 59–70. Springer, Heidelberg (2001). doi: 10.1007/3-540-44669-9_8 · Zbl 0999.68071 · doi:10.1007/3-540-44669-9_8
[3] Ablayev, F.M., 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) · Zbl 1105.68037 · doi:10.1016/j.ic.2005.04.003
[4] 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). doi: 10.1007/978-3-319-09704-6_6 · Zbl 1407.68158 · doi:10.1007/978-3-319-09704-6_6
[5] Ablayev, F.M., 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) · Zbl 1407.68159 · doi:10.1134/S199508021606007X
[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). doi: 10.1007/3-540-61440-0_141 · Zbl 1046.68531 · doi:10.1007/3-540-61440-0_141
[7] Adleman, L.M., DeMarrais, J., Huang, M.D.A.: Quantum computability. SIAM J. Comput. 26(5), 1524–1540 (1997) · Zbl 0895.68043 · doi:10.1137/S0097539795293639
[8] Ambainis, A., Yakaryılmaz, A.: Automata and quantum computing. Technical report. arXiv 1507.01988
(2015) · Zbl 1237.68082
[9] Bertoni, A., Carpentieri, M.: Analogies and differences between quantum and stochastic automata. Theoret. Comput. Sci. 262(1–2), 69–81 (2001) · Zbl 0983.68094 · doi:10.1016/S0304-3975(00)00154-7
[10] Fefferman, B., Lin, C.Y.Y.: A complete characterization of unitary quantum space. Technical report, arXiv 1604.01384
(2016)
[11] Gainutdinova, A., Yakaryılmaz, A.: Nondeterministic unitary OBDDs. Technical report, arXiv 1612.07015
(2016) · Zbl 1407.68159
[12] Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: FOCS, pp. 66–75. IEEE Computer Society (1997) · doi:10.1109/SFCS.1997.646094
[13] Krause, M., Meinel, C., Waack, S.: Separating the eraser turing machine classes \[ L_e \]
, \[ NL_e \]
, \[ co \]
-
\[ NL_e \]
and \[ P_e \]
. Theor. Comput. Sci. 86(2), 267–275 (1991) · Zbl 0749.68036 · doi:10.1016/0304-3975(91)90021-S
[14] Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theoret. Comput. Sci. 237(1–2), 275–306 (2000) · Zbl 0939.68037 · doi:10.1016/S0304-3975(98)00191-1
[15] Nakanishi, M., Hamaguchi, K., Kashiwabara, T.: Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction. In: Du, D.-Z.-Z., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds.) COCOON 2000. LNCS, vol. 1858, pp. 467–476. Springer, Heidelberg (2000). doi: 10.1007/3-540-44968-X_46 · Zbl 0988.68071 · doi:10.1007/3-540-44968-X_46
[16] Nakanishi, M., Indoh, T., Hamaguchi, K., Kashiwabara, T.: On the power of non-deterministic quantum finite automata. IEICE Trans. Inf. Syst. E85–D(2), 327–332 (2002)
[17] Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000) · Zbl 1049.81015
[18] Sauerhoff, M., Sieling, D.: Quantum branching programs and space-bounded nonuniform quantum complexity. Theoret. Comput. Sci. 334(1–3), 177–225 (2005) · Zbl 1080.68029 · doi:10.1016/j.tcs.2004.12.031
[19] 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). doi: 10.1007/978-3-319-13350-8_16 · Zbl 1323.68278 · doi:10.1007/978-3-319-13350-8_16
[20] Watrous, J.: Quantum computational complexity. In: Meyers, R.A. (ed.) Encyclopedia of Complexity and System Science. Springer, New York (2009) · Zbl 1186.81048
[21] Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM (2000) · Zbl 0956.68068 · doi:10.1137/1.9780898719789
[22] Yakaryılmaz, A., Say, A.C.C.: Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput. 10(9–10), 747–770 (2010) · Zbl 1236.81071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.