Improved Quantum Query Upper Bounds Based on Classical Decision Trees

Arjan Cornelissen; Nikhil S. Mande; Subhasree Patro

doi:10.22331/q-2025-06-23-1777

Improved Quantum Query Upper Bounds Based on Classical Decision Trees

Arjan Cornelissen¹, Nikhil S. Mande², and Subhasree Patro³

¹Simons Institute for the Theory of Computing, University of California, Berkeley, United States of America
²University of Liverpool, United Kingdom
³Eindhoven University of Technology, Netherlands

Published:	2025-06-23, volume 9, page 1777
Editor:	Aleksandrs Belovs
Eprint:	arXiv:2203.02968v3
Doi:	https://doi.org/10.22331/q-2025-06-23-1777
Citation:	Quantum 9, 1777 (2025).

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

Abstract

Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up. In particular, we obtain a bounded-error quantum query algorithm of cost $O(\sqrt{s})$ to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size $s$.
Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor, and gave upper bounds in terms of a quantity which we call the "guessing complexity" of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Inf. Comp.'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any complexity-theoretic measure. We also show a polynomial separation between rank and randomized rank for the complete binary AND-OR tree.
Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to its edges. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are asymptotically stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes could yield better upper bounds.

► BibTeX data

@article{Cornelissen2025improvedquantum,
  doi = {10.22331/q-2025-06-23-1777},
  url = {https://doi.org/10.22331/q-2025-06-23-1777},
  title = {Improved {Q}uantum {Q}uery {U}pper {B}ounds {B}ased on {C}lassical {D}ecision {T}rees},
  author = {Cornelissen, Arjan and Mande, Nikhil S. and Patro, Subhasree},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1777},
  month = jun,
  year = {2025}
}

► References

[1] Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in query complexity based on pointer functions. Journal of the ACM, 64(5):32:1–32:24, 2017. Earlier version in STOC'16. doi:10.1145/3106234.
https://doi.org/10.1145/3106234

[2] Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf. Efficient quantum algorithms for (gapped) group testing and junta testing. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 903–922. SIAM, 2016. doi:10.1137/1.9781611974331.ch65.
https://doi.org/10.1137/1.9781611974331.ch65

[3] Agnis Arins. Span-program-based quantum algorithms for graph bipartiteness and connectivity. In Mathematical and Engineering Methods in Computer Science - 10th International Doctoral Workshop, MEMICS, Selected Papers, volume 9548 of Lecture Notes in Computer Science, pages 35–41. Springer, 2015. doi:10.1007/978-3-319-29817-7_4.
https://doi.org/10.1007/978-3-319-29817-7_4

[4] Aleksandrs Belovs. Learning-graph-based quantum algorithm for k-distinctness. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 207–216. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.18.
https://doi.org/10.1109/FOCS.2012.18

[5] Aleksandrs Belovs. Quantum dual adversary for hidden subgroups and beyond. In Proceedings of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC), volume 11493 of Lecture Notes in Computer Science, pages 30–36. Springer, 2019. doi:10.1007/978-3-030-19311-9_4.
https://doi.org/10.1007/978-3-030-19311-9_4

[6] Aleksandrs Belovs and Ben W. Reichardt. Span programs and quantum algorithms for st-connectivity and claw detection. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), volume 7501 of Lecture Notes in Computer Science, pages 193–204. Springer, 2012. doi:10.1007/978-3-642-33090-2_18.
https://doi.org/10.1007/978-3-642-33090-2_18

[7] Salman Beigi and Leila Taghavi. Span program for non-binary functions. Quantum Information and Computation, 19(9&10):760–792, 2019. doi:10.26421/QIC19.9-10-2.
https://doi.org/10.26421/QIC19.9-10-2

[8] Salman Beigi and Leila Taghavi. Quantum speedup based on classical decision trees. Quantum, 4:241, 2020. doi:10.22331/q-2020-03-02-241.
https://doi.org/10.22331/q-2020-03-02-241

[9] Salman Beigi, Leila Taghavi, and Artin Tajdini. Time-and query-optimal quantum algorithms based on decision trees. ACM Transactions on Quantum Computing, 3(4):1–31, 2022. doi:10.1145/3519269.
https://doi.org/10.1145/3519269

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

[11] Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, and Swagato Sanyal. Randomized versus deterministic decision tree size. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 867–880. ACM, 2023. doi:10.1145/3564246.3585199.
https://doi.org/10.1145/3564246.3585199

[12] Chris Cade, Ashley Montanaro, and Aleksandrs Belovs. Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. Quantum Information and Computation, 18(1&2):18–50, 2018. doi:10.26421/QIC18.1-2-2.
https://doi.org/10.26421/QIC18.1-2-2

[13] Arjan Cornelissen, Nikhil S. Mande, and Subhasree Patro. Improved quantum query upper bounds based on classical decision trees. In Anuj Dawar and Venkatesan Guruswami, editors, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, December 18-20, 2022, IIT Madras, Chennai, India, volume 250 of LIcs, pages 15:1–15:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.FSTTCS.2022.15.
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.15

[14] Arjan Cornelissen. Quantum algorithms through graph composition, 2025. doi:10.48550/arXiv.2504.02115.
https://doi.org/10.48550/arXiv.2504.02115

[15] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. CoRR, quant-ph/9607014, 1996. URL: https://doi.org/10.48550/arXiv.quant-ph/9607014.
https://doi.org/10.48550/arXiv.quant-ph/9607014
arXiv:quant-ph/9607014

[16] Yogesh Dahiya and Meena Mahajan. On (simple) decision tree rank. In Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 213 of LIPIcs, pages 15:1–15:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.FSTTCS.2021.15.
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.15

[17] Andrzej Ehrenfeucht and David Haussler. Learning decision trees from random examples. Information and Computation, 82(3):231–246, 1989. doi:10.1016/0890-5401(89)90001-1.
https://doi.org/10.1016/0890-5401(89)90001-1

[18] Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM Journal on Computing, 47(6):2435–2450, 2018. Earlier version in FOCS'15. doi:10.1137/16M1059369.
https://doi.org/10.1137/16M1059369

[19] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC), pages 212–219. ACM, 1996. doi:10.1145/237814.237866.
https://doi.org/10.1145/237814.237866

[20] Peter Høyer, Troy Lee, and Robert Špalek. Negative weights make adversaries stronger. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 526–535. ACM, 2007. doi:10.1145/1250790.1250867.
https://doi.org/10.1145/1250790.1250867

[21] Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum algorithms for connectivity and related problems. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA), volume 112 of LIPIcs, pages 49:1–49:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ESA.2018.49.
https://doi.org/10.4230/LIPIcs.ESA.2018.49

[22] Stacey Jeffery and Shelby Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1:26, 2017. doi:10.22331/q-2017-08-17-26.
https://doi.org/10.22331/q-2017-08-17-26

[23] Robin Kothari. An optimal quantum algorithm for the oracle identification problem. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), volume 25 of LIPIcs, pages 482–493. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. doi:10.4230/LIPIcs.STACS.2014.482.
https://doi.org/10.4230/LIPIcs.STACS.2014.482

[24] Mauricio Karchmer and Avi Wigderson. On span programs. In Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 102–111. IEEE Computer Society, 1993. doi:10.1109/SCT.1993.336536.
https://doi.org/10.1109/SCT.1993.336536

[25] Cedric Yen-Yu Lin and Han-Hsuan Lin. Upper bounds on quantum query complexity inspired by the Elitzur–Vaidman bomb tester. Theory of Computing, 12(1):1–35, 2016. doi:10.4086/toc.2016.v012a018.
https://doi.org/10.4086/toc.2016.v012a018

[26] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy. Quantum query complexity of state conversion. In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS, pages 344–353. IEEE Computer Society, 2011. doi:10.1109/FOCS.2011.75.
https://doi.org/10.1109/FOCS.2011.75

[27] Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, and Swagato Sanyal. Separation between deterministic and randomized query complexity. SIAM Journal on Computing, 47(4):1644–1666, 2018. Earlier versions in FSTTCS'15 and FSTTCS'16. doi:10.1137/17M1124115.
https://doi.org/10.1137/17M1124115

[28] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press, 2016. doi:10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[29] Noam Nisan. CREW prams and decision trees. SIAM Journal on Computing, 20(6):999–1007, 1991. Earlier version in STOC'89. doi:10.1137/0220062.
https://doi.org/10.1137/0220062

[30] Pavel Pudlák and Russell Impagliazzo. A lower bound for DLL algorithms for k-sat (preliminary version). In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 128–136. ACM/SIAM, 2000. URL: https://dl.acm.org/doi/10.5555/338219.338244.
https://dl.acm.org/doi/10.5555/338219.338244

[31] Ben Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 544–551. IEEE Computer Society, 2009. doi:10.1109/FOCS.2009.55.
https://doi.org/10.1109/FOCS.2009.55

[32] Ben Reichardt. Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 560–569. SIAM, 2011. doi:10.1137/1.9781611973082.44.
https://doi.org/10.1137/1.9781611973082.44

[33] Ben Reichardt and Robert Špalek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8(1):291–319, 2012. Earlier version in STOC'08. doi:10.4086/toc.2012.v008a013.
https://doi.org/10.4086/toc.2012.v008a013

[34] Michael E. Saks and Avi Wigderson. Probabilistic boolean decision trees and the complexity of evaluating game trees. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (FOCS), pages 29–38. IEEE Computer Society, 1986. doi:10.1109/SFCS.1986.44.
https://doi.org/10.1109/SFCS.1986.44

[35] Leila Taghavi. Simplified quantum algorithm for the oracle identification problem. Quantum Mach. Intell., 4(2):1–7, 2022. doi:10.1007/s42484-022-00080-2.
https://doi.org/10.1007/s42484-022-00080-2

[36] Ronald de Wolf. Quantum computing: Lecture notes. CoRR, abs/1907.09415, 2019. arXiv:1907.09415, doi:10.48550/arXiv.1907.09415.
https://doi.org/10.48550/arXiv.1907.09415
arXiv:1907.09415

Cited by

[1] Manqoba Q. Hlatshwayo, Manav Babel, Dalila Islas-Sanchez, and Konstantinos Georgopoulos, "A Technical Review of Quantum Computing Use Cases for Finance and Economics", Quantum Reports 8 1, 26 (2026).

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

[3] Yogesh Dahiya and Meena Mahajan, "On (Simple) Decision Tree Rank", arXiv:2209.12877, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 08:57:24) and SAO/NASA ADS (last updated successfully 2026-07-14 19:32:46). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-07-15 08:57:24: Cannot retrieve data from ADS due to rate limitations.

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.