The quantum Fourier transform on a linear nearest neighbor architecture

Abstract

We show how to construct an efficient quantum circuit for computing a good approximation of the quantum Fourier transform on a linear nearest neighbor architecture. The constructed circuit uses no ancillary qubits and its depth and size are $O(n)$ and $O(n\log n)$, respectively, where $n$ is the length of the input. The circuit is useful for decreasing the size of Fowler et al.'s quantum circuit for Shor's factoring algorithm on a linear nearest neighbor architecture.