Optimal Separations Between Randomized and Quantum Query Complexity under Permutation Symmetry
It is proved that every such function over an arbitrary finite alphabet $A$ satisfies R_\varepsilon(f)=O(Q_\varepsilon(f)^2)$, and bounds for graph and hypergraph properties are established, which are tight for permutation-invariant functions and nearly tight for graph and hypergraph properties.