{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T04:20:26Z","timestamp":1773462026835,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540275800","type":"print"},{"value":"9783540316916","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11523468_105","type":"book-chapter","created":{"date-parts":[[2010,7,18]],"date-time":"2010-07-18T18:58:59Z","timestamp":1279479539000},"page":"1299-1311","source":"Crossref","is-referenced-by-count":10,"title":["All Quantum Adversary Methods Are Equivalent"],"prefix":"10.1007","author":[{"given":"Robert","family":"\u0160palek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"105_CR1","doi-asserted-by":"crossref","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum decision trees and semidefinite programming. In: Proc. of the 18th IEEE Conference on Computational Complexity, pp. 179\u2013193 (2003)","DOI":"10.1109\/CCC.2003.1214419"},{"key":"105_CR2","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. In: Proc. of the 44th IEEE Symp. on Foundations of Computer Science, pp. 230\u2013239 (2003)","DOI":"10.1109\/SFCS.2003.1238197"},{"key":"105_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1238","DOI":"10.1007\/978-3-540-27836-8_102","volume-title":"Automata, Languages and Programming","author":"S. Zhang","year":"2004","unstructured":"Zhang, S.: On the power of ambainis\u2019s lower bounds. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1238\u20131250. Springer, Heidelberg (2004)"},{"key":"105_CR4","doi-asserted-by":"crossref","unstructured":"Laplante, S., Magniez, F.: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In: Proceedings of 19th IEEE Conference on Computational Complexity, pp. 294\u2013304 (2004); 294\u2013304 quant-ph\/0311189","DOI":"10.1109\/CCC.2004.1313852"},{"key":"105_CR5","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"H. Bennett","year":"1997","unstructured":"Bennett, H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM Journal on Computing\u00a026, 1510\u20131523 (1997); quant-ph\/9701001","journal-title":"SIAM Journal on Computing"},{"key":"105_CR6","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, 778\u2013797 (2001); Earlier version in FOCS 1998 (1998) quant-ph\/9802049.","journal-title":"Journal of the ACM"},{"key":"105_CR7","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); Earlier version in STOC 2000 (2000) quant-ph\/0002066.","journal-title":"Journal of Computer and System Sciences"},{"key":"105_CR8","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of 28th ACM STOC, pp. 212\u2013219 (1996); quant-ph\/9605043","DOI":"10.1145\/237814.237866"},{"key":"105_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/3-540-45061-0_25","volume-title":"Automata, Languages and Programming","author":"P. H\u00f8yer","year":"2003","unstructured":"H\u00f8yer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 291\u2013299. Springer, Heidelberg (2003); quant-ph\/0304052"},{"key":"105_CR10","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, 429\u2013448 (2002); Special issue on Quantum Computation and Cryptography. quant-ph\/0102078","journal-title":"Algorithmica"},{"key":"105_CR11","unstructured":"Szegedy, M.: On the quantum query complexity of detecting triangles in graphs (2003); quant-ph\/0310107"},{"key":"105_CR12","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 problem. Journal of the ACM\u00a051, 595\u2013605 (2004); quant-ph\/0111102","journal-title":"Journal of the ACM"},{"key":"105_CR13","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. In: Proceedings of 45th IEEE FOCS, pp. 22\u201331 (2004); quant-ph\/0311001","DOI":"10.1109\/FOCS.2004.54"},{"key":"105_CR14","doi-asserted-by":"crossref","unstructured":"Saks, M., Wigderson, A.: Probabilistic Boolean decision trees and the complexity of evaluating games trees. In: Proc. of the 27th Annual Symp. on FOCS, pp. 29\u201338 (1986)","DOI":"10.1109\/SFCS.1986.44"},{"key":"105_CR15","unstructured":"Laplante, S., Lee, T., Szegedy, M.: The quantum adversary method and formula size lower bounds. In: Proceedings of 20th IEEE Conference on Computational Complexity (2005) (to appear); quant-ph\/0501057"},{"key":"105_CR16","unstructured":"Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. In: Proceedings of 16th SODA, pp. 1109\u20131117 (2005); quant-ph\/0310134"},{"key":"105_CR17","volume-title":"Quantum Computation and Quantum Information","author":"M.A. Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"105_CR18","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, 21\u201343 (2002)","journal-title":"Theoretical Computer Science"},{"key":"105_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer, Berlin (1997)","edition":"2"},{"key":"105_CR20","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0024-3795(90)90403-Y","volume":"139","author":"R. Mathias","year":"1990","unstructured":"Mathias, R.: The spectral norm of a nonnegative matrix. Linear Algebra and its Applications\u00a0139, 269\u2013284 (1990)","journal-title":"Linear Algebra and its Applications"},{"key":"105_CR21","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.jcss.2004.02.002","volume":"69","author":"H. Barnum","year":"2004","unstructured":"Barnum, H., Saks, M.: A lower bound on the quantum query complexity of read-once functions. Journal of Computer and Systems Sciences\u00a069, 244\u2013258 (2004); quant-ph\/0201007","journal-title":"Journal of Computer and Systems Sciences"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11523468_105.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T02:35:21Z","timestamp":1740278121000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11523468_105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540275800","9783540316916"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11523468_105","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}