Parallel Quantum Computation and Quantum Codes

Cristopher Moore and Martin Nilsson

Working Papers from Santa Fe Institute

Abstract: 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 more generally any circuit consisting of controlled-not gates, controlled pi-shifts, and Hadamard gates. Finally, while we note the Quantum Fourier Transform can be parallelized to linear depth, we conjecture that an even simpler `staircase' circuit cannot be parallelized to less than linear depth, and might be used to prove that QNC is less than QP.

This supersedes our earlier preprint, ``Notes on Parallel Quantum Computation.''

Keywords: Quantum computation; error-correcting codes; Clifford Group; parallel computation (search for similar items in EconPapers)
Date: 1998-08
References: View complete reference list from CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:98-08-070

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().