{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T22:24:24Z","timestamp":1748384664143,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_11","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T16:03:24Z","timestamp":1186070604000},"page":"133-144","source":"Crossref","is-referenced-by-count":3,"title":["Average-Case Quantum Query Complexity"],"prefix":"10.1007","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald","family":"de Wolf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"11_CR1","unstructured":"N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interscience, 1992."},{"issue":"1","key":"11_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539794275914","volume":"26","author":"L. Alonso","year":"1997","unstructured":"L. Alonso, E. M. Reingold, and R. Schott. The average-case complexity of determining the majority. SIAM Journal on Computing, 26(1):1\u201314, 1997.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. In Proceedings of 39th FOCS, pages 352\u2013361, 1998. http:\/\/xxx.lanl.gov\/abs\/quant-ph\/9802049 .","DOI":"10.1109\/SFCS.1998.743485"},{"issue":"5","key":"11_CR4","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C. H. Bennett","year":"1997","unstructured":"C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510\u20131523, 1997. quant-ph\/9701001.","journal-title":"SIAM Journal on Computing"},{"issue":"4\u20135","key":"11_CR5","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M. Boyer","year":"1998","unstructured":"M. Boyer, G. Brassard, P. H\u00f8yer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4\u20135):493\u2013505, 1998. Earlier version in Physcomp\u201996. quant-ph\/9605034.","journal-title":"Fortschritte der Physik"},{"key":"11_CR6","unstructured":"G. Brassard, P. H\u00f8yer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Forthcoming."},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/261342.261346","volume":"28","author":"G. Brassard","year":"1997","unstructured":"G. Brassard, P. H\u00f8yer, and A. Tapp. Quantum algorithm for the collision problem. ACM SIGACT News (Cryptology Column), 28:14\u201319, 1997. quant-ph\/9705002.","journal-title":"ACM SIGACT News (Cryptology Column)"},{"key":"11_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"820","DOI":"10.1007\/BFb0055105","volume-title":"Proceedings of 25th ICALP","author":"G. Brassard","year":"1998","unstructured":"G. Brassard, P. H\u00f8yer, and A. Tapp. Quantum counting. In Proceedings of 25th ICALP, volume 1443 of Lecture Notes in Computer Science, pages 820\u2013831. Springer, 1998. quant-ph\/9805082."},{"key":"11_CR9","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1098\/rspa.1992.0167","volume":"A439","author":"D. Deutsch","year":"1992","unstructured":"D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. In Proceedings of the Royal Society of London, volume A439, pages 553\u2013558, 1992.","journal-title":"Proceedings of the Royal Society of London"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. A limit on the speed of quantum computation in determining parity. quant-ph\/9802045, 16 Feb 1998.","DOI":"10.1103\/PhysRevLett.81.5442"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th STOC, pages 212\u2013219, 1996. quant-ph\/9605043.","DOI":"10.1145\/237814.237866"},{"key":"11_CR12","unstructured":"E. Hemaspaandra, L. A. Hemaspaandra, and M. Zimand. Almost-everywhere superiority for quantum polynomial time. quant-ph\/9910033, 8 Oct 1999."},{"issue":"1","key":"11_CR13","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. A. Levin","year":"1986","unstructured":"L. A. Levin. Average case complete problems. SIAM Journal on Computing, 15(1):285\u2013286, 1986. Earlier version in STOC\u201984.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR14","unstructured":"M. Mosca. Quantum searching, counting and amplitude amplification by eigenvector analysis. In MFCS\u201998 workshop on Randomized Algorithms, 1998."},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"A. Nayak and F. Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of 31th STOC, pages 384\u2013393, 1999. quant-ph\/9804066.","DOI":"10.1145\/301250.301349"},{"issue":"6","key":"11_CR16","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1137\/0220062","volume":"20","author":"N. Nisan","year":"1991","unstructured":"N. Nisan. CREW PRAMs and decision trees. SIAM Journal on Computing, 20(6):999\u20131007, 1991. Earlier version in STOC\u201989.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"11_CR17","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P. W. Shor","year":"1997","unstructured":"P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484\u20131509, 1997. Earlier version in FOCS\u201994. quant-ph\/9508027.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"11_CR18","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"D. Simon","year":"1997","unstructured":"D. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474\u20131483, 1997. Earlier version in FOCS\u201994.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR19","first-page":"431","volume-title":"Handbook of Theoretical Computer Science. Vol-ume A: Algorithms and Complexity","author":"J. S. Vitter","year":"1990","unstructured":"J. S. Vitter and Ph. Flajolet. Average-case analysis of algorithms and data structures. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science. Vol-ume A: Algorithms and Complexity, pages 431\u2013524. MIT Press, Cambridge, MA, 1990."},{"key":"11_CR20","doi-asserted-by":"publisher","first-page":"2746","DOI":"10.1103\/PhysRevA.60.2746","volume":"60","author":"Ch. Zalka","year":"1999","unstructured":"Ch. Zalka. Grover\u2019s quantum searching algorithm is optimal. Physical Review A, 60:2746\u20132751, 1999. quant-ph\/9711070.","journal-title":"Physical Review A"}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T02:56:27Z","timestamp":1737341787000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_11","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}