{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T01:10:09Z","timestamp":1746148209041,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642544286"},{"type":"electronic","value":"9783642544293"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54429-3_6","type":"book-chapter","created":{"date-parts":[[2014,3,7]],"date-time":"2014-03-07T09:33:06Z","timestamp":1394184786000},"page":"73-103","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas"],"prefix":"10.1007","author":[{"given":"Ben W.","family":"Reichardt","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,3,8]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Childs, A.M., Le Gall, F., Tani, S.: The quantum query complexity of certification. Quantum Inf. Comput. 10, 181\u2013188 (2010) (arXiv:0903.1291[quant-ph])","DOI":"10.26421\/QIC10.3-4-1"},{"issue":"6","key":"6_CR2","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}^{1\/2+o(1)}$$ on a quantum computer. SIAM J. Comput. 39(6), 2513\u20132530 (2010). (Earlier version in FOCS\u201907)","journal-title":"SIAM J. Comput."},{"key":"6_CR3","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. J. Comput. Syst. Sci. 64, 750\u2013767 (2002). (arXiv:quant-ph\/0002066. Earlier version in STOC\u201900)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.4086\/toc.2005.v001a003","volume":"1","author":"A Ambainis","year":"2005","unstructured":"Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range. Theory Comput. 1, 37\u201346 (2005). (arXiv:quant-ph\/0305179)","journal-title":"Theory Comput."},{"issue":"2","key":"6_CR5","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.jcss.2005.06.006","volume":"72","author":"A Ambainis","year":"2006","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. J. Comput. Syst. Sci. 72(2), 220\u2013238 (2006). (arXiv:quant-ph\/0305028. Earlier version in FOCS\u201903)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR6","unstructured":"Ambainis, A.: A nearly optimal discrete query quantum algorithm for evaluating NAND formulas (2007). (arXiv:0704.3628[quant-ph])"},{"issue":"4","key":"6_CR7","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 problem. J. ACM 51(4), 595\u2013605 (2004)","journal-title":"J. ACM"},{"issue":"3","key":"6_CR8","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0020-0190(94)90093-0","volume":"49","author":"ML Bonet","year":"1994","unstructured":"Bonet, M.L., Buss, S.R.: Size-depth tradeoffs for Boolean. Inf. Process. Lett. 49(3), 151\u2013155 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"6_CR9","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"CH Bennett","year":"1997","unstructured":"Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510\u20131523 (1997). (arXiv:quant-ph\/9701001)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"6_CR10","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 48(4), 778\u2013797 (2001). (arXiv:quant-ph\/9802049. Earlier version in FOCS\u201998)","journal-title":"J. ACM"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Bshouty, N.H., Cleve, R., Eberly, W.: Size-depth tradeoffs for algebraic formulae. In: Proceedings of the 32nd IEEE FOCS, pp. 334\u2013341 (1991)","DOI":"10.1109\/SFCS.1991.185387"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: Proceedings of the 30th ACM STOC, pp. 63\u201368 (1998) (arXiv:quant-ph\/9802040)","DOI":"10.1145\/276698.276713"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., de Wolf, R., Zalka, C.: Bounds for small-error and zero-error quantum algorithms. In: Proceedings of the 40th IEEE FOCS, pp. 358\u2013368 (1999) (arXiv:cs\/9904019[cs.CC])","DOI":"10.1109\/SFFCS.1999.814607"},{"issue":"2","key":"6_CR14","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. Syst. Sci. 69(2), 244\u2013258 (2004). (arXiv:quant-ph\/0201007)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum query complexity and semidefinite programming. In: Proceedings of the 18th IEEE, Complexity, pp. 179\u2013193 (2003)","DOI":"10.1109\/CCC.2003.1214419"},{"issue":"5\u20136","key":"6_CR16","first-page":"420","volume":"10","author":"C.-F. Chiang","year":"2010","unstructured":"Chiang, C.-F., Nagaj, D., Wocjan, P.: Efficient circuits for quantum walks. Quantum Inf. Comput. 10(5\u20136), 420\u2013434 (2010) (arXiv:0903.3465 [quant-ph])","journal-title":"Quantum Inf. Comput."},{"key":"6_CR17","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. 4, 169\u2013190 (2008). (arXiv:quant-ph\/0702144)","journal-title":"Theory Comput."},{"key":"6_CR18","unstructured":"Grover, L.K., Rudolph, T.: Creating superpositions that correspond to efficiently integrable probability distributions (2002) (arXiv:quant-ph\/0208112)"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th ACM STOC, pp. 212\u2013219 (1996) (arXiv:quant-ph\/9605043)","DOI":"10.1145\/237814.237866"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: Tradeoffs in the quantum search algorithm (2002) (arXiv:quant-ph\/0201152)","DOI":"10.1103\/PhysRevA.66.052314"},{"key":"6_CR21","unstructured":"H\u00f8yer, P., Lee, T., \u0160palek, R.: Tight adversary bounds for composite functions (2005) (arXiv:quant-ph\/0509067)"},{"key":"6_CR22","unstructured":"H\u00f8yer, P., Lee, T., \u0160palek, R.: Source codes of semidefinite programs for ADV$$^{\\pm }$$. http:\/\/www.ucw.cz\/robert\/papers\/adv\/ (2006)"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P., Lee, T., \u0160palek, R.: Negative weights make adversaries stronger. In: Proceedings of the 39th ACM STOC, pp. 526\u2013535 (2007) (arXiv:quant-ph\/0611054)","DOI":"10.1145\/1250790.1250867"},{"key":"6_CR24","first-page":"291","volume-title":"ICALP 2003. LNCS","author":"P H\u00f8yer","year":"2003","unstructured":"H\u00f8yer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. ICALP 2003. LNCS, vol. 2719, pp. 291\u2013299. Springer, Heidelberg (2003)"},{"issue":"4","key":"6_CR25","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 34(4), 429\u2013448 (2002). (arXiv:quant-ph\/0102078. Special issue on Quantum Computation and Cryptography)","journal-title":"Algorithmica"},{"issue":"1","key":"6_CR26","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0304-3975(93)90254-Q","volume":"107","author":"Rafi Heiman","year":"1993","unstructured":"Heiman, Rafi, Newman, Ilan, Wigderson, Avi: On read-once threshold formulae and their randomized decision tree complexity. Theoret. Comput. Sci. 107(1), 63\u201376 (1993)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"6_CR27","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF01212962","volume":"1","author":"R Heiman","year":"1991","unstructured":"Heiman, R., Wigderson, A.: Randomized vs. deterministic decision tree complexity for read-once boolean functions. Comput. Complex. 1(4), 311\u2013329 (1991). (Earlier version in Structure in Complexity Theory \u201991)","journal-title":"Comput. Complex."},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Kumar, R., Sivakumar, D.: Two applications of information complexity. In: Proceedings of the 35th ACM STOC, pp. 673\u2013682 (2003)","DOI":"10.1145\/780542.780640"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"Kitaev, A.Y., Shen, A.H., Vyalyi, M.N.: Classical and Quantum Computation, vol. 47 of Graduate Studies in Mathematics. American Mathematical Society, Providence (2002)","DOI":"10.1090\/gsm\/047"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the 8th IEEE Symposium on Structure in Complexity Theory, pp. 102\u2013111 (1993)","DOI":"10.1109\/SCT.1993.336536"},{"key":"6_CR31","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00037-006-0212-7","volume":"15","author":"S Laplante","year":"2006","unstructured":"Laplante, S., Lee, T., Szegedy, M.: The quantum adversary method and classical formula size lower bounds. Comput. Complex. 15, 163\u2013196 (2006). (arXiv:quant-ph\/0501057. Earlier version in Complexity\u201905)","journal-title":"Comput. Complex."},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Laplante, S., Magniez, F.: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In: Proceedings of the 19th IEEE, Complexity, pp. 294\u2013304 (2004) (arXiv:quant-ph\/0311189)","DOI":"10.1109\/CCC.2004.1313852"},{"key":"6_CR33","volume-title":"Quantum Computation and Quantum Information","author":"MA Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"6_CR34","doi-asserted-by":"crossref","unstructured":"Reichardt, B.W.: Span programs and quantum query complexity: the general adversary bound is nearly tight for every boolean function. Extended abstract in: Proceedings of the 50th IEEE FOCS, pp. 544\u2013551 (2009) (arXiv:0904.2759[quant-ph])","DOI":"10.1109\/FOCS.2009.55"},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Reichardt, B.W.: Faster quantum algorithm for evaluating game trees. In: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 546\u2013559 (2011) (arXiv:0907.1623[quant-ph])","DOI":"10.1137\/1.9781611973082.43"},{"key":"6_CR36","doi-asserted-by":"crossref","unstructured":"Reichardt, B.W., \u0160palek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proceedings of the 40th ACM STOC, pp. 103\u2013112 (2008) (arXiv:0710.2630[quant-ph])","DOI":"10.1145\/1374376.1374394"},{"key":"6_CR37","doi-asserted-by":"crossref","unstructured":"Santha, M.: On the Monte Carlo decision tree complexity of read-once formulae. Random Struct. Algorithms 6(1):75\u201387 (1995) (Earlier version in Proc. 6th IEEE Structure in Complexity Theory, 1991)","DOI":"10.1002\/rsa.3240060108"},{"key":"6_CR38","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(85)90210-5","volume":"38","author":"M Snir","year":"1985","unstructured":"Snir, M.: Lower bounds on probabilistic linear decision trees. Theor. Comput. Sci. 38, 69\u201382 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"6_CR39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.2006.v002a001","volume":"2","author":"R. \u0160palek","year":"2006","unstructured":"\u0160palek, R., Szegedy, M.: All quantum adversary methods are equivalent. Theor. Comput. 2(1):1\u201318 (2006) (arXiv:quant-ph\/0409116. Earlier version in ICALP\u201905)","journal-title":"Theor. Comput."},{"key":"6_CR40","doi-asserted-by":"crossref","unstructured":"Saks, M., Wigderson, A.: Probabilistic Boolean decision trees and the complexity of evaluating game trees. In: Proceedings of the 27th IEEE FOCS, pp. 29\u201338 (1986)","DOI":"10.1109\/SFCS.1986.44"},{"key":"6_CR41","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th IEEE FOCS, pp. 32\u201341 (2004)","DOI":"10.1109\/FOCS.2004.53"},{"issue":"2\u20133","key":"6_CR42","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.tcs.2005.01.019","volume":"339","author":"S. Zhang","year":"2005","unstructured":"Zhang, S.: On the power of Ambainis\u2019s lower bounds. Theor. Comput. Sci. 339(2\u20133):241\u2013256 (2005) (arXiv:quant-ph\/0311060. Earlier version in ICALP\u201904)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Theory of Quantum Computation, Communication, and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-54429-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T00:35:50Z","timestamp":1746146150000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-54429-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642544286","9783642544293"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54429-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"8 March 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}