{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:49Z","timestamp":1759638409418,"version":"3.35.0"},"reference-count":86,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci. China"],"published-print":{"date-parts":[[2008,6]]},"DOI":"10.1007\/s11704-008-0022-y","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T17:55:03Z","timestamp":1212515703000},"page":"193-207","source":"Crossref","is-referenced-by-count":19,"title":["An overview of quantum computation models: quantum automata"],"prefix":"10.1007","volume":"2","author":[{"given":"Daowen","family":"Qiu","sequence":"first","affiliation":[]},{"given":"Lvzhou","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,6,4]]},"reference":[{"key":"22_CR1","volume-title":"Quantum Computing","author":"J. Gruska","year":"1999","unstructured":"Gruska J. Quantum Computing. London: McGraw-Hill, 1999"},{"key":"22_CR2","volume-title":"Quantum Computation and Quantum Information","author":"M. A. Nielsen","year":"2000","unstructured":"Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000"},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"C. Bennett","year":"1973","unstructured":"Bennett C. Logical reversibility of computation. IBM Journal of Research and Development, 1973, 17: 525\u2013532","journal-title":"IBM Journal of Research and Development"},{"key":"22_CR4","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/BF01011339","volume":"22","author":"P. Benioff","year":"1980","unstructured":"Benioff P. The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Journal of Statistical Physics, 1980, 22: 563\u2013591","journal-title":"Journal of Statistical Physics"},{"key":"22_CR5","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"R. P. Feynman","year":"1982","unstructured":"Feynman R P. Simulating physics with computers. International Journal of Theoretical Physics, 1982, 21: 467\u2013488","journal-title":"International Journal of Theoretical Physics"},{"key":"22_CR6","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D. Deutsch","year":"1985","unstructured":"Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A, 1985, 400: 97\u2013117","journal-title":"Proceedings of the Royal Society of London A"},{"key":"22_CR7","unstructured":"Yao A C. Quantum circuit complexity. In: Proceedings of the 34th IEEE Symposium on Foundations of Computer science. IEEE Computer Society Press, 1993, 352\u2013361"},{"key":"22_CR8","unstructured":"Shor P W. Algorithm for quantum computation: Discrete logarithms and factoring. In: Proceedings of the37th IEEE Annuual Symposium on Foundations of Computer science. IEEE Computer Society Press, 1994, 124\u2013134"},{"key":"22_CR9","first-page":"212","volume-title":"Proceedings of the 28th Annual ACM Symposium on the Theory of Computing","author":"L. Grover","year":"1996","unstructured":"Grover L. A fast quantum mechanical algorithms for datdbase search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. New York: ACM, 1996, 212\u2013219"},{"key":"22_CR10","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"Hopcroft J E, Ullman J D. Introduction to Automata Theory, Languages, and Computation. New York: Addision-Wesley, 1979"},{"key":"22_CR11","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0304-3975(98)00191-1","volume":"237","author":"C. Moore","year":"2000","unstructured":"Moore C, Crutchfield J P. Quantum automata and quantum grammars. Theoretical Computer Science, 2000, 237: 275\u2013306. Also see arXiv: quant-ph\/9707031, 1997","journal-title":"Theoretical Computer Science"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Kondacs A, Watrous J. On the power of finite state automata. In: Proceedings of the 38th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 1997, 66\u201375","DOI":"10.1109\/SFCS.1997.646094"},{"key":"22_CR13","first-page":"332","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science","author":"A. Ambainis","year":"1998","unstructured":"Ambainis A, Freivalds R. One-way quantum finite automata: strengths, weaknesses and generalizations. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science. Palo Alfo, California: IEEE Computer Society Press, 1998, 332\u2013341, also see arXiv: quant-ph\/9802062, 1998"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Nayak A. Optimal lower bounds for quantum automata and random access codes. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 1999, 124\u2013133","DOI":"10.1109\/SFFCS.1999.814608"},{"issue":"4","key":"22_CR15","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1145\/581771.581773","volume":"49","author":"A. Ambainis","year":"2002","unstructured":"Ambainis A, Nayak A, Ta-Shma A, et al. Dense quantum coding and quantum automata. Journal of the ACM 2002, 49(4): 496\u2013511","journal-title":"Journal of the ACM"},{"key":"22_CR16","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1007\/s00224-005-1263-x","volume":"39","author":"A. Ambainis","year":"2006","unstructured":"Ambainis A, Beaudry M, Golovkins M, et al. Algebraic results on quantum automata. Theory of Computing Systems, 2006, 39: 1654\u20131188","journal-title":"Theory of Computing Systems"},{"key":"22_CR17","first-page":"368","volume-title":"Proceedings of the 31st Annual ACM Symposium on Theory of Computing","author":"M. Amano","year":"1999","unstructured":"Amano M, Iwama K. Undecidability on quantum finite automata. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing. Atlanta, Georgia: ACM Computer Society Press, 1999, 368\u2013375"},{"key":"22_CR18","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0304-3975(02)00138-X","volume":"287","author":"A. Ambainis","year":"2002","unstructured":"Ambainis A, Watrous J. Two-way finite automata with quantum and classical states. Theoretical Computer Science, 2002, 287: 299\u2013311","journal-title":"Theoretical Computer Science"},{"key":"22_CR19","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0304-3975(00)00154-7","volume":"262","author":"A. Bertoni","year":"2001","unstructured":"Bertoni A, Carpentieri M. Analogies and differences between quantum and stochastic automata. Theoretical Computer Science, 2001, 262: 69\u201381","journal-title":"Theoretical Computer Science"},{"key":"22_CR20","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1006\/inco.2000.2911","volume":"165","author":"A. Bertoni","year":"2001","unstructured":"Bertoni A, Carpentieri M. Regular Languages accepted by quantum automata. Information and Computation, 2001, 165: 174\u2013182","journal-title":"Information and Computation"},{"issue":"6","key":"22_CR21","doi-asserted-by":"crossref","first-page":"1464","DOI":"10.1137\/S0097539703425861","volume":"34","author":"V. D. Blondel","year":"2005","unstructured":"Blondel V D, Jeandel E, Koiran P, et al. Decidable and undecidable problems about quantum automata. SIAM Journal on Computing, 2005, 34(6): 1464\u20131473","journal-title":"SIAM Journal on Computing"},{"key":"22_CR22","unstructured":"Bertoni A, Mereghetti C, Palano B. Quantum computing: 1-way quantum automata. In: Proceedings of the 9th International Conference on Developments in Language Theory (DLT\u20192003), Lecture Notes in Computer Science, 2003, 2710: 1\u201320"},{"key":"22_CR23","doi-asserted-by":"crossref","first-page":"1456","DOI":"10.1137\/S0097539799353443","volume":"31","author":"A. Brodsky","year":"2002","unstructured":"Brodsky A, Pippenger N. Characterizations of 1-way quantum finite automata. SIAM Journal on Computing, 2002, 31: 1456\u20131478, also seequant-ph\/9903014, 1999","journal-title":"SIAM Journal on Computing"},{"key":"22_CR24","unstructured":"Ambainis A, Kikusts A, Valdats M. On the class of languages recognizable by 1-way quantum finite automata. In: Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, 2001, 2010: 305\u2013316"},{"issue":"1","key":"22_CR25","first-page":"9","volume":"14","author":"D. W. Qiu","year":"2003","unstructured":"Qiu D W. Characterizations of quantum automata. Journal of Software, 2003, 14(1): 9\u201315, (in Chinese)","journal-title":"Journal of Software"},{"key":"22_CR26","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1016\/j.tcs.2003.08.007","volume":"312","author":"D. W. Qiu","year":"2004","unstructured":"Qiu D W, Ying M S. Characterizations of quantum automata. Theoretical Computer Science, 2004, 312: 479\u2013489","journal-title":"Theoretical Computer Science"},{"key":"22_CR27","doi-asserted-by":"crossref","unstructured":"Qiu D W. Some observations on two-way finite automata with quantum and classical states. see quant-ph\/0701187, 2007","DOI":"10.1007\/978-3-540-87442-3_1"},{"key":"22_CR28","unstructured":"Li L Z, Qiu D W. Determining the equivalence for one-way quantum finite automata. See quant-ph\/0703087v2, 2007. Theoretical Computer Science (in press)"},{"key":"22_CR29","doi-asserted-by":"crossref","first-page":"2151","DOI":"10.1023\/A:1003692611402","volume":"39","author":"S. Gudder","year":"2000","unstructured":"Gudder S. Quantum computers. International Journal of Theoretical Physics, 2000, 39: 2151\u20132177","journal-title":"International Journal of Theoretical Physics"},{"key":"22_CR30","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1023\/A:1015731405826","volume":"41","author":"D. W. Qiu","year":"2002","unstructured":"Qiu D W. Characterization of sequential quantum machines. International Journal of Theoretical Physics, 2002, 41: 811\u2013822","journal-title":"International Journal of Theoretical Physics"},{"key":"22_CR31","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.tcs.2006.03.001","volume":"358","author":"L. Z. Li","year":"2006","unstructured":"Li L Z, Qiu D W. Determination of equivalence between quantum sequential machines. Theoretical Computer Science, 2006, 358: 65\u201374","journal-title":"Theoretical Computer Science"},{"key":"22_CR32","doi-asserted-by":"crossref","unstructured":"Golovkins M. Quantum pushdown automata. In: Proceedings of the 27th Conference on Current Trends in Theory and Practice of Informatics. Lecture Notes in Computer Science, 2000, 1963: 336\u2013346","DOI":"10.1007\/3-540-44411-4_22"},{"key":"22_CR33","doi-asserted-by":"crossref","unstructured":"Nakanishi M. On the power of one-sided error quantum pushdown automata with classical stack operations. In: Proceedings of the 10th Annual International Computing and Combinatorics Conference (COCOON 2004). Lecture Notes in Computer Science, 2004, 3106: 179\u2013187","DOI":"10.1007\/978-3-540-27798-9_21"},{"issue":"5","key":"22_CR34","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein E, Vazirani U. Quantum complexity theory. SIAM Journal on Computing, 1997, 26(5): 1411\u20131473","journal-title":"SIAM Journal on Computing"},{"key":"22_CR35","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0304-3975(01)00111-6","volume":"276","author":"H. Nishimura","year":"2002","unstructured":"Nishimura H, Ozawa M. Computational complexity of uniform quantum circuit families and quantum Turing machines. Theoretical Computer Science, 2002, 276: 147\u2013181","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"22_CR36","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1006\/jcss.1999.1655","volume":"59","author":"J. Watrous","year":"1999","unstructured":"Watrous J. Space-bounded quantum complexity. Journal of Computer and System Sciences, 1999, 59(2): 281\u2013326","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR37","unstructured":"Hirvensalo M. On quantum computation. PhD thesis, Turku Center for Computer Science, 1997"},{"key":"22_CR38","unstructured":"Qiu D W. Simulations of quantum Turing machines by quantum multi-stack machines. In: Computability in Europe (CIE2008), Athens, Greece, June 15\u201320, 2008, also see arXiv: quant-ph\/0501176, 2005"},{"issue":"2","key":"22_CR39","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1109\/TIT.2007.913263","volume":"54","author":"M. M\u00fcller","year":"2008","unstructured":"M\u00fcller M. Strongly universal quantum Turing machines and invariance of Kolmogorov complexity. IEEE Transactions on Information Theory, 2008, 54(2): 763\u2013780","journal-title":"IEEE Transactions on Information Theory"},{"key":"22_CR40","doi-asserted-by":"crossref","unstructured":"Watrous J. On one-dimensional cellular automata. In: Proceedings of the 36th IEEE Annual Symposium on Foundations of Computer Science. 1995, 528\u2013537","DOI":"10.1109\/SFCS.1995.492583"},{"issue":"4","key":"22_CR41","doi-asserted-by":"crossref","first-page":"1076","DOI":"10.1137\/S0097539797327702","volume":"31","author":"C. D\u00fcrr","year":"2002","unstructured":"D\u00fcrr C, Santha M. A decision procedure for unitary linear quantum cellular automata. SIAM Journal on Computing, 2002, 31(4): 1076\u20131089","journal-title":"SIAM Journal on Computing"},{"key":"22_CR42","first-page":"981","volume":"39","author":"M. S. Ying","year":"2000","unstructured":"Ying M S. Automata theory based on quantum logic I. International Journal of Theoretical Physics, 2000, 39: 981\u2013991","journal-title":"International Journal of Theoretical Physics"},{"key":"22_CR43","doi-asserted-by":"crossref","first-page":"2545","DOI":"10.1023\/A:1026453524064","volume":"39","author":"M. S. Ying","year":"2000","unstructured":"Ying M S. Automata theory based on quantum logic II. International Journal of Theoretical Physics, 2000, 39: 2545\u20132557","journal-title":"International Journal of Theoretical Physics"},{"issue":"1","key":"22_CR44","first-page":"23","volume":"14","author":"D. W. Qiu","year":"2003","unstructured":"Qiu D W. Automata and grammar theory based on quantum logic. Journal of Software, 2003, 14(1): 23\u201327, (in Chinese)","journal-title":"Journal of Software"},{"key":"22_CR45","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.ic.2003.11.003","volume":"190","author":"D. W. Qiu","year":"2004","unstructured":"Qiu D W. Automata theory based on quantum logic: Some characterizations. Information and Compututation, 2004, 190: 179\u2013195","journal-title":"Information and Compututation"},{"key":"22_CR46","doi-asserted-by":"crossref","first-page":"1425","DOI":"10.1023\/A:1025775827938","volume":"42","author":"R. Q. Lu","year":"2003","unstructured":"Lu R Q, Zheng H. Lattices of quantum automata. International Journal of Theoretical Physics, 2003, 42: 1425\u20131449","journal-title":"International Journal of Theoretical Physics"},{"key":"22_CR47","doi-asserted-by":"crossref","first-page":"1677","DOI":"10.1023\/A:1026135502749","volume":"42","author":"W. Cheng","year":"2003","unstructured":"Cheng W, Wang J. Grammar theory based on quantum logic. International Journal of Theoretical Physics, 2003, 42: 1677\u20131691","journal-title":"International Journal of Theoretical Physics"},{"key":"22_CR48","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.tcs.2005.04.001","volume":"344","author":"M. S. Ying","year":"2005","unstructured":"Ying M S. A theory of computation based on quantum logic (I). Theoretical Computer Science, 2005, 344: 134\u2013207","journal-title":"Theoretical Computer Science"},{"key":"22_CR49","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.tcs.2007.05.026","volume":"386","author":"D. W. Qiu","year":"2007","unstructured":"Qiu D W. Automata theory based on quantum logic: reversibilities and pushdown automata. Theoretical Computer Science, 2007, 386: 38\u201356","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"22_CR50","first-page":"154","volume":"50","author":"D. W. Qiu","year":"2007","unstructured":"Qiu D W. Notes on automata theory based on quantum logic. Science in China (Series F: Information Sciences), 2007, 50(2): 154\u2013169","journal-title":"Science in China (Series F: Information Sciences)"},{"key":"22_CR51","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M. O. Rabin","year":"1963","unstructured":"Rabin M O. Probabilistic automata. Information and Control, 1963, 6: 230\u2013244","journal-title":"Information and Control"},{"key":"22_CR52","volume-title":"Introduction to Probabilistic Automata","author":"A. Paz","year":"1971","unstructured":"Paz A. Introduction to Probabilistic Automata. New York: Academic Press, 1971"},{"key":"22_CR53","unstructured":"Li L Z, Qiu D W. A polynomial-time algorithm for the equivalence between quantum sequential machines. see arXiv: quant-ph\/0604085, 2006"},{"issue":"5","key":"22_CR54","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1137\/S0097539703432165","volume":"33","author":"A. V. Tonder","year":"2004","unstructured":"Tonder A V. A lambda calculus for quantum computation. SIAM Journal on Computing, 2004, 33(5): 1109\u20131135","journal-title":"SIAM Journal on Computing"},{"key":"22_CR55","doi-asserted-by":"crossref","first-page":"2261","DOI":"10.1023\/A:1026663432352","volume":"38","author":"S. Gudder","year":"1999","unstructured":"Gudder S. Quantum automata: An overview. International Journal of Theoretical Physics, 1999, 38: 2261\u20132282","journal-title":"International Journal of Theoretical Physics"},{"key":"22_CR56","doi-asserted-by":"crossref","unstructured":"Koshiba T. Polynomial-time algorithms for the equivalence for one-way quantum finite automata. In: Proceedings of the 12th International Symposium on Algorithms and Computation (ISAAC\u20192001), Christchurch, New Zealand, Lecture Notes in Computer Science, 2001, 2223: 268\u2013278","DOI":"10.1007\/3-540-45678-3_24"},{"key":"22_CR57","doi-asserted-by":"crossref","unstructured":"Ambainis A, Bonner R, Freivalds R, et al. Probabilities to accept languages by quantum finite automata. In: Proceedings of COCOON\u201999, Lecture Notes in Computer Science, 1999, 1627: 174\u2013183","DOI":"10.1007\/3-540-48686-0_17"},{"key":"22_CR58","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(02)00393-6","volume":"295","author":"A. Ambainisa","year":"2003","unstructured":"Ambainisa A, Kikusts A. Exact results for accepting probabilities of quantum automata. Theoretical Computer Science, 2003, 295: 3\u201325","journal-title":"Theoretical Computer Science"},{"key":"22_CR59","unstructured":"Kikusts A. A small 1-way quantum finite automaton. see arXiv: quant-ph\/9810065, 1998"},{"key":"22_CR60","doi-asserted-by":"crossref","unstructured":"Ablayev F, Gainutdinova A. On the Lower Bounds for One-Way Quantum Automata. In: Proceedings of 25th International Symposium on Mathematical Foundations of Computer Science (MFCS\u20192000), Lecture Notes in Computer Science, 2000, 1893: 132\u2013140","DOI":"10.1007\/3-540-44612-5_9"},{"key":"22_CR61","doi-asserted-by":"crossref","unstructured":"Bertoni A, Mereghetti C, Palano B. Lower Bounds on the Size of Quantum Automata Accepting Unary Languages. In: Proceedings of 8th Italian Conference on Theoretical Computer Science (ICTCS\u20192003), Lecture Notes in Computer Science, 2003, 2841: 86\u201396","DOI":"10.1007\/978-3-540-45208-9_8"},{"key":"22_CR62","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1016\/j.tcs.2005.03.032","volume":"340","author":"A. Bertoni","year":"2005","unstructured":"Bertoni A, Mereghetti C, Palano B. Small size quantum automata recognizing some regular languages. Theoretical Computer Science, 2005, 340: 394\u2013407","journal-title":"Theoretical Computer Science"},{"key":"22_CR63","doi-asserted-by":"crossref","unstructured":"Mereghetti C, Palano B. Upper Bounds on the Size of One-Way Quantum Finite Automata, In: Proceedings of the 7th Italian Conference on Theoretical Computer Science (ICTCS\u20192001), Lecture Notes in Computer Science, 2001, 2202: 123\u2013135","DOI":"10.1007\/3-540-45446-2_8"},{"key":"22_CR64","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1051\/ita:2002014","volume":"36","author":"C. Mereghetti","year":"2002","unstructured":"Mereghetti C, Palano B. On the size of one-way quantum finite automata with periodic behaviors. Theoretical Informatics and Applications, 2002, 36: 277\u2013291","journal-title":"Theoretical Informatics and Applications"},{"key":"22_CR65","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.tcs.2007.07.037","volume":"387","author":"C. Mereghetti","year":"2007","unstructured":"Mereghetti C, Palano B. Quantum automata for some multiperiodic languages. Theoretical Computer Science, 2007, 387: 177\u2013186","journal-title":"Theoretical Computer Science"},{"key":"22_CR66","unstructured":"Paschen K. Quantum finite automata using ancilla qubits. University of Karlsruhe, Technical Report, May 2000"},{"key":"22_CR67","doi-asserted-by":"crossref","unstructured":"Freivalds R. Probabilistic two-way machines. In: Proceedings of the International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 1981, 188: 33\u201345","DOI":"10.1007\/3-540-10856-4_72"},{"issue":"1","key":"22_CR68","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0022-0000(86)90045-0","volume":"33","author":"A. Greenberg","year":"1986","unstructured":"Greenberg A, Weiss A. A lower bound for probabilistic algorithms for finite state machines. Journal of Computer and System Sciences, 1986, 33(1): 88\u2013105","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR69","doi-asserted-by":"crossref","first-page":"1011","DOI":"10.1137\/0219069","volume":"19","author":"C. Dwork","year":"1990","unstructured":"Dwork C, Stockmeyer L. A time-complexity gap for two-way probabilistic finite state automata. SIAM Journal on Computing, 1990, 19: 1011\u20131023","journal-title":"SIAM Journal on Computing"},{"key":"22_CR70","doi-asserted-by":"crossref","unstructured":"Kaneps J, Freivalds R. Running time to recognize nonregular languages by 2-way probabilistic automata. In: Proceedings of the 18th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science 1991, 510: 174\u2013185","DOI":"10.1007\/3-540-54233-7_133"},{"issue":"4","key":"22_CR71","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1145\/146585.146599","volume":"39","author":"C. Dwork","year":"1992","unstructured":"Dwork C, Stockmeyer L. Finite state verifier I: the power of interaction. Journal of the ACM, 1992, 39(4): 800\u2013828","journal-title":"Journal of the ACM"},{"key":"22_CR72","doi-asserted-by":"crossref","first-page":"823","DOI":"10.2307\/1968621","volume":"37","author":"G. Birkhoff","year":"1936","unstructured":"Birkhoff G, von Neumann J. The logic of quantum mechanics. Annals of Mathematics, 1936, 37: 823\u2013843","journal-title":"Annals of Mathematics"},{"key":"22_CR73","volume-title":"Orthomodular Structures as Quantum Logics","author":"P. Pt\u00e1k","year":"1991","unstructured":"Pt\u00e1k P, Pulmannov\u00e1 S. Orthomodular Structures as Quantum Logics. Dordrecht: Kluwer, 1991"},{"issue":"6","key":"22_CR74","first-page":"419","volume":"44","author":"D. W. Qiu","year":"2001","unstructured":"Qiu D W. Automata theory based on complete residuated lattice-valued logic. Science in China (Series F: Information Sciences), 2001, 44(6): 419\u2013429","journal-title":"Science in China (Series F: Information Sciences)"},{"issue":"6","key":"22_CR75","first-page":"442","volume":"45","author":"D. W. Qiu","year":"2002","unstructured":"Qiu D W. Automata theory based on complete residuated lattice-valued logic (II). Science in China (Series F: Information Sciences), 2002, 45(6): 442\u2013452","journal-title":"Science in China (Series F: Information Sciences)"},{"key":"22_CR76","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s11225-006-7202-2","volume":"82","author":"A. Ledda","year":"2006","unstructured":"Ledda A, Konig M, Paoli F, et al. MV-algebras and quantum computation. Studia Logica, 2006, 82: 245\u2013270","journal-title":"Studia Logica"},{"key":"22_CR77","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1098\/rspa.1989.0099","volume":"400","author":"D. Deutsch","year":"1989","unstructured":"Deutsch D. Quantum computational networks. Proceedings of the Royal Society of London Series A, 1989, 400: 73\u201390","journal-title":"Proceedings of the Royal Society of London Series A"},{"issue":"5","key":"22_CR78","doi-asserted-by":"crossref","first-page":"1524","DOI":"10.1137\/S0097539795293639","volume":"26","author":"L. Adleman","year":"1997","unstructured":"Adleman L, DeMarrais J, Huang H. Quantum computability. SIAM Journal on Computing, 1997, 26(5): 1524\u20131540","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"22_CR79","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C. Bennett","year":"1997","unstructured":"Bennett C, Bernstein E, Brassard G, et al. Strengths and weaknesses of quantum computation. SIAM Journal on Computing, 1997, 26(5): 1510\u20131523","journal-title":"SIAM Journal on Computing"},{"key":"22_CR80","unstructured":"Cleve R. An Introduction to Quantum Complexity Theory. arXiv: quantph\/9906111v1, 1999"},{"issue":"2","key":"22_CR81","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1006\/jcss.1999.1651","volume":"59","author":"L. Fortnow","year":"1999","unstructured":"Fortnow L, Rogers J. Complexity limitations on quantum computation. Journal of Computer and System Sciences, 1999, 59(2): 240\u2013252","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR82","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/S0304-3975(01)00377-2","volume":"292","author":"L. Fortnow","year":"2003","unstructured":"Fortnow L. One complexity theorists view of quantum computing. Theoretical Computer Science, 2003, 292: 597\u2013610","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"22_CR83","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"D. Simon","year":"1997","unstructured":"Simon D. On the power of quantum computation. SIAM Journal on Computing, 1997, 26(5): 1474\u20131483","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"22_CR84","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2004.10.009","volume":"200","author":"H. Spakowski","year":"2005","unstructured":"Spakowski H, Thakur M, Tripathi R. Quantum and classical complexity classes: Separations, collapses, and closure properties. Information and Computation, 2005, 200(1): 1\u201334","journal-title":"Information and Computation"},{"key":"22_CR85","first-page":"41","volume-title":"Handbook of Formal Languages","author":"S. Yu","year":"1998","unstructured":"Yu S. Regular Languages. In: Rozenberg G, Salomaa A, eds. Handbook of Formal Languages. Berlin: Spring-Verlag, 1998, 41\u2013110"},{"key":"22_CR86","series-title":"Lecture Notes in Computer Science","first-page":"225","volume-title":"Proceedings of the 9th International Conference on Implementation and Application of Automata","author":"H. Nishimura","year":"2004","unstructured":"Nishimura H, Yamakami T. An application of quantum finite automata to interactive proof systems. In: Proceedings of the 9th International Conference on Implementation and Application of Automata. Lecture Notes in Computer Science. Berlin: Springer, 2004, 3317: 225\u2013236"}],"container-title":["Frontiers of Computer Science in China"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-008-0022-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11704-008-0022-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-008-0022-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T15:11:06Z","timestamp":1738249866000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11704-008-0022-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":86,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["22"],"URL":"https:\/\/doi.org\/10.1007\/s11704-008-0022-y","relation":{},"ISSN":["1673-7350","1673-7466"],"issn-type":[{"type":"print","value":"1673-7350"},{"type":"electronic","value":"1673-7466"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}