{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:11:21Z","timestamp":1794381081497,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_102","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"1238-1250","source":"Crossref","is-referenced-by-count":6,"title":["On the Power of Ambainis\u2019s Lower Bounds"],"prefix":"10.1007","author":[{"given":"Shengyu","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"#cr-split#-102_CR1.1","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Quantum lower bound for the collision problem. In: Proceedings of STOC 2002, pp. 635\u2013642 (2002);","DOI":"10.1145\/509907.509999"},{"key":"#cr-split#-102_CR1.2","unstructured":"Also quant-ph\/0111102"},{"key":"#cr-split#-102_CR2.1","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Lower bounds for local search by quantum arguments. To appear in STOC 2004 (2004);","DOI":"10.1145\/1007352.1007358"},{"key":"#cr-split#-102_CR2.2","unstructured":"Also quant-ph\/0307149"},{"key":"#cr-split#-102_CR3.1","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: A better lower bound for quantum algorithms searching an ordering list. In: FOCS 1999, pp. 352\u2013357 (1999);","DOI":"10.1109\/SFFCS.1999.814606"},{"key":"#cr-split#-102_CR3.2","unstructured":"Also quant-ph\/9902053"},{"key":"#cr-split#-102_CR4.1","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. In: FOCS 2003 (2003);","DOI":"10.1109\/SFCS.2003.1238197"},{"key":"#cr-split#-102_CR4.2","unstructured":"Earlier version at quant-ph\/0305028"},{"key":"102_CR5","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1006\/jcss.2002.1826","volume":"64","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. J. Comput. Sys. Sci.\u00a064, 750\u2013767 (2002); Earlier version at STOC 2000","journal-title":"J. Comput. Sys. Sci."},{"key":"102_CR6","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Quantum query algorithms and lower bounds. In: Proceedings of FOTFS III (to appear)","DOI":"10.1007\/978-1-4020-2776-5_2"},{"key":"102_CR7","unstructured":"Ambainis, A.: Quantum lower bounds for collision and element distinctness with small range, quant-ph\/0305179"},{"key":"102_CR8","unstructured":"Ambainis, A.: Quantum walk algorithmn for element distinctness, quantph\/ 0311001"},{"key":"102_CR9","unstructured":"Barnum, H., Saks, M.: A lower bound on the quantum query complexity of readonce functions. To appear in Journal of Computer and System Science. Earlier version at ECCC TR02-002 (2002)"},{"key":"102_CR10","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum query complextiy and semidefinite programming. In: IEEE Conference on Computational Complexity (2003)"},{"key":"102_CR11","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., deWolf, R.: Quantum lower bounds by polynomials. Journal of ACM\u00a048, 778\u2013797 (2001); Earlier versions at FOCS 1998 and quant-ph\/9802049","journal-title":"Journal of ACM"},{"key":"102_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-540-24618-3_11","volume-title":"SOFSEM 2004: Theory and Practice of Computer Science","author":"Berzina","year":"2004","unstructured":"Berzina, Dubrovsky, Freivalds, Lace, Scegulnaja: Quantum query complexity for some graph problems. In: Van Emde Boas, P., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2004. LNCS, vol.\u00a02932, pp. 140\u2013150. Springer, Heidelberg (2004)"},{"key":"102_CR13","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: STOC 1998, pp. 63\u201368 (1998); quant-ph\/9802040","DOI":"10.1145\/276698.276713"},{"key":"102_CR14","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Durr, C., Heiligman, M., Hoyer, P., Magniez, F., Santha, M., De Wolf, R.: Quantum algorithms for element distinctness. In: Complexity 2001, pp. 131\u2013137 (2001); quant-ph\/0007016","DOI":"10.1109\/CCC.2001.933880"},{"issue":"1","key":"102_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\u00a0288(1), 21\u201343 (2002)","journal-title":"Theoretical Computer Science"},{"key":"102_CR16","doi-asserted-by":"crossref","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. In: Proceeding of the Royal Society of London, vol. A439, pp. 553\u2013558 (1992)","DOI":"10.1098\/rspa.1992.0167"},{"key":"102_CR17","doi-asserted-by":"crossref","unstructured":"Durr, C., Heiligman, M., H\u00f8yer, P., Mhalla, M., Lei, Y.: Quantum query complexity of some graph problems. Manuscript, cited by [21] (2003)","DOI":"10.1007\/978-3-540-27836-8_42"},{"key":"102_CR18","unstructured":"Durr, C., Mhalla, M., Lei, Y.: Quantum query complexity of graph connectivity, quant-ph\/0303169"},{"key":"102_CR19","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast quantum mechaqnical algorithm for database search. In: STOC 1996, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"102_CR20","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00453-002-0976-3","volume":"34","author":"P. H\u00f8yer","year":"2002","unstructured":"H\u00f8yer, P., Neerbek, J., Shi, Y.: Quantum lower bounds of ordered searching, sorting and element distinctness. Algorithmica\u00a034, 429\u2013448 (2002); Eearlier versions at ICALP\u201901 and quant-ph\/0102078","journal-title":"Algorithmica"},{"key":"102_CR21","unstructured":"Laplante, S., Magniez, F.: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments, quant-ph\/0311189"},{"key":"102_CR22","unstructured":"Magniez, F., Santha, M., Szegedy, M.: An O(n1.3) quantum algorithm for the Triangle problem, quant-ph\/0310134"},{"key":"102_CR23","doi-asserted-by":"crossref","unstructured":"Nayak, A., Wu, F.: The quantum query complexity of approximating the median and related statistics. In: Proceedings of STOC 1999, pp. 384\u2013393 (1999); also quantph\/ 9804066","DOI":"10.1145\/301250.301349"},{"key":"102_CR24","doi-asserted-by":"crossref","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric Boolean functions. In: STOC 1992, pp. 468\u2013474 (1992)","DOI":"10.1145\/129712.129758"},{"key":"102_CR25","unstructured":"Razborov, A.: Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Science, mathematics (2002); also quantph\/ 0204025"},{"key":"102_CR26","doi-asserted-by":"crossref","unstructured":"Saks, M., Wigderson, A.: Probabilistic boolean decision trees and the complexity of evaluating game trees. In: FOCS 1986, pp. 29\u201338 (1986)","DOI":"10.1109\/SFCS.1986.44"},{"key":"102_CR27","doi-asserted-by":"crossref","unstructured":"Santha, M.: On the Monte Carlo Boolean decision tree complexity of read-once formulae. In: Structures 1991, pp. 180\u2013187 (1991)","DOI":"10.1109\/SCT.1991.160259"},{"key":"#cr-split#-102_CR28.1","unstructured":"Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. In: FOCS 2002, pp. 513\u2013519 (2002);"},{"key":"#cr-split#-102_CR28.2","unstructured":"Earlier version at quant-ph\/0112086"},{"key":"102_CR29","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P. Shor","year":"1997","unstructured":"Shor, P.: Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing\u00a026, 1484\u20131509 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"102_CR30","unstructured":"Szegedy, M.: On the quantum query complexity of detecting triangles in graphs, quant-ph\/0310107"},{"key":"102_CR31","unstructured":"Szegedy, M.: A note on the limitations of quantum adversary method (manuscript)"},{"key":"102_CR32","unstructured":"Yao, A., Zhang, S.: Graph property and circular functions: how low can quantum query complexity go?"},{"key":"102_CR33","unstructured":"Zhang, S.: On the power of Ambainis\u2019s lower bounds, quant-ph\/0311060"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_102.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T16:31:11Z","timestamp":1740501071000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_102","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b99859","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}