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