Fenner, S.; Green, F.; Homer, S.; Zhang, Y.
(Boston University Computer Science Department, 2004-01-12)
We 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 ...