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 of diagonal gates can be parallelized to logarithmic depth, while circuits composed of both cannot. Finally, while...

In this paper we investigate error-thresholds on dynamics fitness-landscapes. We show that there exists both a lower and an upper threshold, representing limits to the copying fidelity of simple replicators. The lower bound can be expressed as a correction term to the error-threshold present on...

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 parallelized to logarithmic depth, including circuits for encoding and decoding standard quantum error-correcting codes, or...

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 is P-complete, so that explicit simulation of the system is almost certainly necessary. We also show that the...