Symmetries, graph properties, and quantum speedupsS

Ben-David, Shalev and Childs, Andrew M. and Gilyén, András Pál and Kretschmer, William and Podder, Supartha and Wang, Daochen (2024) Symmetries, graph properties, and quantum speedupsS. SIAM JOURNAL ON COMPUTING, 53 (6). FOCS20-368. ISSN 0097-5397

Preview

Text 23m1573975.pdf - Published Version Download (720kB) | Preview

Abstract

Aaronson and Ambainis [Theory Comput., 10 (2014), pp. 133-166] and Chailloux [Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2018, pp. 19:1-19:7] showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent superpolynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow superpolynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs-where graph symmetry is manifested differently-we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu [Lecture Notes in Comput. Sci. 6845, Springer, 2011, pp. 365-376] and Montanaro and de Wolf [Theory Comput., 7 (2016)].

Actions (login required)

Edit Item