Quantum Speedup Based on Classical Decision Trees

Salman Beigi1 and Leila Taghavi2

1School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
2School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran

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


Lin and Lin [16] have recently shown how starting with a classical query algorithm (decision tree) for a function, we may find upper bounds on its quantum query complexity. More precisely, they have shown that given a decision tree for a function $f:\{0,1\}^n\to[m]$ whose input can be accessed via queries to its bits, and a $\textit{guessing algorithm}$ that predicts answers to the queries, there is a quantum query algorithm for $f$ which makes at most $O(\sqrt{GT})$ quantum queries where $T$ is the depth of the decision tree and $G$ is the maximum number of mistakes of the guessing algorithm. In this paper we give a simple proof of and generalize this result for functions $f:[\ell]^n \to [m]$ with non-binary input as well as output alphabets. Our main tool for this generalization is non-binary span program which has recently been developed for non-binary functions, and the dual adversary bound. As applications of our main result we present several quantum query upper bounds, some of which are new. In particular, we show that topological sorting of vertices of a directed graph $\mathcal G$ can be done with $O(n^{3/2})$ quantum queries in the adjacency matrix model. Also, we show that the quantum query complexity of the maximum bipartite matching is upper bounded by $O(n^{3/4}\sqrt {m + n})$ in the adjacency list model.

► BibTeX data

► References

[1] Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jérémie Roland. Symmetry-assisted adversaries for quantum state generation. In 2011 IEEE 26th Annual Conference on Computational Complexity, pages 167–177. IEEE, 2011. arXiv:1012.2112, doi:10.1109/​CCC.2011.24.

[2] Agnis Āriņš. Span-program-based quantum algorithms for graph bipartiteness and connectivity. In International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, pages 35–41. Springer, 2015. arXiv:1510.07825v1, doi:10.1007/​978-3-319-29817-7_4.

[3] Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum counting. In Kim G. Larsen, Sven Skyum, and Glynn Winskel, editors, Automata, Languages and Programming, pages 820–831, Berlin, Heidelberg. Springer Berlin Heidelberg. arXiv:9805082, doi:10.1007/​BFb0055105.

[4] Aleksandrs Belovs and Ben W Reichardt. Span programs and quantum algorithms for st-connectivity and claw detection. In Proceedings of the 20th Annual European conference on Algorithms (ESA 12), pages 193–204. Springer Berlin Heidelberg. arXiv:1203.2603, doi:10.1007/​978-3-642-33090-2_18.

[5] Salman Beigi and Leila Taghavi. Span program for non-binary functions. Quantum Information and Computation, 19(9-10):760–792, 2019. arXiv:1805.02714, doi:10.26421/​QIC19.9-10.

[6] Jill Cirasella. Classical and Quantum Algorithms for Finding Cycles. Master's thesis, University of Amsterdam, 2006. URL: http:/​/​www.illc.uva.nl/​Research/​Publications/​Reports/​MoL-2006-06.text.pdf.

[7] Andrew M. Childs and Robin Kothari. Quantum query complexity of minor-closed graph properties. SIAM Journal On Computing. arXiv:1011.1443, doi:10.4230/​LIPIcs.STACS.2011.661.

[8] Chris Cade, Ashley Montanaro, and Aleksandrs Belovs. Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness. oct. arXiv:1610.00581.

[9] Christoph Dürr and Peter Høyer. A Quantum Algorithm for Finding the Minimum. arXiv:9607014.

[10] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310–1328, 2006. arXiv:0401091, doi:10.1137/​050644719.

[11] Low K Grover. A fast quantum mechanical algorithm for database search. Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC), pages 212–219. arXiv:9605043, doi:10.1145/​237814.237866.

[12] John E Hopcroft and Richard M Karp. An $O(n^{2.5})$ algorithm for maximum matching in bipartite graphs. SIAM Journal On Computing, pages 122–125, 1970. doi:10.1137/​0202019.

[13] Peter Høyer, Troy Lee, and Robert Špalek. Negative weights make adversaries stronger. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 526–535. ACM, 2007. arXiv:0611054, doi:10.1145/​1250790.1250867.

[14] Tsuyoshi Ito and Stacey Jeffery. Approximate Span Programs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 2015. URL: http:/​/​arxiv.org/​abs/​1507.00432, arXiv:1507.00432, doi:10.4230/​LIPIcs.ICALP.2016.12.

[15] Arthur B. Kahn. Topological sorting of large networks. Communications of the ACM, 5:558–562, 1962. doi:10.1145/​368996.369025.

[16] 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–35, 2016. URL: https:/​/​theoryofcomputing.org/​articles/​v012a018/​, arXiv:1410.0932, doi:10.4086/​toc.2016.v012a018.

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

[18] Troy Lee, Rajat Mittal, Ben W Reichardt, and Robert Špalek. An adversary for algorithms. arXiv:1011.3020.

[19] Ben W Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 544–551. IEEE, 2009. arXiv:0904.2759, doi:10.1109/​FOCS.2009.55.

[20] Ben W Reichardt and Robert Špalek. Span-program-based quantum algorithm for evaluating formulas. volume 8, pages 291–319. Theory of Computing, 2012. URL: http:/​/​www.theoryofcomputing.org/​articles/​v008a013, arXiv:0710.2630, doi:10.4086/​toc.2012.v008a013.

[21] Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. In Proceedings 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 513–519, 2002. arXiv:0112086, doi:10.1109/​SFCS.2002.1181975.

[22] Robert Endre Tarjan. Edge-disjoint spanning trees and depth-first search. Acta Informatica, 6(2):171–185, 1976. doi:10.1007/​BF00268499.

[23] Shengyu Zhang. On the power of Ambainis lower bounds. Theoretical Computer Science, 339(2-3):241–256, 2005. arXiv:0311060, doi:10.1016/​j.tcs.2005.01.019.

Cited by

[1] Kamil Khadiev, Nikita Savelyev, Mansur Ziatdinov, and Denis Melnikov, "Noisy Tree Data Structures and Quantum Applications", Mathematics 11 22, 4707 (2023).

[2] Shelby Kimmel and R. Teal Witter, Lecture Notes in Computer Science 12808, 543 (2021) ISBN:978-3-030-83507-1.

[3] Leila Taghavi, "Simplified quantum algorithm for the oracle identification problem", Quantum Machine Intelligence 4 2, 19 (2022).

[4] Raoul Heese, Patricia Bickert, and Astrid Elisa Niederle, "Representation of binary classification trees with binary features by quantum circuits", Quantum 6, 676 (2022).

[5] Noel T. Anderson, Jay-U Chung, Shelby Kimmel, Da-Yeon Koh, and Xiaohan Ye, "Improved Quantum Query Complexity on Easier Inputs", Quantum 8, 1309 (2024).

[6] Kyle E. C. Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield, and Eleanor Rieffel, "Quantum-accelerated constraint programming", Quantum 5, 550 (2021).

[7] 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 (2022).

[8] Manoranjan Gandhudi, Gangadharan G.R., Alphonse P.J.A, Vasanth Velayudham, and Leeladhar Nagineni, "Causal aware parameterized quantum stochastic gradient descent for analyzing marketing advertisements and sales forecasting", Information Processing & Management 60 5, 103473 (2023).

[9] Shuai Yang, Wei Zi, Bujiao Wu, Cheng Guo, Jialin Zhang, and Xiaoming Sun, "Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 43 3, 868 (2024).

[10] Arjan Cornelissen, Stacey Jeffery, Maris Ozols, and Alvaro Piedrafita, "Span programs and quantum time complexity", arXiv:2005.01323, (2020).

[11] Noel T. Anderson, Jay-U Chung, and Shelby Kimmel, "Leveraging Unknown Structure in Quantum Query Algorithms", arXiv:2012.01276, (2020).

[12] Michael Czekanski, Shelby Kimmel, and R. Teal Witter, "Robust and Space-Efficient Dual Adversary Quantum Query Algorithms", arXiv:2306.15040, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-15 07:23:38) and SAO/NASA ADS (last updated successfully 2024-04-15 07:23:39). The list may be incomplete as not all publishers provide suitable and complete citation data.