Title  Symmetries, graph properties, and quantum speedups 
Publication Type  Conference Paper 
Year of Publication  2020 
Authors  BenDavid, S, Childs, AM, Gilyen, A, Kretschmer, W, Podder, S, Wang, D 
Conference Name  Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), pp. 649–660 (2020) 
Date Published  6/23/2020 
Abstract  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 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 boundeddegree 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).

URL  https://arxiv.org/abs/2006.12760 
DOI  10.1109/FOCS46700.2020.00066 