{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T15:13:01Z","timestamp":1768317181989,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540280613","type":"print"},{"value":"9783540318064","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_44","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T13:34:13Z","timestamp":1127828053000},"page":"430-439","source":"Crossref","is-referenced-by-count":17,"title":["Promised and Distributed Quantum Search"],"prefix":"10.1007","author":[{"given":"Shengyu","family":"Zhang","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"#cr-split#-44_CR1.1","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Ambainis, A.: Quantum search of spatial regions. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 200\u2013209 (2003);","DOI":"10.1109\/SFCS.2003.1238194"},{"key":"#cr-split#-44_CR1.2","unstructured":"Earlier version at quant-ph\/0303041"},{"issue":"4","key":"44_CR2","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/1008731.1008735","volume":"51","author":"S. Aaronson","year":"2004","unstructured":"Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM\u00a051(4), 595\u2013605 (2004)","journal-title":"Journal of the ACM"},{"key":"#cr-split#-44_CR3.1","unstructured":"Ambainis, A.: Quantum lower bounds for collision and element distinctness with small range. Theory of Computing 1(3) (2005);"},{"key":"#cr-split#-44_CR3.2","unstructured":"Earlier version at quant-ph\/0305179"},{"key":"44_CR4","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":"#cr-split#-44_CR5.1","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 22\u201331 (2004);","DOI":"10.1109\/FOCS.2004.54"},{"key":"#cr-split#-44_CR5.2","unstructured":"Earlier version at quant-ph\/0311001"},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 63\u201368 (1998)","DOI":"10.1145\/276698.276713"},{"key":"#cr-split#-44_CR7.1","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: Proceedings of Sixteenth IEEE conference on Computational Complexity, pp. 131\u2013137 (2001);","DOI":"10.1109\/CCC.2001.933880"},{"key":"#cr-split#-44_CR7.2","unstructured":"Journal version to appear in SIAM Journal of Computing"},{"issue":"1","key":"44_CR8","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":"44_CR9","unstructured":"Childs, A., Eisenberg, J.: Quantum algorithms for subset finding. quantph\/ 0311038"},{"issue":"1","key":"44_CR10","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0304-3975(02)00377-8","volume":"287","author":"R. Wolf de","year":"2002","unstructured":"de Wolf, R.: Quantum communication and complexity. Theoretical Computer Science\u00a0287(1), 337\u2013353 (2002)","journal-title":"Theoretical Computer Science"},{"key":"44_CR11","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"#cr-split#-44_CR12.1","doi-asserted-by":"crossref","unstructured":"Hoyer, P., de Wolf, R.: Improved quantum communication complexity bounds for disjointness and equality. In: Hoyer, P., R. (eds.) Proceedings of the 19th Symposium on Theoretical Aspects of Computer Science, pp. 299\u2013310 (2002);","DOI":"10.1007\/3-540-45841-7_24"},{"key":"#cr-split#-44_CR12.2","unstructured":"Earlier version at quant-ph\/0109068"},{"key":"#cr-split#-44_CR13.1","unstructured":"Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the Triangle problem. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1109\u20131117 (2005);"},{"key":"#cr-split#-44_CR13.2","unstructured":"Earlier versions at quant-ph\/0310107 and quant-ph\/0310134"},{"key":"44_CR14","doi-asserted-by":"crossref","unstructured":"Jain, R., Radhakrishnan, J., Sen, P.: A lower bound for bounded round quantum communication complexity of set disjointness. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 220\u2013229 (2003)","DOI":"10.1109\/SFCS.2003.1238196"},{"issue":"1","key":"44_CR15","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1070\/IM2003v067n01ABEH000422","volume":"67","author":"A. Razborov","year":"2003","unstructured":"Razborov, A.: Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics\u00a067(1), 145\u2013159 (2003)","journal-title":"Izvestiya: Mathematics"},{"key":"44_CR16","unstructured":"Yao, A.: Quantum circuit complexity. In: Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, pp. 352\u2013361 (1993)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T15:38:09Z","timestamp":1736005089000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11533719_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}