{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T12:10:25Z","timestamp":1770811825993,"version":"3.50.0"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642330896","type":"print"},{"value":"9783642330902","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_30","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"337-348","source":"Crossref","is-referenced-by-count":10,"title":["The Quantum Query Complexity of Read-Many Formulas"],"prefix":"10.1007","author":[{"given":"Andrew M.","family":"Childs","sequence":"first","affiliation":[]},{"given":"Shelby","family":"Kimmel","sequence":"additional","affiliation":[]},{"given":"Robin","family":"Kothari","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"30_CR1","doi-asserted-by":"publisher","first-page":"2513","DOI":"10.1137\/080712167","volume":"39","author":"A. Ambainis","year":"2010","unstructured":"Ambainis, A., Childs, A.M., Reichardt, B.W., \u0160palek, R., Zhang, S.: Any AND-OR formula of size N can be evaluated in time N\n                1\/2\u2009+\u2009o(1) on a quantum computer. SIAM J. Comput.\u00a039(6), 2513\u20132530 (2010)","journal-title":"SIAM J. Comput."},{"key":"30_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1007\/978-3-540-92182-0_79","volume-title":"Algorithms and Computation","author":"A. Ambainis","year":"2008","unstructured":"Ambainis, A., Iwama, K., Nakanishi, M., Nishimura, H., Raymond, R., Tani, S., Yamashita, S.: Quantum Query Complexity of Boolean Functions with Small On-Sets. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 907\u2013918. Springer, Heidelberg (2008)"},{"issue":"2","key":"30_CR3","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. J. Comput. System Sci.\u00a069(2), 244\u2013258 (2004)","journal-title":"J. Comput. System Sci."},{"issue":"4","key":"30_CR4","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. J. ACM\u00a048(4), 778\u2013797 (2001)","journal-title":"J. ACM"},{"key":"30_CR5","unstructured":"Beame, P., Machmouchi, W.: The quantum query complexity of AC0. arXiv:1008.2422"},{"key":"30_CR6","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C.H. Bennett","year":"1997","unstructured":"Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput.\u00a026, 1510\u20131523 (1997)","journal-title":"SIAM J. Comput."},{"key":"30_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-540-24618-3_11","volume-title":"SOFSEM 2004: Theory and Practice of Computer Science","author":"A. Berzina","year":"2004","unstructured":"Berzina, A., Dubrovsky, A., Freivalds, R., Lace, L., Scegulnaja, O.: Quantum Query Complexity for Some Graph Problems. In: Van Emde Boas, P., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2004. LNCS, vol.\u00a02932, pp. 140\u2013150. Springer, Heidelberg (2004)"},{"issue":"4-5","key":"30_CR8","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. Fortschr. Phys.\u00a046(4-5), 493\u2013505 (1998)","journal-title":"Fortschr. Phys."},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: 30th STOC, pp. 63\u201368 (1998)","DOI":"10.1145\/276698.276713"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Buhrman, H., \u0160palek, R.: Quantum verification of matrix products. In: 17th SODA, pp. 880\u2013889 (2006)","DOI":"10.1145\/1109557.1109654"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"119","DOI":"10.4086\/toc.2009.v005a005","volume":"5","author":"A.M. Childs","year":"2009","unstructured":"Childs, A.M., Cleve, R., Jordan, S.P., Yonge-Mallo, D.: Discrete-query quantum algorithm for NAND trees. Theory Comput.\u00a05, 119\u2013123 (2009)","journal-title":"Theory Comput."},{"issue":"6","key":"30_CR12","doi-asserted-by":"publisher","first-page":"1310","DOI":"10.1137\/050644719","volume":"35","author":"C. D\u00fcrr","year":"2006","unstructured":"D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Mhalla, M.: Quantum query complexity of some graph problems. SIAM J. Comput.\u00a035(6), 1310\u20131328 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"30_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.4086\/toc.2008.v004a008","volume":"4","author":"E. Farhi","year":"2008","unstructured":"Farhi, E., Goldstone, J., Gutmann, S.: A quantum algorithm for the Hamiltonian NAND tree. Theory Comput.\u00a04(1), 169\u2013190 (2008)","journal-title":"Theory Comput."},{"issue":"24","key":"30_CR14","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.: Limit on the speed of quantum computation in determining parity. Phys. Rev. Lett.\u00a081(24), 5442\u20135444 (1998)","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"30_CR15","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. Lett.\u00a079(2), 325\u2013328 (1997)","journal-title":"Phys. Rev. Lett."},{"key":"30_CR16","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)"},{"key":"30_CR17","unstructured":"Jeffery, S., Kothari, R., Magniez, F.: Improving quantum query complexity of Boolean matrix multiplication using graph collision, arXiv:1112.5855"},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"Jukna, S.: Boolean Function Complexity. Springer (2012)","DOI":"10.1007\/978-3-642-24508-4"},{"issue":"1","key":"30_CR19","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/BF01405045","volume":"9","author":"V.M. Khrapchenko","year":"1971","unstructured":"Khrapchenko, V.M.: Complexity of the realization of a linear function in the class of \u03a0-circuits. Math. Notes\u00a09(1), 21\u201323 (1971)","journal-title":"Math. Notes"},{"key":"30_CR20","unstructured":"Kothari, R.: Formula size lower bounds for AC0 functions. Theoretical Computer Science Stack Exchange, \n                  \n                    http:\/\/cstheory.stackexchange.com\/q\/7156"},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Improved output-sensitive quantum algorithms for Boolean matrix multiplication. In: 23rd SODA, pp. 1464\u20131476 (2012)","DOI":"10.1137\/1.9781611973099.116"},{"key":"30_CR22","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/050643684","volume":"37","author":"F. Magniez","year":"2007","unstructured":"Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput.\u00a037, 413\u2013424 (2007)","journal-title":"SIAM J. Comput."},{"key":"30_CR23","first-page":"999","volume":"7","author":"E.I. Nechiporuk","year":"1966","unstructured":"Nechiporuk, E.I.: A Boolean function. Soviet Mathematics Doklady\u00a07, 999\u20131000 (1966)","journal-title":"Soviet Mathematics Doklady"},{"key":"30_CR24","unstructured":"Nisan, N.: Shortest formula for an n-term monotone CNF. Theoretical Computer Science Stack Exchange, \n                  \n                    http:\/\/cstheory.stackexchange.com\/a\/7087"},{"key":"30_CR25","doi-asserted-by":"crossref","unstructured":"Reichardt, B.: Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In: 50th FOCS, pp. 544\u2013551 (2009)","DOI":"10.1109\/FOCS.2009.55"},{"key":"30_CR26","doi-asserted-by":"crossref","unstructured":"Reichardt, B.: Reflections for quantum query algorithms. In: 22nd SODA, pp. 560\u2013569 (2011)","DOI":"10.1137\/1.9781611973082.44"},{"key":"30_CR27","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V., Williams, R.: Subcubic equivalences between path, matrix, and triangle problems. In: 51st FOCS, pp. 645\u2013654 (2010)","DOI":"10.1109\/FOCS.2010.67"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:54:53Z","timestamp":1620129293000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}