64 citations · 77 across the 3 of their papers we have counts for
3 papers
cond-mat1998★ 64 cited
The Computational Complexity of Sandpiles
Cristopher Moore, Martin Nilsson
Given an initial distribution of sand in an Abelian sandpile, what final state does it relax to after all possible avalanches have taken place? In d >= 3, we show that this problem…
quant-ph1998★ 12 cited
Parallel Quantum Computation and Quantum Codes
Cristopher Moore, Martin Nilsson
We propose a definition of QNC, the quantum analog of the efficient parallel class NC. We exhibit several useful gadgets and prove that various classes of circuits can be paralleli…
quant-ph1998★ 1 cited
Some Notes on Parallel Quantum Computation
Cristopher Moore, Martin Nilsson
We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or…