On the Complexity of Quantum ACC

F. Green, S. Homer, C. Pollett

For any $q>1$, let $\MOD_q$ be a quantum gate that determines if the number of 1's in the input is divisible by $q$. We show that for any $q,t>1$, $\MOD_q$ is equivalent to $\M…