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

Question

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.

Answer 1

I'm not sure how you've heard about the quantum fourier transform without also seeing the circuit for it, but the wikipedia article on quantum fourier transform includes a simple quantum fourier transform circuit with polynomial gate count:

The title of your question suggests you're looking for a constant depth circuit, but I'm not aware of any constant depth circuit for the QFT. There are log depth circuits, though.