Performing the Quantum Fourier Transform in Linear Parallel Time

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.

MoreLess

Year of publication:	1998-01
Authors:	Moore, Cristopher
Institutions:	Santa Fe Institute
Subject:	Quantum computation \| parallel computation \| Fourier transform \| factoring

More details

Series:	Working Papers.
Type of publication:	Book / Working Paper
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005740013