Parallel Quantum Computation and Quantum Codes

Abstract

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 itnor a simpler "staircase" circuit can be parallelized to less than this.