{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T06:25:57Z","timestamp":1774592757268,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540424871","type":"print"},{"value":"9783540446699","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_8","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"59-70","source":"Crossref","is-referenced-by-count":22,"title":["On Computational Power of Quantum Branching Programs"],"prefix":"10.1007","author":[{"given":"Farid","family":"Ablayev","sequence":"first","affiliation":[]},{"given":"Aida","family":"Gainutdinova","sequence":"additional","affiliation":[]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"8_CR1","series-title":"Lect Notes Comput Sci","first-page":"348","volume-title":"Electronic Colloquium in Computational Complexity","author":"F. Ablayev","year":"1998","unstructured":"F. Ablayev and M. Karpinski, On the power of randomized branching programs, Electronic Colloquium in Computational Complexity, ECCC TR98-004, (1998), available at http:\/\/www.eccc.uni-trier.de\/eccc\/ , also appeared in Proc. 28th ICALP (1996), LNCS Vol. 1099, Springer, 1996, 348\u2013356."},{"key":"8_CR2","unstructured":"F. Ablayev and M. Karpinski, A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs, ECCC TR98-011 (1998), available at http:\/\/www.eccc.uni-trier.de\/eccc\/ ."},{"key":"8_CR3","unstructured":"P. Alexandrov, Introduction to set theory and general topology, Berlin, 1984."},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"A. Ambainis and R. Freivalds, 1-way quantum finite automata: strengths, weaknesses and generalization, In Proceeding of the 39th IEEE Conference on Foundation of Computer Science, 1998, 332\u2013342. See also quant-ph\/9802062 v3.","DOI":"10.1109\/SFCS.1998.743469"},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. Barrington","year":"1989","unstructured":"D. Barrington, Bounded-width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC 1, Journal of Comp. and System Sci. 38, (1989), 150\u2013164.","journal-title":"NC1, Journal of Comp. and System Sci."},{"key":"8_CR6","unstructured":"A. Brodsky and N. Pippenger. Characterization of 1-way quantum finite automata. quant-ph\/9903014, available at http:\/\/xxx.lanl.gov\/archive\/quant-ph . See also its Russian mirror: http:\/\/xxx.itep.ru ."},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"R. Feynman","year":"1982","unstructured":"R. Feynman, Simulation Physics with Computers, International Journal of Theoretical Physics, (1982), 21, 467.","journal-title":"International Journal of Theoretical Physics"},{"key":"8_CR8","unstructured":"R. Freivalds, Quantum finite automata, Manuscript 2000, personal communication."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"A. Kondacs and J. Watrous. On the power of quantum finite state automata. In proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, 66\u201375.","DOI":"10.1109\/SFCS.1997.646094"},{"issue":"5","key":"8_CR10","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P. Shor","year":"1997","unstructured":"P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. on Computing, 26(5), (1997), 1484\u20131509.","journal-title":"SIAM J. on Computing"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T07:28:23Z","timestamp":1737358103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}