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.