Journal
SIAM JOURNAL ON COMPUTING
Volume 31, Issue 3, Pages 799-815Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S0097539799355053
Keywords
quantum circuits; parallel computation; quantum complexity classes; quantum error-correcting codes; group theory
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available