01555nas a2200169 4500008004100000245005500041210005300096260001400149520105800163100002201221700002301243700001901266700002401285700002101309700001801330856003701348 2020 eng d00aSymmetries, graph properties, and quantum speedups0 aSymmetries graph properties and quantum speedups c6/23/20203 a

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).

1 aBen-David, Shalev1 aChilds, Andrew, M.1 aGilyen, Andras1 aKretschmer, William1 aPodder, Supartha1 aWang, Daochen uhttps://arxiv.org/abs/2006.12760