3 citations · 3 across the 2 of their papers we have counts for
4 papers
Bounds on the Power of Constant-Depth Quantum Circuits
Stephen Fenner, Frederic Green, Steven Homer +1
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) polynomi…
Quantum Lower Bounds for Fanout
Maosen Fang, Stephen Fenner, Frederic Green +2
We prove several new lower bounds for constant depth quantum circuits. The main result is that parity (and hence fanout) requires log depth circuits, when the circuits are composed…
On the Complexity of Quantum ACC
F. Green, S. Homer, C. Pollett
For any , let $\MOD_q$ be a quantum gate that determines if the number of 1's in the input is divisible by . We show that for any , $\MOD_q$ is equivalent to $\M…
Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy
Stephen Fenner, Frederic Green, Steven Homer +1
It is shown that determining whether a quantum computation has a non-zero probability of accepting is at least as hard as the polynomial time hierarchy. This hardness result also a…