×

On the computational power of probabilistic and quantum branching program. (English) Zbl 1105.68037

Summary: We show that one-qubit polynomial time computations are as powerful as NC\(^1\) circuits. More generally, we define syntactic models for quantum and stochastic branching programs of bounded width and prove upper and lower bounds on their power. We show that any NC\(^1\) language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless NC\(^1 =\) ACC. This separates width-2 quantum programs from width-2 doubly stochastic programs as we show the latter cannot compute the middle bit of multiplication. Finally, we show that bounded-width quantum and stochastic programs can be simulated by classical programs of larger but bounded width, and thus are in NC\(^1\). For read-once quantum branching programs (QBPs), we give a symmetric Boolean function which is computable by a read-once QBP with \(O (\log n)\) width, but not by a deterministic read-once BP with \(o (n)\) width, or by a classical randomized read-once BP with \(o (n)\) width which is “stable” in the sense that its transitions depend on the value of the queried variable but do not vary from step to step. Finally, we present a general lower bound on the width of read-once QBPs, showing that our \(O (\log n)\) upper bound for this symmetric function is almost tight.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
81P68 Quantum computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ablayev, F.; Moore, C.; Pollett, C., Quantum and stochastic branching programs of bounded width, (Proc. 29th Intl. Colloquium on Automata. Proc. 29th Intl. Colloquium on Automata, Languages and Programming Lecture Notes in Computer Science (2002), Springer-Verlag), 343-354 · Zbl 1056.68085
[2] F. Ablayev, A. Gainutdinova, M. Karpinski, On the computational power of quantum branching, in: Proc. FCT 2001, Lecture Notes in Computer Science, vol. 2138, 2001, pp. 59-70.; F. Ablayev, A. Gainutdinova, M. Karpinski, On the computational power of quantum branching, in: Proc. FCT 2001, Lecture Notes in Computer Science, vol. 2138, 2001, pp. 59-70. · Zbl 0999.68071
[3] Ablayev, F.; Karpinski, M., On the power of randomized branching programs, (Proceedings of the ICALP’96. Proceedings of the ICALP’96, Lecture Notes in Computer Science, vol. 1099 (1996), Springer-Verlag), 348-356 · Zbl 1046.68531
[4] Ablayev, F.; Karpinski, M., A lower bound for integer multiplication on randomized ordered read-once branching programs, Informat. Comput., 186, 1, 78-89 (2003) · Zbl 1059.68045
[5] A. Ambainis, L. Schulman, U. Vazirani, Computing with highly mixed states, in: Proc. 32nd ACM Symp. on Theory of Computing, 2000, pp. 697-704.; A. Ambainis, L. Schulman, U. Vazirani, Computing with highly mixed states, in: Proc. 32nd ACM Symp. on Theory of Computing, 2000, pp. 697-704. · Zbl 1296.68054
[6] Barrington, D. A., Bounded-width polynomial branching programs recognize exactly those languages in \(NC^1\), J. Comput. Syst. Sci., 38, 1, 150-164 (1989) · Zbl 0667.68059
[7] Barrington, D. A.; Therien, D., Finite monoids and the fine structure of \(NC^1\), J. ACM, 35, 4, 941-952 (1988) · Zbl 0667.68068
[8] Borodin, A.; Razborov, A.; Smolensky, R., On lower bounds for read-\(k\)-times branching programs, Comput. Complexity, 3, 1-18 (1993) · Zbl 0777.68043
[9] Kemeny, J. G.; Snell, J. L., Finite Markov Chains (1960), Van Nostrand · Zbl 0112.09802
[10] Kondacs, A.; Watrous, J., On the power of quantum finite automata, Proc. 38th IEEE Conf. on Foundations of Computer Science, 66-75 (1997)
[11] Maurer, W.; Rhodes, J., A property of finite simple non-abelian groups, Proc. AMS, 16, 552-554 (1965) · Zbl 0132.26903
[12] Moore, C.; Crutchfield, J. P., Quantum automata and quantum grammars, Theor. Comput. Sci., 237, 275-306 (2000) · Zbl 0939.68037
[13] Moore, C.; Thérien, D.; Lemieux, F.; Berman, J.; Drisko, A., Circuits and expressions with non-associative gates, J. Comput. Syst. Sci., 60, 368-394 (2000) · Zbl 0955.68053
[14] M. Nakanishi, K. Hamaguchi, T. Kashiwabara, Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction, in: Proc. 6th Intl. Conf. on Computing and Combinatorics (COCOON), Lecture Notes in Computer Science, vol. 1858, 2000, pp. 467-476.; M. Nakanishi, K. Hamaguchi, T. Kashiwabara, Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction, in: Proc. 6th Intl. Conf. on Computing and Combinatorics (COCOON), Lecture Notes in Computer Science, vol. 1858, 2000, pp. 467-476. · Zbl 0988.68071
[15] Nielsen, M. A.; Chuang, I. L., Quantum Computation and Quantum Information (2000), Cambridge University Press: Cambridge University Press Cambridge, MA · Zbl 1049.81015
[16] Papadimitriou, C., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0833.68049
[17] Rabin, M., Probabilistic automata, Informat. Control, 6, 230-245 (1963) · Zbl 0182.33602
[18] Razborov, A. A., Lower bounds for the size of circuits of bounded depth with basis {&, ⊕}, Math. Notes Acad. Sci. USSR, 41, 4, 333-338 (1987) · Zbl 0632.94030
[19] 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
[20] Shor, P., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 5, 1484-1509 (1997) · Zbl 1005.11065
[21] R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in: Proc. 19th ACM Symposium on the Theory of Computing, 1987, pp. 77-82.; R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in: Proc. 19th ACM Symposium on the Theory of Computing, 1987, pp. 77-82.
[22] J.H. van Lint, R.M. Wilson, A Course in Combinatorics, second ed., Cambridge, 2001.; J.H. van Lint, R.M. Wilson, A Course in Combinatorics, second ed., Cambridge, 2001. · Zbl 0980.05001
[23] Wegener, I., Branching Programs and Binary Decision Diagrams, SIAM Monographs Discrete Math. Appl. (2000) · Zbl 0956.68068
[24] A.C. Yao, Lower bounds by probabilistic arguments, in: Proc. 24th IEEE Conf. on Foundations of Computer Science, 1983, pp. 420-428.; A.C. Yao, Lower bounds by probabilistic arguments, in: Proc. 24th IEEE Conf. on Foundations of Computer Science, 1983, pp. 420-428.
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.