Graph properties and circular functions: how low can quantum query complexity go?

In decision tree models, considerable attention has been paid on the effect of symmetry on computational complexity. That is, for a permutation group Γ, how low can the complexity be for any Boolean function invariant under Γ? In this paper, we investigate this question for quantum decision trees for graph properties, directed graph properties, and circular functions. In particular, we prove that the n-vertex Scorpion graph property has quantum query complexity Θ^˜ (n¹2/), which implies that the minimum quantum complexity for graph properties is strictly less than that for monotone graph properties (known to be Ω(n²3/)). A directed graph property, SINK, is also shown to have the Θ^˜(n¹2/) quantum query complexity. Furthermore, we give an N-ary circular function which has the quantum query complexity Θ ^˜(N¹4/). Finally, we show that for any permutation group Γ, as long as Γ is transitive, the quantum query complexity of any function invariant to Γ is at least Ω(N¹4/), which implies that our examples are (almost) the best ones in the sense of pinning down the complexity for the corresponding permutation group.