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.
Abstract
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}^nto[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.
https://doi.org/10.1109/CCC.2011.24
arXiv:1012.2112
[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.
https://doi.org/10.1007/978-3-319-29817-7_4
arXiv:1510.07825v1
[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.
https://doi.org/10.1007/BFb0055105
arXiv:9805082
[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.
https://doi.org/10.1007/978-3-642-33090-2_18
arXiv:1203.2603
[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.
https://doi.org/10.26421/QIC19.9-10
arXiv:1805.02714
[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.
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.
https://doi.org/10.4230/LIPIcs.STACS.2011.661
arXiv:1011.1443
[8] Chris Cade, Ashley Montanaro, and Aleksandrs Belovs. Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness. oct. arXiv:1610.00581.
arXiv:1610.00581
[9] Christoph Dürr and Peter Høyer. A Quantum Algorithm for Finding the Minimum. arXiv:9607014.
arXiv:quant-ph/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.
https://doi.org/10.1137/050644719
arXiv:0401091
[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.
https://doi.org/10.1145/237814.237866
arXiv:9605043
[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.
https://doi.org/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.
https://doi.org/10.1145/1250790.1250867
arXiv:0611054
[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.
https://doi.org/10.4230/LIPIcs.ICALP.2016.12
arXiv:1507.00432
[15] Arthur B. Kahn. Topological sorting of large networks. Communications of the ACM, 5:558–562, 1962. doi:10.1145/368996.369025.
https://doi.org/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.
https://doi.org/10.4086/toc.2016.v012a018
arXiv:1410.0932
https://theoryofcomputing.org/articles/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.
https://doi.org/10.1109/FOCS.2011.75
arXiv:1011.3020
[18] Troy Lee, Rajat Mittal, Ben W Reichardt, and Robert Špalek. An adversary for algorithms. arXiv:1011.3020.
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.
https://doi.org/10.1109/FOCS.2009.55
arXiv:0904.2759
[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.
https://doi.org/10.4086/toc.2012.v008a013
arXiv:0710.2630
http://www.theoryofcomputing.org/articles/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.
https://doi.org/10.1109/SFCS.2002.1181975
arXiv:0112086
[22] Robert Endre Tarjan. Edge-disjoint spanning trees and depth-first search. Acta Informatica, 6(2):171–185, 1976. doi:10.1007/BF00268499.
https://doi.org/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.
https://doi.org/10.1016/j.tcs.2005.01.019
arXiv:0311060
Cited by
Could not fetch Crossref cited-by data during last attempt 2020-03-02 16:26:18: Could not fetch cited-by data for 10.22331/q-2020-03-02-241 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2020-03-02 16:26:19).
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.
Source: https://quantum-journal.org/papers/q-2020-03-02-241/
