# Why is the application of a Quantum Fourier Transform constant time?

I am just curious (complexity theory wise) why the unitary matrix for the QFT (Quantum Fourier Transform) is constant time. From what I know, there is no general way to represent it as a sequence of tensor products of different matrices (for arbitrarily large cases); so how can it be implemented, in sub-polynomial time, on a quantum computer?

For a concrete perspective, imagine a world in which we have quantum computers embedded into our office computers that run the QFT. Say we would like to run it with 500 qubits; how would we compute such a 500 qubit QFT matrix in polynomial time?

I know that it follows a regular pattern when written in matrix form:

$$F = \begin{bmatrix} \omega_N^{0 \times 0} & \omega_N^{0 \times 1} & \cdots \\ \omega_N^{1 \times 0} & \omega_N^{1 \times 1} \\ \vdots & & \ddots \end{bmatrix}$$

But how is this really computed for arbitrary numbers of qubits in complexity-theory.

• – glS
Feb 27 at 8:07 