Some Notes on Parallel Quantum Computation

Cristopher Moore and Martin Nilsson

Working Papers from Santa Fe Institute

Abstract: 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 we note the Quantum Fourier Transform can be parallelized to linear depth, we exhibit a simple quantum circuit related to it that we believe cannot be parallelized to less than linear depth, and therefore might be used to prove that QNC

Keywords: Quantum computation; parallel computation; Quantum Fourier Transform (search for similar items in EconPapers)
Date: 1998-04
References: View references in EconPapers 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-04-033

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 ().