Performing the Quantum Fourier Transform in Linear Parallel Time

Cristopher Moore

Working Papers from Santa Fe Institute

Abstract: We exhibit a quantum circuit that performs the Quantum Fourier Transform on $n$ qubits in $ (n)$ depth. Thus, a parallel quantum computer can carry out the QFT in linear time. We conjecture that this can, in fact, be reduced to $ ({\rm log} n)$ depth, which would place the QFT in the class {\bf QNC} of problems solvable in logarithmic parallel time.

Keywords: Quantum computation; parallel computation; Fourier transform; factoring (search for similar items in EconPapers)
Date: 1998-01
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-01-013

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