SIAM Journal on Computing 31(3) (2002) 799-815.
We study the class QNC of efficient parallel quantum circuits, the quantum analog of 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 more generally any circuit consisting of controlled-not gates, controlled pi-shifts, and Hadamard gates. Finally, while we note the exact quantum Fourier transform can be parallelized to linear depth, we conjecture that neither it nor a simpler ``staircase'' circuit can be parallelized to less than this.
This supersedes our earlier preprint, ``Notes on Parallel Quantum Computation.''
Click here to download a shorter (and older) version