1
$\begingroup$

The standard DFT:

$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2 \pi kn/N} \tag{1}$$

takes approximately $N^2$ complex summations and multiplications (or $\mathcal{O}(N^2)$). The faster version of FT known as FFT is extermely faster than the classical DFT and requires approximately $Nlog_2N$ complex summations and multiplications (or $\mathcal{O}(Nlog_2N)$) through butterfly structures and less calculations of twiddle factors. For QFT I just know that it operates with the phases in Fourier basis, so the result of such transform is the rotation of each qubit for the angle, which is factor of 2 more or less realtive to the neghboring qubit:

$$QFT_N|x\rangle = \frac{1}{\sqrt(N)} \left(|0\rangle+e^{\frac{2\pi i}{2}x}|1\rangle\right)\otimes \left(|0\rangle+e^{\frac{2\pi i}{2^2}x}|1\rangle\right)\otimes...\otimes\left(|0\rangle+e^{\frac{2\pi i}{2^{n-1}}x}|1\rangle\right)\otimes\left(|0\rangle+e^{\frac{2\pi i}{2^{n}}x}|1\rangle\right)\tag{2}$$

In this case for me it is not evident how to calculate the complexity of this algorithm. How can I estimate the complexity of QFT in terms of complex summations and multiplications?

$\endgroup$
5
  • $\begingroup$ it is not clear which "algorithm" you're considering in the case of the QFT. The QFT is not "an algorithm" in the classical sense. There's no point in using it to compute the DFT of a classical vector. And it's also not clear what this even means: using the standard decomposition of the QFT in terms of elementary gates and "evolving" the input vector through it as if it was a state? That probably wouldn't be very efficient, but it's also not the point of the QFT $\endgroup$
    – glS
    May 2, 2023 at 13:03
  • $\begingroup$ @glS, I saw some topics on QFT in the framework of quantum algorithms (or as a part of them) and unintentionally call the QFT as "algorithm", sorry for that( I just would like to know, if there is an advantage of using QFT over FFT, I think it could compared by the speed of computation or complexity. $\endgroup$
    – Curious
    May 2, 2023 at 14:46
  • $\begingroup$ well, that's the thing. They're not really comparable, in that they do different things. The QFT acts on quantum states and gives you quantum states. The FFT is a technique to efficiently apply the DFT to a classical vector. These are different tasks $\endgroup$
    – glS
    May 3, 2023 at 10:58
  • $\begingroup$ @glS, ok, but it doesn't mean that we can't estimate QFT complexity $\endgroup$
    – Curious
    May 4, 2023 at 7:40
  • 1
    $\begingroup$ it means that you have to be careful what "QFT complexity" means, because it likely doesn't mean the same as what you think saying "FFT complexity", thus them not being comparable. To be clear, there are connections between QFT and FFT, see eg quantumcomputing.stackexchange.com/questions/1999. But these are not about one being "faster" than the other $\endgroup$
    – glS
    May 4, 2023 at 8:55

1 Answer 1

2
$\begingroup$

You're doing the Fourier transform over a basis of size $N$. If we assume that $N=2^n$, then you're using $n=\log_2(N)$ qubits in the quantum algorithm.

You can look up what the circuit looks like for the QFT. The key ingredient is that there's a controlled-phase gate (of some phase) between every pair of qubits. Overall, there are $O(n^2)$ gates. This is your complexity.

$\endgroup$
4
  • $\begingroup$ thank you!) could you please clarify a bit, where does it come from, that the complexity is the square of qubits number? $\endgroup$
    – Curious
    May 2, 2023 at 13:16
  • $\begingroup$ For example, for 4 qubits I need 6 CPHASE gates, 4 H-gates and 2 SWAPs, but for $O(n^2)$ the overall number of gates is 16... $\endgroup$
    – Curious
    May 2, 2023 at 13:32
  • 1
    $\begingroup$ The $O$ notation means "of the order of", telling you roughly how the scaling goes, and not the precise number. If memory serves, the precise number of gates you need in $\binom{n}{2}+n$. I wouldn't bother counting the swaps. But precise counting is pretty pointless because it depends on what gate set you're counting relative to (how do you make a cphase gate of a specific phase?), it's just that the leading term is $~n^2$, which is the same no matter the precise details of the counting of gates. $\endgroup$
    – DaftWullie
    May 2, 2023 at 15:26
  • 1
    $\begingroup$ ok, if we can consider (roughly) for each qubit pairwise (which is $n-1$) $CPHASE$-gate plus $H$-gate it becomes clear for me) $\endgroup$
    – Curious
    May 2, 2023 at 16:09

Your Answer

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

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