7 citations · 20 across the 5 of their papers we have counts for
6 papers
Fixed-Parameter Extrapolation and Aperiodic Order
Stephen Fenner, Frederic Green, Steven Homer
Fix any . We say that a set is - if, whenever and are in , the point is also in . If is also (topolo…
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…
Counting, Fanout, and the Complexity of Quantum ACC
Frederic Green, Steven Homer, Cristopher Moore +1
We propose definitions of $\QAC^0$, the quantum analog of the classical class $\AC^0$ of constant-depth circuits with AND and OR gates of arbitrary fan-in, and $\QACC[q]$, the anal…
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…