{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T02:48:12Z","timestamp":1775270892962,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2018,11,14]],"date-time":"2018-11-14T00:00:00Z","timestamp":1542153600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,11,14]],"date-time":"2018-11-14T00:00:00Z","timestamp":1542153600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"NWO Veni Innovational Research Grant","award":["39.021.752"],"award-info":[{"award-number":["39.021.752"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["PHY-1125565"],"award-info":[{"award-number":["PHY-1125565"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000936","name":"Gordon and Betty Moore Foundation","doi-asserted-by":"publisher","award":["GBMF-12500028"],"award-info":[{"award-number":["GBMF-12500028"]}],"id":[{"id":"10.13039\/100000936","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00453-018-0527-1","type":"journal-article","created":{"date-parts":[[2018,11,14]],"date-time":"2018-11-14T06:41:08Z","timestamp":1542177668000},"page":"2158-2195","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Approximate Span Programs"],"prefix":"10.1007","volume":"81","author":[{"given":"Tsuyoshi","family":"Ito","sequence":"first","affiliation":[]},{"given":"Stacey","family":"Jeffery","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,14]]},"reference":[{"key":"527_CR1","first-page":"1510","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. (special issue on quantum computing) 26, 1510\u20131523 (1997). arXiv:quant-ph\/9701001v1","journal-title":"SIAM J. Comput. (special issue on quantum computing)"},{"key":"527_CR2","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, 778\u2013797 (2001)","journal-title":"J. ACM"},{"key":"527_CR3","doi-asserted-by":"crossref","unstructured":"Belovs, A., Childs, A.M., Jeffery, S., Kothari, R., Magniez, F.: Time efficient quantum walks for 3-distinctness. In: Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), pp. 105\u2013122 (2013)","DOI":"10.1007\/978-3-642-39206-1_10"},{"key":"527_CR4","doi-asserted-by":"crossref","unstructured":"Belovs, A.: Learning-graph-based quantum algorithm for $$k$$-distinctness. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 207\u2013216 (2012)","DOI":"10.1109\/FOCS.2012.18"},{"key":"527_CR5","doi-asserted-by":"crossref","unstructured":"Belovs, A.: Span programs for functions with constant-sized 1-certificates. In: Proceedings of the 44th Symposium on Theory of Computing (STOC 2012), pp. 77\u201384 (2012)","DOI":"10.1145\/2213977.2213985"},{"key":"527_CR6","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Lomonaca, S.J., Brandt, H.E. (eds.) Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series Millennium Volume, pp. 53\u201374. AMS (2002). arXiv:quant-ph\/0005055v1"},{"key":"527_CR7","doi-asserted-by":"crossref","unstructured":"Belovs, A., Reichardt, B.: Span programs and quantum algorithms for $$st$$-connectivity and claw detection. In: Proceedings of the 20th European Symposium on Algorithms (ESA 2012), pp. 193\u2013204 (2012)","DOI":"10.1007\/978-3-642-33090-2_18"},{"issue":"1969","key":"527_CR8","doi-asserted-by":"publisher","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. Proc. Royal Soc. A Math. Phys. Eng. Sci. 454(1969), 339\u2013354 (1998)","journal-title":"Proc. Royal Soc. A Math. Phys. Eng. Sci."},{"issue":"4","key":"527_CR9","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01270385","volume":"6","author":"AK Chandra","year":"1996","unstructured":"Chandra, A.K., Raghavan, P., Ruzzo, W.L., Smolensky, R., Tiwari, P.: The electrical resistance of a graph captures its commute and cover times. Comput. Complex. 6(4), 312\u2013340 (1996)","journal-title":"Comput. Complex."},{"key":"527_CR10","doi-asserted-by":"crossref","DOI":"10.5948\/UPO9781614440222","volume-title":"Random Walks and Electrical Networks, volume 22 of the Carus Mathematical Monographs","author":"PG Doyle","year":"1984","unstructured":"Doyle, P.G., Snell, J.L.: Random Walks and Electrical Networks, volume 22 of the Carus Mathematical Monographs. The Mathematical Association of America, Washington (1984)"},{"key":"527_CR11","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 (STOC 1996), pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"527_CR12","doi-asserted-by":"publisher","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"AW Harrow","year":"2009","unstructured":"Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009)","journal-title":"Phys. Rev. Lett."},{"key":"527_CR13","unstructured":"Jeffery, S.: Frameworks for Quantum Algorithms. Ph.D. thesis, University of Waterloo (2014). http:\/\/uwspace.uwaterloo.ca\/handle\/10012\/8710 . Accessed 01 Jan 2015"},{"key":"527_CR14","unstructured":"Kitaev, A.: Quantum measurements and the Abelian stabilizer problem (1995). arXiv:quant-ph\/9511026"},{"key":"527_CR15","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the IEEE 8th Annual Conference on Structure in Complexity Theory, pp. 102\u2013111 (1993)","DOI":"10.1109\/SCT.1993.336536"},{"key":"527_CR16","doi-asserted-by":"crossref","unstructured":"Lee, T., Mittal, R., Reichardt, B., \u0160palek, R., Szegedy, M.: Quantum query complexity of state conversion. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), pp. 344\u2013353 (2011)","DOI":"10.1109\/FOCS.2011.75"},{"key":"527_CR17","volume-title":"Markov Chains and Mixing Times","author":"DA Levin","year":"2009","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2009)"},{"key":"527_CR18","unstructured":"Montanaro, A., de Wolf, R.: A survey of quantum property testing (2013). arXiv:1310.2035"},{"key":"527_CR19","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: Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 544\u2013551 (2009). arXiv:0904.2759 [quant-ph]","DOI":"10.1109\/FOCS.2009.55"},{"key":"527_CR20","doi-asserted-by":"crossref","unstructured":"Reichardt, B.: Reflections for quantum query algorithms. In: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 560\u2013569 (2011)","DOI":"10.1137\/1.9781611973082.44"},{"issue":"13","key":"527_CR21","doi-asserted-by":"publisher","first-page":"291","DOI":"10.4086\/toc.2012.v008a013","volume":"8","author":"B Reichardt","year":"2012","unstructured":"Reichardt, B., \u0160palek, R.: Span-program-based quantum algorithm for evaluating formulas. Theory Comput. 8(13), 291\u2013319 (2012)","journal-title":"Theory Comput."},{"key":"527_CR22","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp. 32\u201341 (2004)","DOI":"10.1109\/FOCS.2004.53"},{"key":"527_CR23","unstructured":"Wang, G.: Quantum algorithms for approximating the effective resistances in electrical networks (2013). arXiv:1311.1851"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0527-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0527-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0527-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T01:55:09Z","timestamp":1775267709000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0527-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,14]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["527"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0527-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,14]]},"assertion":[{"value":"16 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}