{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T00:54:59Z","timestamp":1778547299790,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,8,30]],"date-time":"2013-08-30T00:00:00Z","timestamp":1377820800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s00453-013-9826-8","type":"journal-article","created":{"date-parts":[[2013,8,29]],"date-time":"2013-08-29T18:42:47Z","timestamp":1377801767000},"page":"775-796","source":"Crossref","is-referenced-by-count":32,"title":["On Exact Quantum Query Complexity"],"prefix":"10.1007","volume":"71","author":[{"given":"Ashley","family":"Montanaro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Jozsa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Graeme","family":"Mitchison","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,8,30]]},"reference":[{"issue":"2","key":"9826_CR1","doi-asserted-by":"crossref","first-page":"165","DOI":"10.26421\/QIC3.2-7","volume":"3","author":"S. Aaronson","year":"2003","unstructured":"Aaronson, S.: Quantum lower bound for Recursive Fourier Sampling. Quantum Information and Computation 3(2), 165\u2013174 (2003). arXiv:quant-ph\/0209060","journal-title":"Quantum Information and Computation"},{"key":"9826_CR2","unstructured":"Ambainis, A.: Superlinear advantage for exact quantum algorithms (2012). arXiv:1211.0721"},{"key":"9826_CR3","unstructured":"Ambainis, A., Iraids, J., Smotrovs, J.: Exact quantum query complexity of EXACT and THRESHOLD (2013). arXiv:1302.1235"},{"key":"9826_CR4","first-page":"179","volume-title":"Proceedings of 18th Annual IEEE Conference on Computational Complexity","author":"H. Barnum","year":"2003","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum query complexity and semi-definite programming. In: Proceedings of 18th Annual IEEE Conference on Computational Complexity, pp. 179\u2013193 (2003)"},{"issue":"4","key":"9826_CR5","doi-asserted-by":"crossref","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 48(4), 778\u2013797 (2001). arXiv:quant-ph\/9802049","journal-title":"Journal of the ACM"},{"issue":"5","key":"9826_CR6","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM Journal on Computing 26(5), 1411\u20131473 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"9826_CR7","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1109\/ISTCS.1997.595153","volume-title":"Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems","author":"G. Brassard","year":"1997","unstructured":"Brassard, G., H\u00f8yer, P.: An exact quantum polynomial-time algorithm for Simon\u2019s problem. In: Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems, pp. 12\u201323 (1997). arXiv:quant-ph\/9704027"},{"key":"9826_CR8","doi-asserted-by":"crossref","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 288, 21\u201343 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"1969","key":"9826_CR9","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1098\/rspa.1998.0164","volume":"454","author":"R. Cleve","year":"1998","unstructured":"Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. Proceedings of the Royal Society, Series A 454(1969), 339\u2013354 (1998). arXiv:quant-ph\/9708016","journal-title":"Proceedings of the Royal Society, Series A"},{"issue":"3","key":"9826_CR10","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1109\/TIT.1985.1057043","volume":"31","author":"G. Cohen","year":"1985","unstructured":"Cohen, G., Karpovsky, M., Mattson, H. Jr., Schatz, J.: Covering radius\u2014survey and recent results. IEEE Transactions on Information Theory 31(3), 328\u2013343 (1985)","journal-title":"IEEE Transactions on Information Theory"},{"key":"9826_CR11","first-page":"362","volume-title":"Proceedings of 39th Annual Symposium on Foundations of Computer Science","author":"W. Dam van","year":"1998","unstructured":"van Dam, W.: Quantum oracle interrogation: Getting all information for almost half the price. In: Proceedings of 39th Annual Symposium on Foundations of Computer Science, pp. 362\u2013367. IEEE Press, New York (1998). arXiv:quant-ph\/9805006"},{"issue":"1907","key":"9826_CR12","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1098\/rspa.1992.0167","volume":"439","author":"D. Deutsch","year":"1992","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proceedings of the Royal Society, Series A 439(1907), 553\u2013558 (1992)","journal-title":"Proceedings of the Royal Society, Series A"},{"key":"9826_CR13","unstructured":"Dubrovska, A., Mischenko-Slatenkova, T.: Computing boolean functions: Exact quantum query algorithms and low degree polynomials (2006). arXiv:quant-ph\/0607022"},{"key":"9826_CR14","doi-asserted-by":"crossref","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. Physical Review Letters 81, 5442\u20135444 (1998). arXiv:quant-ph\/9802045","journal-title":"Physical Review Letters"},{"key":"9826_CR15","unstructured":"Grant, M., Boyd, S.: CVH: Matlab software for disciplined convex programming, version 1.21. http:\/\/cvxr.com\/cvx , April 2011"},{"issue":"4","key":"9826_CR16","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1007\/s00453-002-0981-6","volume":"34","author":"T. Hayes","year":"2002","unstructured":"Hayes, T., Kutin, S., van Melkebeek, D.: The quantum black-box complexity of majority. Algorithmica 34(4), 480\u2013501 (2002). arXiv:quant-ph\/0109101","journal-title":"Algorithmica"},{"key":"9826_CR17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix Analysis","author":"R.A. Horn","year":"1985","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)"},{"key":"9826_CR18","first-page":"78","volume":"87","author":"P. H\u00f8yer","year":"2005","unstructured":"H\u00f8yer, P., \u0160palek, R.: Lower bounds on quantum query complexity. Bulletin of the European Association for Theoretical Computer Science 87, 78\u2013103 (2005). arXiv:quant-ph\/0509153","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"9826_CR19","first-page":"526","volume-title":"Proc. 39th Annual ACM Symp. Theory of Computing","author":"P. H\u00f8yer","year":"2007","unstructured":"H\u00f8yer, P., Lee, T., \u0160palek, R.: Negative weights make adversaries stronger. In: Proc. 39th Annual ACM Symp. Theory of Computing, pp. 526\u2013535 (2007). arXiv:quant-ph\/0611054 . Numerical results and source code at http:\/\/www.ucw.cz\/~robert\/papers\/adv\/"},{"key":"9826_CR20","unstructured":"Midrij\u0101nis, G.: Exact quantum query complexity for total Boolean functions (2004). arXiv:quant-ph\/0403168"},{"issue":"24","key":"9826_CR21","doi-asserted-by":"crossref","first-page":"1110","DOI":"10.1016\/j.ipl.2010.09.009","volume":"110","author":"A. Montanaro","year":"2010","unstructured":"Montanaro, A.: Nonadaptive quantum query complexity. Information Processing Letters 110(24), 1110\u20131113 (2010). arXiv:1001.0018","journal-title":"Information Processing Letters"},{"key":"9826_CR22","unstructured":"Montanaro, A., Jozsa, R., Mitchison, G.: On exact quantum query complexity (2011). arXiv:1111.0475"},{"key":"9826_CR23","unstructured":"Montanaro, A., Jozsa, R., Mitchison, G.: Source code used to calculate quantum query complexity. http:\/\/www.damtp.cam.ac.uk\/user\/am994\/qc\/"},{"issue":"4","key":"9826_CR24","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of Boolean functions as real polynomials. Computational Complexity 4(4), 301\u2013313 (1994)","journal-title":"Computational Complexity"},{"key":"9826_CR25","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/1374376.1374394","volume-title":"Proceedings of 40th Annual ACM Symposium on Theory of Computing","author":"B. Reichardt","year":"2008","unstructured":"Reichardt, B., \u0160palek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proceedings of 40th Annual ACM Symposium on Theory of Computing, pp. 103\u2013112 (2008). arXiv:0710.2630"},{"key":"9826_CR26","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1137\/1.9781611973082.44","volume-title":"Proc. 22nd ACM-SIAM Symp. Discrete Algorithms","author":"B. Reichardt","year":"2011","unstructured":"Reichardt, B.: Reflections for quantum query algorithms. In: Proc. 22nd ACM-SIAM Symp. Discrete Algorithms, pp. 560\u2013569 (2011). arXiv:1005.1601"},{"key":"9826_CR27","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"D.R. Simon","year":"1997","unstructured":"Simon, D.R.: On the power of quantum computation. SIAM Journal on Computing 26, 1474\u20131483 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"9826_CR28","unstructured":"Vasilieva, A.: Quantum query algorithm constructions for computing AND, OR and MAJORITY boolean functions (2007). arXiv:0710.5592"},{"key":"9826_CR29","unstructured":"Vasilieva, A.: Exact quantum query algorithm for error detection code verification (2009). arXiv:0904.3660"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9826-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9826-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9826-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,5]],"date-time":"2022-03-05T03:24:55Z","timestamp":1646450695000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9826-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,30]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9826"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9826-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8,30]]}}}