arXiv:quant-ph/9801038
Another Way to Perform the Quantum Fourier Transform in Linear Parallel Time
Cristopher Moore
Abstract
. We exhibit a quantum circuit that performs the Quantum Fourier Transform on n qubits in O(n) depth. Thus, a parallel quantum computer can carry out the QFT in linear time. Griffiths and Niu have already shown this, so this paper is little more than an exercise in quantum circuit design; but perhaps it illustrates a worthwhile idea. We also speculate as to whether the QFT might be in the class QNC 1 of problems solvable in logarithmic parallel time. Shor's factoring algorithm [6] suggests that quantum computers can do things in polynomial time that classical computers cannot. However, since decoherence due to storage errors is a function of time, we should also ask to what extent we can parallelize quantum algorithms; if we can do many quantum operations at once, rather than serially, we can solve larger problems before our computer decoheres. Consider a quantum circuit operating on a set of qubits, containing onequbit gates (2 \\Theta 2 unitary matrices) and the two-qubit controlled...