I try to understand how to concretely use the Quantum Fourier Transform so as to retrieve the frequency amplitudes $g_{0},\dots, g_{N-1}$ out of the discrete time series $f_{0},\dots, f_{N-1}$ ($f_k\in\mathbb{R}$), just like it would be done in a classical way.

If I understand well, the first task is to build a quantum state which encodes the time series as its amplitude coefficients : $$ \lvert \psi \rangle = \sum_{k=0}^{N-1}f_{k}\lvert k \rangle $$

Then, the Quantum Circuit for the QFT performs the unitary : $$ U\lvert \psi \rangle = \sum_{k=0}^{N-1}g_{k}\lvert k \rangle $$

The question is that if I give you a time series, whatever, what is the procedure to build a corresponding $\lvert \psi \rangle$ ?

Also, how do you retrieve in the end of the circuit by measurements the $g_{k}$ ?

Surprisingly, although there are many tutorials on the QFT, I found no pieces of information about these questions but this post, which seems to tackle the first question.

In the sequel, I try to address as far as I can the first question.

Obviously, for $\lvert \psi \rangle$ to be a valid state, the time series must be normalized : $$ \sum_{k=0}^{N-1} (f_k)^2 = 1 $$ which can be done easily by rescaling all $f_k$ coefficients.

For the sake of simplicity assume $N=4$, then : $$ \lvert \psi \rangle = f_{0}\lvert 0 \rangle + f_{1}\lvert 1 \rangle +f_{2}\lvert 2 \rangle +f_{3}\lvert 3 \rangle = f_{0}\lvert 00 \rangle + f_{1}\lvert 01 \rangle +f_{2}\lvert 10 \rangle +f_{3}\lvert 11 \rangle $$

So we need two qubits, $q_0$ and $q_1$, the state of each qubit is : $$ \lvert q_{0} \rangle = \cos(\frac{\theta_{0}}{2})\lvert 0 \rangle + e^{i\varphi_{0}} \sin(\frac{\theta_{0}}{2})\lvert 1 \rangle,\quad \lvert q_{1} \rangle = \cos(\frac{\theta_{1}}{2})\lvert 0 \rangle + e^{i\varphi_{1}} \sin(\frac{\theta_{1}}{2})\lvert 1 \rangle $$

The joint state of both qubit is then : \begin{equation} \begin{split} \lvert q_{0}q_{1} \rangle = &\cos(\frac{\theta_{0}}{2}) \cos(\frac{\theta_{1}}{2})\lvert 00 \rangle + \cos(\frac{\theta_{0}}{2})\sin(\frac{\theta_{1}}{2})\lvert 01 \rangle\\ &+ \sin(\frac{\theta_{0}}{2})\cos(\frac{\theta_{1}}{2})\lvert 10 \rangle+ \sin(\frac{\theta_{0}}{2})\sin(\frac{\theta_{1}}{2})\lvert 11 \rangle \end{split} \end{equation} where I assumed $\varphi_{0}= \varphi_{1} = 0$

Encoding the time series $f_{0},\dots, f_{N-1}$ into both qubits would consist in finding $\theta_0$ and $\theta_1$ such that : \begin{equation} \begin{split} f_{0} = \cos(\frac{\theta_{0}}{2}) \cos(\frac{\theta_{1}}{2})&,\quad f_{1} = \cos(\frac{\theta_{0}}{2})\sin(\frac{\theta_{1}}{2}),\quad \\ f_{2} = \sin(\frac{\theta_{0}}{2})\cos(\frac{\theta_{1}}{2})&,\quad f_{3} = \sin(\frac{\theta_{0}}{2})\sin(\frac{\theta_{1}}{2}) \end{split} \end{equation} It would then be enough to rotate each qubit around $X$ axis with respective angle $\theta_0$ and $\theta_1$, starting from $\lvert 0 \rangle$.

However, previous formula assume $\lvert \psi \rangle$ to be factorized (not entangled), which imposes a drastic condition on the time series : $$ f_0f_3 = f_1 f_2 $$ it appears that this procedure is very limited. Is there a more general procedure ?



Your Answer

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