Document Open Access Logo

Improved Quantum Query Upper Bounds Based on Classical Decision Trees

Authors Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.15.pdf
  • Filesize: 0.76 MB
  • 22 pages

Document Identifiers

Author Details

Arjan Cornelissen
  • Institute for Logic, Language, and Computation, University of Amsterdam, The Netherlands
  • QuSoft, Amsterdam, The Netherlands
Nikhil S. Mande
  • QuSoft, Amsterdam, The Netherlands
  • CWI, Amsterdam, The Netherlands
Subhasree Patro
  • QuSoft, Amsterdam, The Netherlands
  • CWI Amsterdam, The Netherlands
  • University of Amsterdam, The Netherlands

Funding

  • Mande, Nikhil S.: Supported by the Dutch Research Council (NWO/OCW), as part of the Quantum Software Consortium programme (project number 024.003.037), and through QuantERA ERA-NET Cofund project QuantAlgo (project number 680-91-034, ended in December 2021).
  • Patro, Subhasree: Mainly supported by the Robert Bosch Stiftung, also additionally supported by NWO Gravitation grants NETWORKS and QSC, and through QuantERA ERA-NET Cofund project QuantAlgo (project number 680-91-034, ended in December 2021).

Acknowledgements

We thank Ronald de Wolf for useful comments.

Cite As Get BibTex

Arjan Cornelissen, Nikhil S. Mande, and Subhasree Patro. Improved Quantum Query Upper Bounds Based on Classical Decision Trees. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.15

Abstract

We consider the following question in query complexity: Given a classical query algorithm in the form of a decision tree, when does there exist a quantum query algorithm with a speed-up (i.e., that makes fewer queries) 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 the number of queries. In particular, our results give a bounded-error quantum query algorithm of cost O(√s) to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size s. This recovers an O(√n) algorithm for the Search problem, for example.
Lin and Lin [Theory of Computing'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor. Their upper bounds are 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 [Information and Computation'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 measure studied in classical complexity theory. We also show a polynomial separation between rank and its natural randomized analog 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 edges of the tree. 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 strictly 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 in their construction could yield better upper bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Oracles and decision trees
  • Theory of computation → Quantum complexity theory
Keywords
  • Quantum Query Complexity
  • Decision Trees
  • Decision Tree Rank

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

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. URL: 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 Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 903-922. SIAM, 2016. URL: 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. URL: https://doi.org/10.1007/978-3-319-29817-7_4.
  4. Salman Beigi and Leila Taghavi. Span program for non-binary functions. Quantum Information and Computation, 19(9&10):760-792, 2019. URL: https://doi.org/10.26421/QIC19.9-10-2.
  5. Salman Beigi and Leila Taghavi. Quantum speedup based on classical decision trees. Quantum, 4:241, 2020. URL: https://doi.org/10.22331/q-2020-03-02-241.
  6. Salman Beigi, Leila Taghavi, and Artin Tajdini. Time and query optimal quantum algorithms based on decision trees. CoRR, abs/2105.08309, 2021. URL: http://arxiv.org/abs/2105.08309.
  7. 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. URL: https://doi.org/10.1109/FOCS.2012.18.
  8. 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. URL: https://doi.org/10.1007/978-3-030-19311-9_4.
  9. 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. URL: https://doi.org/10.1007/978-3-642-33090-2_18.
  10. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21-43, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00144-X.
  11. 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. URL: https://doi.org/10.26421/QIC18.1-2-2.
  12. Arjan Cornelissen, Nikhil S. Mande, and Subhasree Patro. Improved quantum query upper bounds based on classical decision trees, 2022. URL: https://doi.org/10.48550/ARXIV.2203.02968.
  13. 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. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2021.15.
  14. Andrzej Ehrenfeucht and David Haussler. Learning decision trees from random examples. Information and Computation, 82(3):231-246, 1989. URL: https://doi.org/10.1016/0890-5401(89)90001-1.
  15. 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. URL: https://doi.org/10.1137/16M1059369.
  16. 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. URL: https://doi.org/10.1145/237814.237866.
  17. 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. URL: https://doi.org/10.1145/1250790.1250867.
  18. 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. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.49.
  19. Stacey Jeffery and Shelby Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1:26, 2017. Google Scholar
  20. 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. URL: https://doi.org/10.1109/SCT.1993.336536.
  21. 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. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.482.
  22. 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. URL: https://doi.org/10.1109/FOCS.2011.75.
  23. 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. URL: https://doi.org/10.4086/toc.2016.v012a018.
  24. 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. URL: https://doi.org/10.1137/17M1124115.
  25. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press, 2016. URL: https://www.cambridge.org/de/academic/subjects/physics/quantum-physics-quantum-information-and-quantum-computation/quantum-computation-and-quantum-information-10th-anniversary-edition?format=HB.
  26. Noam Nisan. CREW prams and decision trees. SIAM Journal on Computing, 20(6):999-1007, 1991. Earlier version in STOC'89. URL: https://doi.org/10.1137/0220062.
  27. 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: http://dl.acm.org/citation.cfm?id=338219.338244.
  28. Ben Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 544-551, 2009. Google Scholar
  29. 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. URL: https://doi.org/10.1137/1.9781611973082.44.
  30. 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. URL: https://doi.org/10.4086/toc.2012.v008a013.
  31. 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. URL: https://doi.org/10.1109/SFCS.1986.44.
  32. Leila Taghavi. Simplified quantum algorithm for the oracle identification problem. CoRR, abs/2109.03902, 2021. URL: http://arxiv.org/abs/2109.03902.
  33. Ronald de Wolf. Quantum computing: Lecture notes. CoRR, abs/1907.09415, 2019. URL: http://arxiv.org/abs/1907.09415.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact