Taming Quantum Time Complexity

Aleksandrs Belovs; Stacey Jeffery; Duyal Yolcu

doi:10.22331/q-2024-08-23-1444

Taming Quantum Time Complexity

Aleksandrs Belovs¹, Stacey Jeffery², and Duyal Yolcu³

¹Center for Quantum Computing Science, Faculty of Science and Technology, University of Latvia
²QuSoft, CWI & University of Amsterdam
³https://github.com/qudent

Published:	2024-08-23, volume 8, page 1444
Eprint:	arXiv:2311.15873v3
Doi:	https://doi.org/10.22331/q-2024-08-23-1444
Citation:	Quantum 8, 1444 (2024).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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 $exactness$. Second, through careful accounting $thriftiness$, 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 $\textit{quantum Las Vegas query complexity}$. Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum $time$ 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, $Q(f\circ g)=\mathcal{O}(Q(f)\cdot Q(g))$, without log factors.

We achieve this by employing a novel approach to the design of quantum algorithms based on what we call $transducers$, 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.

Featured image: A graphical illustration of how a transducer is implemented on a quantum computer. Transducers are the main novel technical tool of the paper.

► BibTeX data

@article{Belovs2024tamingquantumtime,
  doi = {10.22331/q-2024-08-23-1444},
  url = {https://doi.org/10.22331/q-2024-08-23-1444},
  title = {Taming {Q}uantum {T}ime {C}omplexity},
  author = {Belovs, Aleksandrs and Jeffery, Stacey and Yolcu, Duyal},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1444},
  month = aug,
  year = {2024}
}

► References

[1] A. Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210–239, 2007. Earlier: FOCS'04, arXiv:quant-ph/0311001.
https://doi.org/10.1137/S0097539705447311
arXiv:quant-ph/0311001

[2] A. Ambainis. Quantum search with variable times. Theory of Computing Systems, 47(3):786–807, 2010. Earlier: STACS'08, arXiv:quant-ph/0609188.
https://doi.org/10.1007/s00224-009-9219-1
arXiv:quant-ph/0609188

[3] A. Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Proc. of 29th STACS, volume 14 of LIPIcs, pages 636–647. Dagstuhl, 2012. arXiv:1010.4458.
https://doi.org/10.4230/LIPIcs.STACS.2012.636
arXiv:1010.4458

[4] 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–922, 2016. arXiv:1507.03126.
https://doi.org/10.1137/1.9781611974331.ch65
arXiv:1507.03126

[5] A. Ambainis, A. M. Childs, B. W. Reichardt, R. Špalek, 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–2530, 2010. Earlier: FOCS'07.
https://doi.org/10.1137/080712167

[6] 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–7:18, 2023. arXiv:2302.06749.
https://doi.org/10.4230/LIPIcs.TQC.2023.7
arXiv:2302.06749

[7] P. Andrés-Martí nez. Unbounded loops in quantum programs: categories and weak while loops. PhD thesis, University of Edinburgh, 2022. arXiv:2212.05371.
arXiv:2212.05371

[8] M. Bartha. Quantum Turing automata. In Proc. of 8th DCM, volume 143 of EPTCS, pages 17–31, 2014. arXiv:1404.0074.
https://doi.org/10.4204/EPTCS.143.2
arXiv:1404.0074

[9] S. Beigi and L. Taghavi. Span program for non-binary functions. Quantum Information & Computation, 19(9):760––792, 2019. arXiv:1805.02714.
arXiv:1805.02714

[10] A. Belovs. Learning-graph-based quantum algorithm for $k$-distinctness. In Proc. of 53rd IEEE FOCS, pages 207–216, 2012. arXiv:1205.1534.
https://doi.org/10.1109/FOCS.2012.18
arXiv:1205.1534

[11] A. Belovs. Span programs for functions with constant-sized 1-certificates. In Proc. of 44th ACM STOC, pages 77–84, 2012. arXiv:1105.4024.
https://doi.org/10.1145/2213977.2213985
arXiv:1105.4024

[12] A. Belovs. Quantum walks and electric networks. arXiv:1302.3143, 2013.
arXiv:1302.3143

[13] A. Belovs. Applications of the Adversary Method in Quantum Query Algorithms. PhD thesis, University of Latvia, 2014. arXiv:1402.3858.
arXiv:1402.3858

[14] A. Belovs. Variations on quantum adversary. arXiv:1504.06943, 2015.
arXiv:1504.06943

[15] A. Belovs. Global phase helps in quantum search: Yet another look at the welded tree problem. arXiv:2404.19476, 2024.
arXiv:2404.19476

[16] 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–204. Springer, 2012. arXiv:1203.2603.
https://doi.org/10.1007/978-3-642-33090-2_18
arXiv:1203.2603

[17] A. Belovs and D. Yolcu. One-way ticket to Las Vegas and the quantum adversary. arXiv:2301.02003, 2023.
arXiv:2301.02003

[18] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411–1473, 1997. Earlier: STOC'93.
https://doi.org/10.1137/S0097539796300921

[19] G. Brassard, P. Høyer, 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–74, 2002. arXiv:quant-ph/0005055.
arXiv:quant-ph/0005055

[20] H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288:21–43, 2002.
https://doi.org/10.1016/S0304-3975(01)00144-X

[21] 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–68, 2003. arXiv:quant-ph/0209131.
https://doi.org/10.1145/780542.780552
arXiv:quant-ph/0209131

[22] R. Cleve. An introduction to quantum complexity theory. arXiv:quant-ph/9906111, 1999.
https://doi.org/10.1142/9789810248185_0004
arXiv:quant-ph/9906111

[23] A. Cornelissen, S. Jeffery, M. Ozols, and A. Piedrafita. Span programs and quantum time complexity. In Proc. of 45th MFCS, pages 26:1–26:14, 2020. arXiv:2005.01323.
https://doi.org/10.4230/LIPIcs.MFCS.2020.26
arXiv:2005.01323

[24] E. Farhi, J. Goldstone, and S. Gutmann. A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4:169–190, 2008. arXiv:quant-ph/0702144.
https://doi.org/10.4086/toc.2008.v004a008
arXiv:quant-ph/0702144

[25] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proc. of 28th ACM STOC, pages 212–219, 1996. arXiv:quant-ph/9605043.
https://doi.org/10.1145/237814.237866
arXiv:quant-ph/9605043

[26] S. Jeffery. Quantum subroutine composition. arXiv:2209.14146, 2022.
arXiv:2209.14146

[27] S. Jeffery. Span programs and quantum space complexity. Theory of Computing, 18(11):1–49, 2022. arXiv:1908.04232.
https://doi.org/10.4086/toc.2022.v018a011
arXiv:1908.04232

[28] S. Jeffery and S. Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1:26, 2017. arXiv:1704.00765v3.
https://doi.org/10.22331/q-2017-08-17-26
arXiv:1704.00765v3

[29] S. Jeffery and S. Zur. Multidimensional quantum walks, with application to k-distinctness. In Proc. of 55th ACM STOC, pages 1125–1130, 2023. arXiv:2208.13492.
https://doi.org/10.1145/3564246.3585158
arXiv:2208.13492

[30] T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy. Quantum query complexity of state conversion. In Proc. of 52nd IEEE FOCS, pages 344–353, 2011. arXiv:1011.3020.
https://doi.org/10.1109/FOCS.2011.75
arXiv:1011.3020

[31] 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–314. Springer, 2013. ECCC:2012/099.
https://doi.org/10.1007/978-3-642-39206-1_59

[32] 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–329. Springer, 2011. ECCC:2010/192.
https://doi.org/10.1007/978-3-642-22006-7_27

[33] 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–551, 2009. arXiv:0904.2759.
https://doi.org/10.1109/FOCS.2009.55
arXiv:0904.2759

[34] B. W. Reichardt. Reflections for quantum query algorithms. In Proc. of 22nd ACM-SIAM SODA, pages 560–569, 2011. arXiv:1005.1601.
https://doi.org/10.1137/1.9781611973082.44
arXiv:1005.1601

[35] B. W. Reichardt. Span-program-based quantum algorithm for evaluating unbalanced formulas. In Proc. of 6th TQC, volume 6745 of LNCS, pages 73–103. Springer, 2014. arXiv:0907.1622.
https://doi.org/10.1007/978-3-642-54429-3_6
arXiv:0907.1622

[36] B. W. Reichardt and R. Špalek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8:291–319, 2012. Earlier: STOC'08, arXiv:0710.2630.
https://doi.org/10.4086/toc.2012.v008a013
arXiv:0710.2630

[37] M. Saks and A. Wigderson. Probabilistic Boolean decision trees and the complexity of evaluating game trees. In Proc. of 27th IEEE FOCS, pages 29–38, 1986.
https://doi.org/10.1109/SFCS.1986.44

[38] M. Santha. On the Monte Carlo boolean decision tree complexity of read-once formulae. Random Structures and Algorithms, 6(1):75–87, 1995.
https://doi.org/10.1002/rsa.3240060108

[39] M. Santha. Quantum walk based search algorithms. In Proc. of 5th TAMC, volume 4978 of LNCS, pages 31–46. Springer, 2008. arXiv:0808.0059.
https://doi.org/10.1007/978-3-540-79228-4_3
arXiv:0808.0059

[40] M. Snir. Lower bounds for probabilistic linear decision trees. Theoretical Computer Science, 38:69–82, 1985.
https://doi.org/10.1016/0304-3975(85)90210-5

[41] M. Szegedy. Quantum speed-up of Markov chain based algorithms. In Proc. of 45th IEEE FOCS, pages 32–41, 2004.
https://doi.org/10.1109/FOCS.2004.53

[42] 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–265, 2012. arXiv:1101.0796.
https://doi.org/10.1145/2090236.2090258
arXiv:1101.0796

Cited by

[1] Aleksandrs Belovs and Ansis Rosmanis, "Tight Quantum Lower Bound for Approximate Counting with Quantum States", computational complexity 35 1, 2 (2026).

[2] Aleksandrs Belovs and Stacey Jeffery, "Space-Efficient Quantum Error Reduction without log Factors", Quantum 10, 2039 (2026).

[3] Lorenzo Laneve, "An adversary bound for quantum signal processing", Quantum 10, 2025 (2026).

[4] Stacey Jeffery and Freek Witteveen, "Quantum-Merlin-Arthur Problems Have Perfect Completeness with an Infinite Counter", Physical Review Letters 136 18, 180601 (2026).

[5] Kiran Siripuri, Shashank Thota, and Prasanna Mandala, 2026 6th International Conference on Inventive Computation and Information Technologies (ICICIT) 508 (2026) ISBN:979-8-3315-5011-0.

[6] Lorenzo Laneve and Stefan Wolf, "On multivariate polynomials achievable with quantum signal processing", Quantum 9, 1641 (2025).

[7] Stacey Jeffery and Freek Witteveen, "${\sf QMA}={\sf QMA}_1$ with an infinite counter", arXiv:2506.15551, (2025).

[8] Aleksandrs Belovs and Ansis Rosmanis, "Tight Quantum Lower Bound for Approximate Counting with Quantum States", arXiv:2002.06879, (2020).

[9] Stacey Jeffery, "Quantum Subroutine Composition", arXiv:2209.14146, (2022).

[10] Aleksandrs Belovs, "Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem", arXiv:2404.19476, (2024).

[11] Jevgēnijs Vihrovs, "Quantum Search on Computation Trees", arXiv:2505.22405, (2025).

[12] Stacey Jeffery and Galina Pass, "Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer", arXiv:2401.08355, (2024).

[13] Stacey Jeffery, "Composing Quantum Algorithms", arXiv:2502.09240, (2025).

[14] Stacey Jeffery and Galina Pass, "A Quantum Time-Space Tradeoff for Directed $st$-Connectivity", arXiv:2510.08403, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 12:52:39) and SAO/NASA ADS (last updated successfully 2026-08-09 12:52:41). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.