  Quantum computers can sometimes exponentially outperform classical ones, but
only for problems with sufficient structure. While it is well known that query
problems with full permutation symmetry can have at most polynomial quantum
speedup -- even for partial functions -- it is unclear how far this condition
must be relaxed to enable exponential speedup. In particular, it is natural to
ask whether exponential speedup is possible for (partial) graph properties, in
which the input describes a graph and the output can only depend on its
isomorphism class. We show that the answer to this question depends strongly on
the input model. In the adjacency matrix model, we prove that the bounded-error
randomized query complexity $R$ of any graph property $\mathcal{P}$ has
$R(\mathcal{P}) = O(Q(\mathcal{P})^{6})$, where $Q$ is the bounded-error
quantum query complexity. This negatively resolves an open question of
Montanaro and de Wolf in the adjacency matrix model. More generally, we prove
$R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})$ for any $l$-uniform hypergraph
property $\mathcal{P}$ in the adjacency matrix model. In direct contrast, in
the adjacency list model for bounded-degree graphs, we exhibit a promise
problem that shows an exponential separation between the randomized and quantum
query complexities.
