The universality of the quantum Fourier transform in forming the basis of quantum computing algorithms Academic Article uri icon


  • The quantum Fourier transform (QFT) is a powerful tool in quantum computing. The main ingredients of QFT are formed by the Walsh-Hadamard transform H and phase shifts P (·), both of which are 2 × 2 unitary matrices as operators on the two-dimensional 1-qubit space. In this paper, we show that H and P(·) suffice to generate the unitary group U(2) and, consequently, through controlled-U operations and their concatenations, the entire unitary group U (2n) on n qubits can be generated. Since any quantum computing algorithm in an n-qubit quantum computer is based on operations by matrices in U(2n), in this sense we have the universality of the QFT. © 2002 Elsevier Science (USA). All rights reserved.

author list (cited authors)

  • Bowden, C. M., Chen, G., Diao, Z., & Klappenecker, A.

citation count

  • 4

publication date

  • October 2002