The quantum Fourier transform on a linear nearest neighbor architecture (pp383-391)
          Yasuhiro Takahashi, Noboru Kunihiro, and Kazuo Ohta
          doi: https://doi.org/10.26421/QIC7.4-7
Abstracts: 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.
Key words: quantum circuits, quantum Fourier transforms, Shor’s factoring algorithm, linear nearest neighbor architectures