1
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

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:

enter image description here

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.

$\endgroup$
2
  • $\begingroup$ Oh, that makes a lot of sense now. $\endgroup$
    – wavosa
    Feb 26 at 18:57
  • $\begingroup$ Høyer and Špalek proved that we can approximate the QFT in constant depth with polynomially small error by using unbounded fanout gates. $\endgroup$ Feb 27 at 4:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.