{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:07Z","timestamp":1770994087832,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540422877","type":"print"},{"value":"9783540482246","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_29","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"346-357","source":"Crossref","is-referenced-by-count":14,"title":["Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness"],"prefix":"10.1007","author":[{"given":"Peter","family":"H\u00f8yer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Neerbek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaoyun","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: A better lower bound for quantum algorithms searching an ordered list. Proc. of 40th IEEE FOCS (1999) 352\u2013357","DOI":"10.1109\/SFFCS.1999.814606"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. Proc. of 32nd ACM STOC (2000) 636\u2013643","DOI":"10.1145\/335305.335394"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., DE Wolf, R.: Quantum lower bounds by polynomials. Proc. of 39th IEEE FOCS (1998) 352\u2013361","DOI":"10.1109\/SFCS.1998.743485"},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0220017","volume":"20","author":"P. Beame","year":"1991","unstructured":"Beame, P.: A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput. 20 (1991) 270\u2013277","journal-title":"SIAM J. Comput."},{"key":"29_CR5","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C. H. Bennet","year":"1997","unstructured":"Bennet, C. H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computation. SIAM J. Comput. 26 (1997) 1510\u20131523","journal-title":"SIAM J. Comput."},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/0022-0000(81)90037-4","volume":"22","author":"A. Borodin","year":"1981","unstructured":"Borodin, A., Fischer, M. J., Kirkpatrick, D. G., Lynch, NA., Tompa, M.: A time-space tradeoff for sorting on nonoblivious machines. J. Comput. Sys. Sci. 22 (1981) 351\u2013364","journal-title":"J. Comput. Sys. Sci."},{"key":"29_CR7","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. quant-ph\/0005055, 2000"},{"key":"29_CR8","unstructured":"Buhrman, H., D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Magniez, F., Santha, M., DE Wolf, R.: Quantum algorithms for element distinctness. Proc. of 16th IEEE Computational Complexity (2001) (to appear)"},{"key":"29_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. Inform. Proc. Lett. 70 (1999) 205\u2013209","journal-title":"Inform. Proc. Lett."},{"key":"29_CR10","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. Amer. Math. Monthly 90 (1983) 301\u2013312","journal-title":"Amer. Math. Monthly"},{"key":"29_CR11","doi-asserted-by":"crossref","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, 1998","DOI":"10.1103\/PhysRevLett.81.5442"},{"key":"29_CR12","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Invariant quantum algorithms for insertion into an ordered list. quant-ph\/9901059, 1999"},{"key":"29_CR13","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF01270387","volume":"6","author":"D. Grigoriev","year":"1996","unstructured":"Grigoriev, D., Karpinski, M., Meyer AUF DER Heide, F., Smolensky, R.: A lower bound for randomized algebraic decision trees. Comput. Complexity 6 (1996\/1997) 357\u2013375","journal-title":"Comput. Complexity"},{"key":"29_CR14","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. Phys. Rev. Letters 79 (1997) 325\u2013328","journal-title":"Phys. Rev. Letters"},{"key":"29_CR15","doi-asserted-by":"crossref","first-page":"012301","DOI":"10.1103\/PhysRevA.62.012301","volume":"62","author":"R Jozsa","year":"2000","unstructured":"Jozsa, R., Schlienz, J.: Distinguishability of states and von Neumann entropy. Phys. Rev. A 62 (2000) 012301","journal-title":"Phys. Rev. A"},{"key":"29_CR16","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P. W. Shor","year":"1997","unstructured":"Shor, P. W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26 (1997) 1484\u20131509","journal-title":"SIAM J. Comput."},{"key":"29_CR17","unstructured":"Vedral, V.: The role of relative entropy in quantum information theory. quant-ph\/0102094, 2001"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"2746","DOI":"10.1103\/PhysRevA.60.2746","volume":"60","author":"Ch. Zalka","year":"1999","unstructured":"Zalka, Ch.: Grover\u2019s quantum searching algorithm is optimal. Phys. Rev. A 60 (1999) 2746\u20132751","journal-title":"Phys. Rev. A"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:28:19Z","timestamp":1556936899000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}