{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T16:26:32Z","timestamp":1750436792127,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212362"},{"type":"electronic","value":"9783540247494"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24749-4_10","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T19:01:54Z","timestamp":1283972514000},"page":"105-116","source":"Crossref","is-referenced-by-count":17,"title":["Quantum Identification of Boolean Oracles"],"prefix":"10.1007","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akinori","family":"Kawachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroyuki","family":"Masuda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raymond H.","family":"Putra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shigeru","family":"Yamashita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Quantum lower bound for the collision problem. In: Proceedings of the 34th Symposium on Theory of Computing, pp. 635\u2013642 (2002)","key":"10_CR1","DOI":"10.1145\/509907.509999"},{"doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Lower bounds for local search by quantum arguments. In: Quantph\/0307149 (2003)","key":"10_CR2","DOI":"10.1145\/1007352.1007358"},{"doi-asserted-by":"crossref","unstructured":"Aaronson, S., Ambainis, A.: Quantum search of spatial regions. In: Proceedings of the 44th Symposium on Foundations of Computer Science, pp. 200\u2013209 (2003)","key":"10_CR3","DOI":"10.1109\/SFCS.2003.1238194"},{"key":"10_CR4","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, 750\u2013767 (2002)","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. In: Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 230\u2013239 (2003)","key":"10_CR5","DOI":"10.1109\/SFCS.2003.1238197"},{"unstructured":"Ambainis, A.: Quantum walks and a new quantum algorithm for element distinctness. In: Quant-ph\/0311001 (2003); (invited talk in EQIS 2003)","key":"10_CR6"},{"unstructured":"Barnum, H., Saks, M.: A lower bound on the quantum complexity of read-once functions. Electronic Colloquium on Computational Complexity (2002)","key":"10_CR7"},{"doi-asserted-by":"crossref","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum query complexity and semi-definite programming. In: Proceedings of the 18th IEEE Conference on Computational Complexity, pp. 179\u2013193 (2003)","key":"10_CR8","DOI":"10.1109\/CCC.2003.1214419"},{"doi-asserted-by":"crossref","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. In: Proceedings of 39th IEEE Symposium on Foundation of Computer Science, pp. 352\u2013361 (1998)","key":"10_CR9","DOI":"10.1109\/SFCS.1998.743485"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/3-540-49208-9_10","volume-title":"Quantum Computing and Quantum Communications","author":"D. Biron","year":"1998","unstructured":"Biron, D., Biham, O., Biham, E., Grassl, M., Lidar, D.A.: Generalized Grover Search Algorithm for Arbitrary Initial Amplitude Distribution. In: Williams, C.P. (ed.) QCQC 1998. LNCS, vol.\u00a01509, pp. 140\u2013147. Springer, Heidelberg (1998)"},{"issue":"5","key":"10_CR11","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C. Bennett","year":"1997","unstructured":"Bennett, C., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput.\u00a026(5), 1510\u20131523 (1997)","journal-title":"SIAM J. Comput."},{"issue":"4-5","key":"10_CR12","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":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik\u00a046(4-5), 493\u2013505 (1998)","journal-title":"Fortschritte der Physik"},{"doi-asserted-by":"crossref","unstructured":"Buhrman, H., D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum Algorithms for Element Distinctness. In: Proceedings of the 16th IEEE Annual Conference on Computational Complexity (CCC 2001), pp. 131\u2013137 (2001)","key":"10_CR13","DOI":"10.1109\/CCC.2001.933880"},{"issue":"5","key":"10_CR14","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput.\u00a026(5), 1411\u20131473 (1997)","journal-title":"SIAM J. Comput."},{"unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum Amplitude Amplification and Estimation. In: AMS Contemporary Mathematics Series Millennium Volume entitled Quantum Computation & Information (to appear)","key":"10_CR15"},{"key":"10_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/3-540-49208-9_11","volume-title":"Quantum Computing and Quantum Communications","author":"D.P. Chi","year":"1998","unstructured":"Chi, D.P., Kim, J.: Quantum Database Searching by a Single Query. In: Williams, C.P. (ed.) QCQC 1998. LNCS, vol.\u00a01509, pp. 148\u2013151. Springer, Heidelberg (1998)"},{"doi-asserted-by":"crossref","unstructured":"D\u00fcrr, C., Mhalla, M., Lei, Y.: Quantum query complexity of graph connectivity. In: Quant-ph\/0303169 (2003)","key":"10_CR17","DOI":"10.1007\/978-3-540-27836-8_42"},{"doi-asserted-by":"crossref","unstructured":"van Dam, W.: Quantum oracle interrogation: getting all information for almost half the price. In: Proceedings of the 39th IEEE Symposium on the Foundation of Computer Science, pp. 362\u2013367 (1998)","key":"10_CR18","DOI":"10.1109\/SFCS.1998.743486"},{"doi-asserted-by":"crossref","unstructured":"Deutsch, D., Jozsa, R.: Rapid solutions of problems by quantum computation. In: Proceedings of the Royal Society, London. Series A, vol.\u00a0439, pp. 553\u2013558 (1992)","key":"10_CR19","DOI":"10.1098\/rspa.1992.0167"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"5442","DOI":"10.1103\/PhysRevLett.81.5442","volume":"81","author":"E. Farhi","year":"1998","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: A Limit on the Speed of Quantum Computation in Determining Parity. Phys. Rev. Lett.\u00a081, 5442\u20135444 (1998)","journal-title":"Phys. Rev. Lett."},{"issue":"6","key":"10_CR21","doi-asserted-by":"publisher","first-page":"4331","DOI":"10.1103\/PhysRevA.60.4331","volume":"60","author":"E. Farhi","year":"1999","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: How many functions can be distinguished with k quantum queries? Phys. Rev. A\u00a060(6), 4331\u20134333 (1999)","journal-title":"Phys. Rev. A"},{"doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996)","key":"10_CR22","DOI":"10.1145\/237814.237866"},{"doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A framework for fast quantum mechanical algorithms. In: Proceedings of the 30th ACM Symposium on Theory of Computing, pp. 53\u201362 (1998)","key":"10_CR23","DOI":"10.1145\/276698.276712"},{"doi-asserted-by":"crossref","unstructured":"Grover, L.K.: Rapid sampling through quantum computing. In: Proceedings of the 32th ACM Symposium on Theory of Computing, pp. 618\u2013626 (2000)","key":"10_CR24","DOI":"10.1145\/335305.335389"},{"doi-asserted-by":"crossref","unstructured":"Nayak, A., Wu, F.: The quantum query complexity of approximating the median and related statistics. In: Proceedings of the 31th ACM Symposium on Theory of Computing, pp. 384\u2013393 (1999)","key":"10_CR25","DOI":"10.1145\/301250.301349"},{"unstructured":"Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. In: Proceedings of the 43rd IEEE Symposium on the Foundation of Computer Science, pp. 513\u2013519 (2002)","key":"10_CR26"},{"doi-asserted-by":"crossref","unstructured":"Vazirani, U.: On the power of quantum computation. Philosophical Transaction of the Royal Society of London, Series A\u00a0(356), 1759\u20131768 (1998)","key":"10_CR27","DOI":"10.1098\/rsta.1998.0247"}],"container-title":["Lecture Notes in Computer Science","STACS 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24749-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T17:08:26Z","timestamp":1740503306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24749-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212362","9783540247494"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24749-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}