{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:20Z","timestamp":1760202680510,"version":"3.40.5"},"publisher-location":"Cham","reference-count":44,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319133492"},{"type":"electronic","value":"9783319133508"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13350-8_18","type":"book-chapter","created":{"date-parts":[[2014,12,9]],"date-time":"2014-12-09T07:46:18Z","timestamp":1418111178000},"page":"231-245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["From Quantum Query Complexity to State Complexity"],"prefix":"10.1007","author":[{"given":"Shenggen","family":"Zheng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daowen","family":"Qiu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,10]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","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 287, 299\u2013311 (2002)","journal-title":"Theoretical Computer Science"},{"key":"18_CR2","unstructured":"Ambainis, A., Freivalds, R.: One-way quantum finite automata: strengths, weaknesses and generalizations. In: Proceedings of the 39th FOCS, pp. 332\u2013341 (1998)."},{"issue":"4","key":"18_CR3","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1145\/581771.581773","volume":"49","author":"A Ambainis","year":"2002","unstructured":"Ambainis, A., Nayak, A., Ta-Shma, A., Vazirani, U.: Dense quantum coding and quantum automata. Journal of the ACM 49(4), 496\u2013511 (2002)","journal-title":"Journal of the ACM"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"1916","DOI":"10.1016\/j.tcs.2009.01.027","volume":"410","author":"A Ambainis","year":"2009","unstructured":"Ambainis, A., Nahimovs, N.: Improved constructions of quantum automata. Theoretical Computer Science 410, 1916\u20131922 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"7","key":"18_CR5","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.ipl.2012.01.001","volume":"112","author":"A Ambainis","year":"2012","unstructured":"Ambainis, A., Yakaryilmaz, A.: Superiority of exact quantum automata for promise problems. Information Processing Letters 112(7), 289\u2013291 (2012)","journal-title":"Information Processing Letters"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Superlinear advantage for exact quantum algorithms. In: Proceedings of 45th STOC, pp. 891\u2013900 (2013).","DOI":"10.1145\/2488608.2488721"},{"key":"18_CR7","unstructured":"Ambainis, A., Iraids, A., Smotrovs, J.: Exact quantum query complexity of EXACT and THRESHOLD. In: Proceedings of 8th TQC, pp. 263\u2013269 (2013)"},{"key":"18_CR8","unstructured":"Ambainis, A., Gruska, J., Zheng, S.G.: Exact query complexity of some special classes of Boolean functions, arXiv:1404.1684 (2014)"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. Journal of the ACM 48, 778\u2013797 (2001)","journal-title":"Journal of the ACM"},{"key":"18_CR10","doi-asserted-by":"publisher","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. Theoretical Computer Science 340, 394\u2013407 (2005)","journal-title":"Theoretical Computer Science"},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.tcs.2006.01.042","volume":"356","author":"A Bertoni","year":"2006","unstructured":"Bertoni, A., Mereghetti, C., Palano, B.: Some formal tools for analyzing quantum automata. Theoretical Computer Science 356, 14\u201325 (2006)","journal-title":"Theoretical Computer Science"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P.: An exact quantum polynomial-time algorithm for Simon\u2019s problem. In: Proceedings of the Israeli Symposium on Theory of Computing and Systems, pp. 12\u201323 (1997).","DOI":"10.1109\/ISTCS.1997.595153"},{"key":"18_CR13","doi-asserted-by":"publisher","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 31, 1456\u20131478 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: Proceedings of 30th STOC, pp. 63\u201368 (1998).","DOI":"10.1145\/276698.276713"},{"key":"18_CR15","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H Buhrman","year":"2002","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theoretical Computer Science 288, 21\u201343 (2002)","journal-title":"Theoretical Computer Science"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1103\/RevModPhys.82.665","volume":"82","author":"H Buhrman","year":"2010","unstructured":"Buhrman, H., Cleve, R., Massar, S., de Wolf, R.: Nonlocality and Communication Complexity. Rev. Mod. Phys. 82, 665\u2013698 (2010)","journal-title":"Rev. Mod. Phys."},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1098\/rspa.1992.0167","volume":"A439","author":"D Deutsch","year":"1992","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London A439, 553\u2013558 (1992)","journal-title":"Proceedings of the Royal Society of London"},{"issue":"1","key":"18_CR18","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1090\/S0002-9947-1987-0871675-6","volume":"300","author":"P Frankl","year":"1987","unstructured":"Frankl, P., R\u00f6dl, V.: Forbidden intersections. Trans. Amer. Math. Soc. 300(1), 259\u2013286 (1987)","journal-title":"Trans. Amer. Math. Soc."},{"key":"18_CR19","doi-asserted-by":"publisher","first-page":"1923","DOI":"10.1016\/j.tcs.2009.01.028","volume":"410","author":"R Freivalds","year":"2009","unstructured":"Freivalds, R., Ozols, M., Mancinska, L.: Improved constructions of mixed state quantum automata. Theoretical Computer Science 410, 1923\u20131931 (2009)","journal-title":"Theoretical Computer Science"},{"key":"18_CR20","unstructured":"Gruska, J.: Foundations of computing. Thomson International Computer Press (1997)."},{"key":"18_CR21","volume-title":"Quantum Computing","author":"J Gruska","year":"1999","unstructured":"Gruska, J.: Quantum Computing. McGraw-Hill, London (1999)"},{"key":"18_CR22","unstructured":"Gruska, J.: Descriptional complexity issues in quantum computing. J. Automata, Languages Combin. 5(3), 191\u2013218 (2000)."},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Gruska, J., Qiu, D.W., Zheng, S.G.: Generalizations of the distributed Deutsch-Jozsa promise problem, arXiv:1402.7254 (2014)","DOI":"10.1017\/S0960129515000158"},{"key":"18_CR24","unstructured":"Gruska, J., Qiu, D.W., Zheng, S.G.: Potential of quantum finite automata with exact acceptance, arXiv:1404.1689 (2014)"},{"key":"18_CR25","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1006\/inco.2001.3040","volume":"169","author":"J Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J., Schintger, G.: On the Power of Las Vegas for One-Way Communication Complexity. OBDDs, and Finite Automata, Information and Computation 169, 284\u2013296 (2001)","journal-title":"OBDDs, and Finite Automata, Information and Computation"},{"key":"18_CR26","doi-asserted-by":"crossref","unstructured":"Klauck, H.: On quantum and probabilistic communication: Las Vegas and one-way protocols. In: Proceedings of the 32th STOC, pp. 644\u2013651 (2000).","DOI":"10.1145\/335305.335396"},{"key":"18_CR27","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E.: Communication Complexity. Cambridge University Press (1997).","DOI":"10.1017\/CBO9780511574948"},{"key":"18_CR28","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proceedings of the 38th FOCS, pp. 66\u201375 (1997).","DOI":"10.1109\/SFCS.1997.646094"},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Exponential separation of quantum and classical online space complexity. In: Proceedings of SPAA 2006, pp. 67\u201373 (2006)","DOI":"10.1145\/1148109.1148119"},{"key":"18_CR30","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1051\/ita:2001106","volume":"35","author":"C Mereghetti","year":"2001","unstructured":"Mereghetti, C., Palano, B., Pighizzini, G.: Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. RAIRO-Inf. Theor. Appl. 35, 477\u2013490 (2001)","journal-title":"RAIRO-Inf. Theor. Appl."},{"key":"18_CR31","doi-asserted-by":"publisher","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. RAIRO-Inf. Theor. Appl. 36, 277\u2013291 (2002)","journal-title":"RAIRO-Inf. Theor. Appl."},{"key":"18_CR32","doi-asserted-by":"publisher","unstructured":"Montanaro, A., Jozsa, R., Mitchison, G.: On exact quantum query complexity, Algorithmica (2013) doi:10.1007\/s00453-013-9826-8","DOI":"10.1007\/s00453-013-9826-8"},{"key":"18_CR33","doi-asserted-by":"publisher","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 237, 275\u2013306 (2000)","journal-title":"Theoretical Computer Science"},{"key":"18_CR34","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s00236-011-0139-6","volume":"48","author":"DW Qiu","year":"2011","unstructured":"Qiu, D.W., Li, L.Z., Zou, X.F., Mateus, P., Gruska, J.: Multi-letter quantum finite automata: decidability of the equivalence and minimization of states. Acta Inf. 48, 271\u2013290 (2011)","journal-title":"Acta Inf."},{"key":"18_CR35","unstructured":"Qiu, D.W., Li, L.Z., Mateus, P., Gruska, J.: Quantum finite automata. In: Finite State Based Models and Applications, CRC Handbook, pp. 113\u2013144. CRC Press (2012)."},{"key":"18_CR36","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Some Complexity Questions Related to Distributed Computing. In: Proceedings of 11th STOC, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"},{"key":"18_CR37","first-page":"471","volume":"64","author":"S Yu","year":"2005","unstructured":"Yu, S.: State Complexity: Recent Results and Open Problems. Fundamenta Informaticae 64, 471\u2013480 (2005)","journal-title":"Fundamenta Informaticae"},{"key":"18_CR38","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1016\/j.ic.2011.01.008","volume":"209","author":"A Yakaryilmaz","year":"2011","unstructured":"Yakaryilmaz, A., Cem Say, A.C.: Unbounded-error quantum computation with small space bounds. Information and Computation 209, 873\u2013892 (2011)","journal-title":"Information and Computation"},{"issue":"4","key":"18_CR39","first-page":"19","volume":"12","author":"A Yakaryilmaz","year":"2010","unstructured":"Yakaryilmaz, A., Cem Say, A.C.: Succinctness of two-way probabilistic and quantum finite automata. Discrete Mathematics and Theoretical Computer Science 12(4), 19\u201340 (2010)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"issue":"5","key":"18_CR40","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1142\/S0129054112500141","volume":"23","author":"SG Zheng","year":"2012","unstructured":"Zheng, S.G., Qiu, D.W., Li, L.Z.: Some languages recognized by two-way finite automata with quantum and classical states. International Journal of Foundation of Computer Science 23(5), 1117\u20131129 (2012)","journal-title":"International Journal of Foundation of Computer Science"},{"key":"18_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-642-31644-9_19","volume-title":"Languages Alive","author":"SG Zheng","year":"2012","unstructured":"Zheng, S.G., Qiu, D.W., Li, L.Z., Gruska, J.: One-Way Finite Automata with Quantum and Classical States. In: Bordihn, H., Kutrib, M., Truthe, B. (eds.) Languages Alive. LNCS, vol. 7300, pp. 273\u2013290. Springer, Heidelberg (2012)"},{"key":"18_CR42","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.tcs.2013.06.005","volume":"499","author":"SG Zheng","year":"2013","unstructured":"Zheng, S.G., Qiu, D.W., Gruska, J., Li, L.Z., Mateus, P.: State succinctness of two-way finite automata with quantum and classical states. Theoretical Computer Science 499, 98\u2013112 (2013)","journal-title":"Theoretical Computer Science"},{"key":"18_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/978-3-319-04921-2_49","volume-title":"Language and Automata Theory and Applications","author":"SG Zheng","year":"2014","unstructured":"Zheng, S.G., Gruska, J., Qiu, D.W.: On the state complexity of semi-quantum finite automata. In: Dediu, A.-H., Mart\u00edn-Vide, C., Sierra-Rodr\u00edguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 601\u2013612. Springer, Heidelberg (2014)"},{"key":"18_CR44","unstructured":"Zheng, S.G., Gruska, J., Qiu, D.W.: Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata, arXiv:1304.3876 (2013)"}],"container-title":["Lecture Notes in Computer Science","Computing with New Resources"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13350-8_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T00:01:01Z","timestamp":1747180861000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13350-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319133492","9783319133508"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13350-8_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"10 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}