Realization of a scalable coherent quantum Fourier transform*

The exponential speed-up in some quantum algorithms is a direct result of parallel function-evaluation paths that interfere through a quantum Fourier transform (QFT)[1]. We report the implementation of a fully coherent QFT on five trapped $Yb^+$ atomic qubits using sequences of fundamental quantum logic gates[2]. These modular gates can be used to program arbitrary sequences nearly independent of system size and distance between qubits. We use this capability to first perform a Deutsch-Jozsa algorithm where several instances of three-qubit balanced and constant functions are implemented and then examined using single qubit QFTs. Secondly, we apply a fully coherent five-qubit QFT as a part of a quantum phase estimation protocol. Here, the QFT operates on a five-qubit superposition state with a particular phase modulation of its coefficients and directly produces the corresponding phase to five-bit precision. Finally, we examine the performance of the QFT in the period finding problem in the context of Shor's factorization algorithm. [1] R. Cleve et al. Proc. R. Soc. Lond. A, 454, 339-354(1998). [2] S. Debnath et al., In preparation.