{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T09:12:31Z","timestamp":1773393151211,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705741","type":"print"},{"value":"9783540705758","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_71","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"869-880","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Quantum Adversary Lower Bounds for Ordered Search"],"prefix":"10.1007","author":[{"given":"Andrew M.","family":"Childs","sequence":"first","affiliation":[]},{"given":"Troy","family":"Lee","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"71_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: A better lower bound for quantum algorithms searching an ordered list. In: Proc. 40th FOCS, pp. 352\u2013357 (1999)","DOI":"10.1109\/SFFCS.1999.814606"},{"issue":"4","key":"71_CR2","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. Journal of Computer and System Sciences\u00a064(4), 750\u2013767 (2002); Preliminary version in STOC 2000","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"71_CR3","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.jcss.2005.06.006","volume":"72","author":"A. Ambainis","year":"2006","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences\u00a072(2), 220\u2013238 (2006); Preliminary version in FOCS 2003","journal-title":"Journal of Computer and System Sciences"},{"key":"71_CR4","doi-asserted-by":"crossref","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum query complexity and semidefinite programming. In: Proc. 18th CCC, pp. 179\u2013193 (2003)","DOI":"10.1109\/CCC.2003.1214419"},{"issue":"4","key":"71_CR5","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\u00a048(4), 778\u2013797 (2001); Preliminary version in FOCS 1998","journal-title":"Journal of the ACM"},{"key":"71_CR6","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C.H. Bennett","year":"1997","unstructured":"Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM Journal on Computing\u00a026, 1510\u20131523 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"71_CR7","unstructured":"Ben-Or, M., Hassidim, A.: Quantum search in an ordered list via adaptive learning, quant-ph\/0703231"},{"key":"71_CR8","unstructured":"Brookes, E.M., Jacokes, M.B., Landahl, A.J.: An improved quantum algorithm for searching an ordered list (2004)"},{"issue":"5","key":"71_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0020-0190(99)00069-1","volume":"70","author":"H. Buhrman","year":"1999","unstructured":"Buhrman, H., de Wolf, R.: A lower bound for quantum search of an ordered list. Information Processing Letters\u00a070(5), 205\u2013209 (1999)","journal-title":"Information Processing Letters"},{"issue":"3","key":"71_CR10","doi-asserted-by":"publisher","first-page":"32335","DOI":"10.1103\/PhysRevA.75.032335","volume":"75","author":"A.M. Childs","year":"2007","unstructured":"Childs, A.M., Landahl, A.J., Parrilo, P.A.: Improved quantum algorithms for the ordered search problem via semidefinite programming. Physical Review A\u00a075(3), 032335 (2007)","journal-title":"Physical Review A"},{"issue":"5","key":"71_CR11","doi-asserted-by":"publisher","first-page":"301","DOI":"10.2307\/2975779","volume":"90","author":"M.-D. Choi","year":"1983","unstructured":"Choi, M.-D.: Tricks or treats with the Hilbert matrix. American Mathematical Monthly\u00a090(5), 301\u2013312 (1983)","journal-title":"American Mathematical Monthly"},{"key":"71_CR12","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: A limit on the speed of quantum computation for insertion into an ordered list, quant-ph\/9812057"},{"key":"71_CR13","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Invariant quantum algorithms for insertion into an ordered list, quant-ph\/9901059"},{"key":"71_CR14","volume-title":"Concrete Mathematics","author":"R.L. Graham","year":"1989","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison-Wesley, Reading (1989)"},{"key":"71_CR15","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"L.K. Grover","year":"1997","unstructured":"Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters\u00a079, 325\u2013328 (1997); Preliminary version in STOC 1996","journal-title":"Physical Review Letters"},{"key":"71_CR16","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P., Lee, T., \u0160palek, R.: Negative weights make adversaries stronger. In: Proc. 39th STOC, pp. 526\u2013535 (2007)","DOI":"10.1145\/1250790.1250867"},{"issue":"4","key":"71_CR17","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 complexities of ordered searching, sorting, and element distinctness. Algorithmica\u00a034(4), 429\u2013448 (2002); Preliminary version in ICALP 2001","journal-title":"Algorithmica"},{"key":"71_CR18","doi-asserted-by":"crossref","unstructured":"Laplante, S., Magniez, F.: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In: Proc. 19th CCC, pp. 294\u2013304 (2004)","DOI":"10.1109\/CCC.2004.1313852"},{"key":"71_CR19","doi-asserted-by":"crossref","unstructured":"\u0160palek, R.: The multiplicative quantum adversary. In: Proc. 23rd CCC (to appear, 2008), available at quant-ph\/0703237","DOI":"10.1109\/CCC.2008.9"},{"issue":"1","key":"71_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.2006.v002a001","volume":"2","author":"R. \u0160palek","year":"2006","unstructured":"\u0160palek, R., Szegedy, M.: All quantum adversary methods are equivalent. Theory of Computing\u00a02(1), 1\u201318 (2006); Preliminary version in ICALP 2005","journal-title":"Theory of Computing"},{"issue":"2-3","key":"71_CR21","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.tcs.2005.01.019","volume":"339","author":"S. Zhang","year":"2005","unstructured":"Zhang, S.: On the power of Ambainis\u2019s lower bounds. Theoretical Computer Science\u00a0339(2-3), 241\u2013256 (2005); Preliminary version in ICALP 2004","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_71","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:13:23Z","timestamp":1738325603000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}