Fenner, StephenGreen, F.Homer, S.Zhang, Y.2011-10-202011-10-202004-01-12https://hdl.handle.net/2144/1531We show that if a language is recognized within certain error bounds by constant-depth quantum circuits over a finite family of gates, then it is computable in (classical) polynomial time. In particular, our results imply EQNC^0 ⊆ P, where EQNC^0 is the constant-depth analog of the class EQP. On the other hand, we adapt and extend ideas of Terhal and DiVincenzo [?] to show that, for any family 𝓕 of quantum gates including Hadamard and CNOT gates, computing the acceptance probabilities of depth-five circuits over 𝓕 is just as hard as computing these probabilities for circuits over 𝓕. In particular, this implies that NQNC^0=NQACC=NDQP=coC₌P, where NQNC^0 is the constant-depth analog of the class NQP. This essentially refutes a conjecture of Green et al. that NQACC ⊆ TC^0 [?].en-USTechnical Report