{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T05:10:03Z","timestamp":1751001003305,"version":"3.41.0"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319710686"},{"type":"electronic","value":"9783319710693"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-71069-3_24","type":"book-chapter","created":{"date-parts":[[2017,11,18]],"date-time":"2017-11-18T03:42:41Z","timestamp":1510976561000},"page":"305-317","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Time-Space Complexity Advantages for\u00a0Quantum Computing"],"prefix":"10.1007","author":[{"given":"Shenggen","family":"Zheng","sequence":"first","affiliation":[]},{"given":"Daowen","family":"Qiu","sequence":"additional","affiliation":[]},{"given":"Jozef","family":"Gruska","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,19]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Ambainis, A.: Quantum search of spatial regions. In: Proceedings of the 44th FOCS, pp. 200\u2013209 (2003)","DOI":"10.1109\/SFCS.2003.1238194"},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Ben-David, S., Kothari, R.: Separations in query complexity using cheat sheets. In: Proceedings of the 48th STOC, pp. 863\u2013876 (2016)","DOI":"10.1145\/2897518.2897644"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Freivalds, R.: One-way quantum finite automata: strengths, weaknesses and generalizations. In: Proceedings of the 39th FOCS, pp. 332\u2013341 (1998)","DOI":"10.1109\/SFCS.1998.743469"},{"key":"24_CR4","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. TCS 287, 299\u2013311 (2002)","journal-title":"TCS"},{"key":"24_CR5","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., Vazirani, U.: Dense quantum coding and quantum finite automata. J. ACM 49, 496\u2013511 (2002)","journal-title":"J. ACM"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Superlinear advantage for exact quantum algorithms. In: Proceedings of the 45th STOC, pp. 891\u2013900 (2013)","DOI":"10.1145\/2488608.2488721"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Balodis, K., Belovs, A., Lee, T., Santha, M., Smotrovs, J.: Separations in query complexity based on pointer functions. In: Proceedings of the 48th STOC, pp. 800\u2013813 (2016)","DOI":"10.1145\/2897518.2897524"},{"key":"24_CR8","unstructured":"Ambainis, A., Kokainis, M., Kothari, R.: Nearly optimal separations between communication (or query) complexity and partitions. In: Proceedings of the 31st CCC, pp. 4:1\u20134:14 (2016)"},{"key":"24_CR9","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0211022","volume":"11","author":"A Borodin","year":"1982","unstructured":"Borodin, A., Cook, S.: A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput. 11, 287\u2013297 (1982)","journal-title":"SIAM J. Comput."},{"key":"24_CR10","first-page":"204","volume":"45","author":"L Babai","year":"1992","unstructured":"Babai, L., Nisan, N., Szegedy, M.: Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. JCSS 45, 204\u2013232 (1992)","journal-title":"JCSS"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: Proceedings of the 30th STOC, pp. 63\u201368 (1998)","DOI":"10.1145\/276698.276713"},{"key":"24_CR12","doi-asserted-by":"crossref","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. TCS 288, 21\u201343 (2002)","journal-title":"TCS"},{"key":"24_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-10856-4_72","volume-title":"Mathematical Foundations of Computer Science 1981","author":"R Freivalds","year":"1981","unstructured":"Freivalds, R.: Probabilistic two-way machines. In: Gruska, J., Chytil, M. (eds.) MFCS 1981. LNCS, vol. 118, pp. 33\u201345. Springer, Heidelberg (1981). https:\/\/doi.org\/10.1007\/3-540-10856-4_72"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Goos, M., Pitassi, T., Watson, T.: Deterministic communication vs. partition number. In: Proceedings of the 56th FOCS, pp. 1077\u20131088 (2015)","DOI":"10.1109\/FOCS.2015.70"},{"key":"24_CR15","unstructured":"Goos, M., Pitassi, T., Watson, T.: Randomized communication vs. partition number. In: Proceedings of the 44th ICALP, pp. 52:1\u201352:15 (2017)"},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th STOC, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"24_CR17","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1017\/S0960129515000158","volume":"27","author":"J Gruska","year":"2017","unstructured":"Gruska, J., Qiu, D.W., Zheng, S.G.: Generalizations of the distributed Deutsch-Jozsa promise problem. Math. Struct. Comput. Sci. 27, 311\u2013331 (2017). arXiv:1402.7254","journal-title":"Math. Struct. Comput. Sci."},{"key":"24_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-27903-2","volume-title":"Design and Analysis of Randomized Algorithms","author":"J Hromkovi\u010d","year":"2005","unstructured":"Hromkovi\u010d, J.: Design and Analysis of Randomized Algorithms. Springer, Cham (2005). https:\/\/doi.org\/10.1007\/3-540-27903-2"},{"key":"24_CR19","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":"24_CR20","doi-asserted-by":"crossref","unstructured":"Klauck, H.: Quantum time-space tradeoffs for sorting. In: Proceedings of the 35th STOC, pp. 69\u201376 (2003)","DOI":"10.1145\/780542.780553"},{"key":"24_CR21","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1137\/05063235X","volume":"36","author":"H Klauck","year":"2007","unstructured":"Klauck, H., \u0160palek, R., de Wolf, R.: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM J. Comput. 36, 1472\u20131493 (2007)","journal-title":"SIAM J. Comput."},{"key":"24_CR22","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997)"},{"key":"24_CR23","doi-asserted-by":"crossref","first-page":"1144","DOI":"10.1016\/j.jcss.2015.01.001","volume":"81","author":"LZ Li","year":"2015","unstructured":"Li, L.Z., Feng, Y.: On hybrid models of quantum finite automata. J. Comput. Syst. Sci. 81, 1144\u20131158 (2015). arXiv:1206.2131","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR24","first-page":"113","volume-title":"Handbook on Finite State Based Models and Applications","author":"DW Qiu","year":"2012","unstructured":"Qiu, D.W., Li, L.Z., Mateus, P., Gruska, J.: Quantum finite automata. In: Wang, J. (ed.) Handbook on Finite State Based Models and Applications, pp. 113\u2013141. CRC Press, Boca Raton (2012)"},{"key":"24_CR25","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A Razborov","year":"1992","unstructured":"Razborov, A.: On the distributional complexity of disjointness. TCS 106, 385\u2013390 (1992)","journal-title":"TCS"},{"key":"24_CR26","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":"24_CR27","first-page":"19","volume":"12","author":"A Yakary\u0131lmaz","year":"2010","unstructured":"Yakary\u0131lmaz, A., Say, A.C.C.: Succinctness of two-way probabilistic and quantum finite automata. Discrete Math. Theor. Comput. Sci. 12, 19\u201340 (2010)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"24_CR28","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":"S Zheng","year":"2012","unstructured":"Zheng, S., Qiu, D., Li, L., 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). https:\/\/doi.org\/10.1007\/978-3-642-31644-9_19"},{"key":"24_CR29","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1051\/ita\/2014003","volume":"48","author":"SG Zheng","year":"2014","unstructured":"Zheng, S.G., Gruska, J., Qiu, D.W.: On the state complexity of semi-quantum finite automata. RAIRO-Theor. Inform. Appl. 48, 187\u2013207 (2014). Earlier version in LATA 2014. arXiv:1307.2499","journal-title":"RAIRO-Theor. Inform. Appl."},{"key":"24_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-319-13350-8_18","volume-title":"Computing with New Resources","author":"S Zheng","year":"2014","unstructured":"Zheng, S., Qiu, D.: From quantum query complexity to state complexity. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Computing with New Resources. LNCS, vol. 8808, pp. 231\u2013245. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-13350-8_18"}],"container-title":["Lecture Notes in Computer Science","Theory and Practice of Natural Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-71069-3_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T04:30:27Z","timestamp":1750998627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-71069-3_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319710686","9783319710693"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-71069-3_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}