CWI (The Netherlands) and ULB (Belgium)
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Expansion testing aims to decide whether an $n$-node graph has expansion at least $Phi$, or is far from any such graph. We propose a quantum expansion tester with complexity $widetilde{O}(n^{1/3}Phi^{-1})$. This accelerates the $widetilde{O}(n^{1/2}Phi^{-2})$ classical tester by Goldreich and Ron [Algorithmica ’02] [12], and combines the $widetilde{O}(n^{1/3}Phi^{-2})$ and $widetilde{O}(n^{1/2}Phi^{-1})$ quantum speedups by Ambainis, Childs and Liu [RANDOM ’11] and Apers and Sarlette [QIC ’19] [8], respectively. The latter approach builds on a quantum fast-forwarding scheme, which we improve upon by initially growing a seed set in the graph. To grow this seed set we use a so-called evolving set process from the graph clustering literature, which allows to grow an appropriately local seed set.
► BibTeX data
► References
[1] Reid Andersen, Fan R.K. Chung, and Kevin Lang. Local graph partitioning using PageRank vectors. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), pages 475–486. IEEE, 2006. 10.1109/FOCS.2006.44.
https://doi.org/10.1109/FOCS.2006.44
[2] Andris Ambainis, Andrew M. Childs, and Yi-Kai Liu. Quantum property testing for bounded-degree graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 365–376. Springer, 2011. 10.1007/978-3-642-22935-0_31.
https://doi.org/10.1007/978-3-642-22935-0_31
[3] Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis. Quadratic speedup for finding marked vertices by quantum walks. In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC), pages 412–424. ACM, 2020. 10.1145/3357713.3384252.
https://doi.org/10.1145/3357713.3384252
[4] Reid Andersen, Shayan Oveis Gharan, Yuval Peres, and Luca Trevisan. Almost optimal local graph clustering using evolving sets. Journal of the ACM, 63(2):15, 2016. 10.1145/2856030.
https://doi.org/10.1145/2856030
[5] Andris Ambainis. Quantum walk algorithm for element distinctness. 11SIAM Journal on Computing SIAM J. Comp., 37(1):210–239, 2007. 10.1137/S0097539705447311.
https://doi.org/10.1137/S0097539705447311
[6] Reid Andersen and Yuval Peres. Finding sparse cuts locally using evolving sets. In Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), pages 235–244. ACM, 2009. 10.1145/1536414.1536449.
https://doi.org/10.1145/1536414.1536449
[7] Simon Apers. Quantum walk sampling by growing seed sets. In Proceedings of the 27th European Symposium on Algorithms (ESA), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:12. Springer, 2019. 10.4230/LIPIcs.ESA.2019.9.
https://doi.org/10.4230/LIPIcs.ESA.2019.9
[8] Simon Apers and Alain Sarlette. Quantum fast-forwarding Markov chains and property testing. Quantum Information and Computation, 19(3&4):181–213, 2019.
https://dl.acm.org/doi/10.5555/3370245.3370246
[9] Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres. Testing graph clusterability: Algorithms and lower bounds. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2018. 10.1109/FOCS.2018.00054.
https://doi.org/10.1109/FOCS.2018.00054
[10] Artur Czumaj, Pan Peng, and Christian Sohler. Testing cluster structure of graphs. In Proceedings of the 47th ACM Symposium on Theory of Computing (STOC), pages 723–732. ACM, 2015. 10.1145/2746539.2746618.
https://doi.org/10.1145/2746539.2746618
[11] Artur Czumaj and Christian Sohler. Testing expansion in bounded-degree graphs. Combinatorics, Probability and Computing, 19(5-6):693–709, 2010. 10.1017/S096354831000012X.
https://doi.org/10.1017/S096354831000012X
[12] Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302–343, 2002. 10.1007/s00453-001-0078-7.
https://doi.org/10.1007/s00453-001-0078-7
[13] Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 68–75. Springer, 2011. 10.1007/978-3-642-22670-0_9.
https://doi.org/10.1007/978-3-642-22670-0_9
[14] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439–561, 2006. 10.1090/S0273-0979-06-01126-8.
https://doi.org/10.1090/S0273-0979-06-01126-8
[15] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), pages 49:1–49:21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. 10.4230/LIPIcs.ITCS.2017.49.
https://doi.org/10.4230/LIPIcs.ITCS.2017.49
[16] Satyen Kale and Comandur Seshadhri. An expansion tester for bounded degree graphs. SIAM Journal on Computing, 40(3):709–720, 2011. 10.1137/100802980.
https://doi.org/10.1137/100802980
[17] David A Levin, Yuval Peres, and Elizabeth L Wilmer. Markov chains and mixing times. American Mathematical Society, 2017. 10.1090/mbk/058.
https://doi.org/10.1090/mbk/058
[18] Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787–832, 1999. 10.1145/331524.331526.
https://doi.org/10.1145/331524.331526
[19] Anand Louis, Prasad Raghavendra, and Santosh Vempala. The complexity of approximating vertex expansion. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 360–369. IEEE, 2013. 10.1109/FOCS.2013.46.
https://doi.org/10.1109/FOCS.2013.46
[20] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. Theory of Computing Library Graduate Surveys, (7):1–81, 2016. 10.4086/toc.gs.2016.007.
https://doi.org/10.4086/toc.gs.2016.007
[21] Ben Morris and Yuval Peres. Evolving sets, mixing and heat kernel bounds. Probability Theory and Related Fields, 133(2):245–266, 2005. 10.1007/s00440-005-0434-7.
https://doi.org/10.1007/s00440-005-0434-7
[22] Asaf Nachmias and Asaf Shapira. Testing the expansion of a graph. Information and Computation, 208(4):309, 2010. 10.1016/j.ic.2009.09.002.
https://doi.org/10.1016/j.ic.2009.09.002
[23] Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. Approximating the exponential, the Lanczos method and an $widetilde{O}(m)$-time spectral algorithm for balanced separator. In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), pages 1141–1160. ACM, 2012. 10.1145/2213977.2214080.
https://doi.org/10.1145/2213977.2214080
[24] Daniel A. Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on Computing, 42(1):1–26, 2013. 10.1137/080744888.
https://doi.org/10.1137/080744888
[25] John Watrous. Quantum simulations of classical random walks and undirected graph connectivity. Journal of Computer and System Sciences, 62(2):376–391, 2001. 10.1006/jcss.2000.1732.
https://doi.org/10.1006/jcss.2000.1732
Cited by
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-09-16-323/
