{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,14]],"date-time":"2026-11-14T00:20:02Z","timestamp":1794615602141,"version":"4.9.1"},"reference-count":42,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T00:00:00Z","timestamp":1724371200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Union Recovery and Resilience Facility","award":["2.3.1.1.i.0\/1\/22\/I\/CFLA\/001"],"award-info":[{"award-number":["2.3.1.1.i.0\/1\/22\/I\/CFLA\/001"]}],"id":[{"id":"https:\/\/ror.org\/019w4f821","id-type":"ROR","asserted-by":"crossref"}]},{"name":"NWO Klein","award":["OCENW.Klein.061"],"award-info":[{"award-number":["OCENW.Klein.061"]}]},{"name":"ARO","award":["W911NF2010327"],"award-info":[{"award-number":["W911NF2010327"]}]},{"name":"ERC","award":["101040624"],"award-info":[{"award-number":["101040624"]}]},{"name":"NWA-ORC","award":["1389.20.241"],"award-info":[{"award-number":["1389.20.241"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>\n                    Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>e<\/mml:mi>\n                      <mml:mi>x<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                      <mml:mi>c<\/mml:mi>\n                      <mml:mi>t<\/mml:mi>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mi>e<\/mml:mi>\n                      <mml:mi>s<\/mml:mi>\n                      <mml:mi>s<\/mml:mi>\n                    <\/mml:math>\n                    . Second, through careful accounting\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>t<\/mml:mi>\n                      <mml:mi>h<\/mml:mi>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mi>i<\/mml:mi>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mi>t<\/mml:mi>\n                      <mml:mi>i<\/mml:mi>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mi>e<\/mml:mi>\n                      <mml:mi>s<\/mml:mi>\n                      <mml:mi>s<\/mml:mi>\n                    <\/mml:math>\n                    , the total query complexity is smaller if subroutines are mostly run on cheaper inputs -- a property that is much less obvious in quantum algorithms than in their classical counterparts. While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work by two of the authors (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                        <mml:mtext class=\"MJX-tex-mathit\" mathvariant=\"italic\">quantum Las Vegas query complexity<\/mml:mtext>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    . Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>t<\/mml:mi>\n                      <mml:mi>i<\/mml:mi>\n                      <mml:mi>m<\/mml:mi>\n                      <mml:mi>e<\/mml:mi>\n                    <\/mml:math>\n                    complexity.In this work, we show how to achieve both exactness and thriftiness in the setting of time complexity. We generalize the quantum subroutine composition results of Jeffery 2022 so that, in particular, no error reduction is needed. We give a time complexity version of the well-known result in quantum query complexity,\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>Q<\/mml:mi>\n                      <mml:mo stretchy=\"false\">(<\/mml:mo>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mo>&amp;#x2218;<\/mml:mo>\n                      <mml:mi>g<\/mml:mi>\n                      <mml:mo stretchy=\"false\">)<\/mml:mo>\n                      <mml:mo>=<\/mml:mo>\n                      <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                        <mml:mi class=\"MJX-tex-caligraphic\" mathvariant=\"script\">O<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mo stretchy=\"false\">(<\/mml:mo>\n                      <mml:mi>Q<\/mml:mi>\n                      <mml:mo stretchy=\"false\">(<\/mml:mo>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mo stretchy=\"false\">)<\/mml:mo>\n                      <mml:mo>&amp;#x22C5;<\/mml:mo>\n                      <mml:mi>Q<\/mml:mi>\n                      <mml:mo stretchy=\"false\">(<\/mml:mo>\n                      <mml:mi>g<\/mml:mi>\n                      <mml:mo stretchy=\"false\">)<\/mml:mo>\n                      <mml:mo stretchy=\"false\">)<\/mml:mo>\n                    <\/mml:math>\n                    , without log factors.We achieve this by employing a novel approach to the design of quantum algorithms based on what we call\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>t<\/mml:mi>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mi>s<\/mml:mi>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mi>u<\/mml:mi>\n                      <mml:mi>c<\/mml:mi>\n                      <mml:mi>e<\/mml:mi>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mi>s<\/mml:mi>\n                    <\/mml:math>\n                    , and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, rather than only decision problems; provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.\n                  <\/jats:p>","DOI":"10.22331\/q-2024-08-23-1444","type":"journal-article","created":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T06:24:47Z","timestamp":1724394287000},"page":"1444","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":6,"title":["Taming Quantum Time Complexity"],"prefix":"10.22331","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-1625-108X","authenticated-orcid":false,"given":"Aleksandrs","family":"Belovs","sequence":"first","affiliation":[{"name":"Center for Quantum Computing Science, Faculty of Science and Technology, University of Latvia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0046-5089","authenticated-orcid":false,"given":"Stacey","family":"Jeffery","sequence":"additional","affiliation":[{"name":"QuSoft, CWI & University of Amsterdam"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Duyal","family":"Yolcu","sequence":"additional","affiliation":[{"name":"https:\/\/github.com\/qudent"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2024,8,23]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"A. Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210\u2013239, 2007. Earlier: FOCS&apos;04, arXiv:quant-ph\/0311001.","DOI":"10.1137\/S0097539705447311"},{"key":"1","doi-asserted-by":"publisher","unstructured":"A. Ambainis. Quantum search with variable times. Theory of Computing Systems, 47(3):786\u2013807, 2010. Earlier: STACS&apos;08, arXiv:quant-ph\/0609188.","DOI":"10.1007\/s00224-009-9219-1"},{"key":"2","doi-asserted-by":"publisher","unstructured":"A. Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Proc. of 29th STACS, volume 14 of LIPIcs, pages 636\u2013647. Dagstuhl, 2012. arXiv:1010.4458.","DOI":"10.4230\/LIPIcs.STACS.2012.636"},{"key":"3","doi-asserted-by":"publisher","unstructured":"A. Ambainis, A. Belovs, O. Regev, and R. de Wolf. Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. In Proc. of 27th ACM-SIAM SODA, pages 903\u2013922, 2016. arXiv:1507.03126.","DOI":"10.1137\/1.9781611974331.ch65"},{"key":"4","doi-asserted-by":"publisher","unstructured":"A. Ambainis, A. M. Childs, B. W. Reichardt, R. \u0160palek, and S. Zhang. Any AND-OR formula of size $N$ can be evaluated in time $N^{1\/2+o(1)}$ on a quantum computer. SIAM Journal on Computing, 39(6):2513\u20132530, 2010. Earlier: FOCS&apos;07.","DOI":"10.1137\/080712167"},{"key":"5","doi-asserted-by":"publisher","unstructured":"A. Ambainis, M. Kokainis, and J. Vihrovs. Improved algorithm and lower bound for variable time quantum search. In Proc. of 18th TQC, volume 266 of LIPIcs, pages 7:1\u20137:18, 2023. arXiv:2302.06749.","DOI":"10.4230\/LIPIcs.TQC.2023.7"},{"key":"6","unstructured":"P. Andr\u00e9s-Mart\u00ed nez. Unbounded loops in quantum programs: categories and weak while loops. PhD thesis, University of Edinburgh, 2022. arXiv:2212.05371."},{"key":"7","doi-asserted-by":"publisher","unstructured":"M. Bartha. Quantum Turing automata. In Proc. of 8th DCM, volume 143 of EPTCS, pages 17\u201331, 2014. arXiv:1404.0074.","DOI":"10.4204\/EPTCS.143.2"},{"key":"8","doi-asserted-by":"crossref","unstructured":"S. Beigi and L. Taghavi. Span program for non-binary functions. Quantum Information & Computation, 19(9):760\u2013\u2013792, 2019. arXiv:1805.02714.","DOI":"10.26421\/QIC19.9-10-2"},{"key":"9","doi-asserted-by":"publisher","unstructured":"A. Belovs. Learning-graph-based quantum algorithm for $k$-distinctness. In Proc. of 53rd IEEE FOCS, pages 207\u2013216, 2012. arXiv:1205.1534.","DOI":"10.1109\/FOCS.2012.18"},{"key":"10","doi-asserted-by":"publisher","unstructured":"A. Belovs. Span programs for functions with constant-sized 1-certificates. In Proc. of 44th ACM STOC, pages 77\u201384, 2012. arXiv:1105.4024.","DOI":"10.1145\/2213977.2213985"},{"key":"11","unstructured":"A. Belovs. Quantum walks and electric networks. arXiv:1302.3143, 2013."},{"key":"12","unstructured":"A. Belovs. Applications of the Adversary Method in Quantum Query Algorithms. PhD thesis, University of Latvia, 2014. arXiv:1402.3858."},{"key":"13","unstructured":"A. Belovs. Variations on quantum adversary. arXiv:1504.06943, 2015."},{"key":"14","unstructured":"A. Belovs. Global phase helps in quantum search: Yet another look at the welded tree problem. arXiv:2404.19476, 2024."},{"key":"15","doi-asserted-by":"publisher","unstructured":"A. Belovs and B. W. Reichardt. Span programs and quantum algorithms for $st$-connectivity and claw detection. In Proc. of 20th ESA, volume 7501 of LNCS, pages 193\u2013204. Springer, 2012. arXiv:1203.2603.","DOI":"10.1007\/978-3-642-33090-2_18"},{"key":"16","unstructured":"A. Belovs and D. Yolcu. One-way ticket to Las Vegas and the quantum adversary. arXiv:2301.02003, 2023."},{"key":"17","doi-asserted-by":"publisher","unstructured":"E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411\u20131473, 1997. Earlier: STOC&apos;93.","DOI":"10.1137\/S0097539796300921"},{"key":"18","doi-asserted-by":"crossref","unstructured":"G. Brassard, P. H\u00f8yer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pages 53\u201374, 2002. arXiv:quant-ph\/0005055.","DOI":"10.1090\/conm\/305\/05215"},{"key":"19","doi-asserted-by":"publisher","unstructured":"H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288:21\u201343, 2002.","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"20","doi-asserted-by":"publisher","unstructured":"A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proc. of 35th ACM STOC, pages 59\u201368, 2003. arXiv:quant-ph\/0209131.","DOI":"10.1145\/780542.780552"},{"key":"21","doi-asserted-by":"publisher","unstructured":"R. Cleve. An introduction to quantum complexity theory. arXiv:quant-ph\/9906111, 1999.","DOI":"10.1142\/9789810248185_0004"},{"key":"22","doi-asserted-by":"publisher","unstructured":"A. Cornelissen, S. Jeffery, M. Ozols, and A. Piedrafita. Span programs and quantum time complexity. In Proc. of 45th MFCS, pages 26:1\u201326:14, 2020. arXiv:2005.01323.","DOI":"10.4230\/LIPIcs.MFCS.2020.26"},{"key":"23","doi-asserted-by":"publisher","unstructured":"E. Farhi, J. Goldstone, and S. Gutmann. A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4:169\u2013190, 2008. arXiv:quant-ph\/0702144.","DOI":"10.4086\/toc.2008.v004a008"},{"key":"24","doi-asserted-by":"publisher","unstructured":"L. K. Grover. A fast quantum mechanical algorithm for database search. In Proc. of 28th ACM STOC, pages 212\u2013219, 1996. arXiv:quant-ph\/9605043.","DOI":"10.1145\/237814.237866"},{"key":"25","unstructured":"S. Jeffery. Quantum subroutine composition. arXiv:2209.14146, 2022."},{"key":"26","doi-asserted-by":"publisher","unstructured":"S. Jeffery. Span programs and quantum space complexity. Theory of Computing, 18(11):1\u201349, 2022. arXiv:1908.04232.","DOI":"10.4086\/toc.2022.v018a011"},{"key":"27","doi-asserted-by":"publisher","unstructured":"S. Jeffery and S. Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1:26, 2017. arXiv:1704.00765v3.","DOI":"10.22331\/q-2017-08-17-26"},{"key":"28","doi-asserted-by":"publisher","unstructured":"S. Jeffery and S. Zur. Multidimensional quantum walks, with application to k-distinctness. In Proc. of 55th ACM STOC, pages 1125\u20131130, 2023. arXiv:2208.13492.","DOI":"10.1145\/3564246.3585158"},{"key":"29","doi-asserted-by":"publisher","unstructured":"T. Lee, R. Mittal, B. W. Reichardt, R. \u0160palek, and M. Szegedy. Quantum query complexity of state conversion. In Proc. of 52nd IEEE FOCS, pages 344\u2013353, 2011. arXiv:1011.3020.","DOI":"10.1109\/FOCS.2011.75"},{"key":"30","doi-asserted-by":"publisher","unstructured":"N. Leonardos. An improved lower bound for the randomized decision tree complexity of recursive majority. In Proc. of 40th ICALP, Part I, volume 7965 of LNCS, pages 303\u2013314. Springer, 2013. ECCC:2012\/099.","DOI":"10.1007\/978-3-642-39206-1_59"},{"key":"31","doi-asserted-by":"publisher","unstructured":"F. Magniez, A. Nayak, M. Santha, and D. Xiao. Improved bounds for the randomized decision tree complexity of recursive majority. In Proc. of 38th ICALP, volume 6755 of LNCS, pages 317\u2013329. Springer, 2011. ECCC:2010\/192.","DOI":"10.1007\/978-3-642-22006-7_27"},{"key":"32","doi-asserted-by":"publisher","unstructured":"B. W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proc. of 50th IEEE FOCS, pages 544\u2013551, 2009. arXiv:0904.2759.","DOI":"10.1109\/FOCS.2009.55"},{"key":"33","doi-asserted-by":"publisher","unstructured":"B. W. Reichardt. Reflections for quantum query algorithms. In Proc. of 22nd ACM-SIAM SODA, pages 560\u2013569, 2011. arXiv:1005.1601.","DOI":"10.1137\/1.9781611973082.44"},{"key":"34","doi-asserted-by":"publisher","unstructured":"B. W. Reichardt. Span-program-based quantum algorithm for evaluating unbalanced formulas. In Proc. of 6th TQC, volume 6745 of LNCS, pages 73\u2013103. Springer, 2014. arXiv:0907.1622.","DOI":"10.1007\/978-3-642-54429-3_6"},{"key":"35","doi-asserted-by":"publisher","unstructured":"B. W. Reichardt and R. \u0160palek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8:291\u2013319, 2012. Earlier: STOC&apos;08, arXiv:0710.2630.","DOI":"10.4086\/toc.2012.v008a013"},{"key":"36","doi-asserted-by":"publisher","unstructured":"M. Saks and A. Wigderson. Probabilistic Boolean decision trees and the complexity of evaluating game trees. In Proc. of 27th IEEE FOCS, pages 29\u201338, 1986.","DOI":"10.1109\/SFCS.1986.44"},{"key":"37","doi-asserted-by":"publisher","unstructured":"M. Santha. On the Monte Carlo boolean decision tree complexity of read-once formulae. Random Structures and Algorithms, 6(1):75\u201387, 1995.","DOI":"10.1002\/rsa.3240060108"},{"key":"38","doi-asserted-by":"publisher","unstructured":"M. Santha. Quantum walk based search algorithms. In Proc. of 5th TAMC, volume 4978 of LNCS, pages 31\u201346. Springer, 2008. arXiv:0808.0059.","DOI":"10.1007\/978-3-540-79228-4_3"},{"key":"39","doi-asserted-by":"publisher","unstructured":"M. Snir. Lower bounds for probabilistic linear decision trees. Theoretical Computer Science, 38:69\u201382, 1985.","DOI":"10.1016\/0304-3975(85)90210-5"},{"key":"40","doi-asserted-by":"publisher","unstructured":"M. Szegedy. Quantum speed-up of Markov chain based algorithms. In Proc. of 45th IEEE FOCS, pages 32\u201341, 2004.","DOI":"10.1109\/FOCS.2004.53"},{"key":"41","doi-asserted-by":"publisher","unstructured":"B. Zhan, S. Kimmel, and A. Hassidim. Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure. In Proc. of 3rd ACM ITCS, pages 249\u2013265, 2012. arXiv:1101.0796.","DOI":"10.1145\/2090236.2090258"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-08-23-1444\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T15:36:47Z","timestamp":1794584207000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-08-23-1444\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,23]]},"references-count":42,"URL":"https:\/\/doi.org\/10.22331\/q-2024-08-23-1444","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,23]]},"article-number":"1444"}}