Showing quant-phShow all
2 papers · 1 filter
quant-ph2002
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-ph2000
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…