9 citations · 25 across the 6 of their papers we have counts for
Showing quant-phShow all
3 papers · 1 filter
quant-ph2002★ 5 cited
Quantum and Stochastic Branching Programs of Bounded Width
Farid Ablayev, Cristopher Moore, Chris Pollett
In this paper we show that one qubit polynomial time computations are at least as powerful as $\NC^1$ circuits. More precisely, we define syntactic models for quantum and stochasti…
quant-ph2001★ 4 cited
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…
quant-ph2000★ 7 cited
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…