TY - CONF T1 - Symmetries, graph properties, and quantum speedups T2 - Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649–660 (2020) Y1 - 2020 A1 - Shalev Ben-David A1 - Andrew M. Childs A1 - Andras Gilyen A1 - William Kretschmer A1 - Supartha Podder A1 - Daochen Wang AB -

Aaronson and Ambainis (2009) and Chailloux (2018) 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 super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial 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 (2010) and Montanaro and de Wolf (2013).

JA - Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649–660 (2020) UR - https://arxiv.org/abs/2006.12760 U5 - https://doi.org/10.1109/FOCS46700.2020.00066 ER -