In this article, I will explain the Quantum Fourier Transform (QFT) algorithm. blueqat has a tutorial on the subject, but there is no example for n qubits, so I decided to include it. The Fast Fourier Transformation (FFT) on a normal classical computer is capable of processing on the order of $O(n2^n)$ for the length of the input data bits, but this can easily become uncomputable as the input data sequence grows. Using the Quantum Fourier Transform, however, only $O(logn)$ order is needed.

First of all, any wave can be expressed as a superposition of various frequency components. This is common to all waves, not just light and sound waves. The Fourier transform is a method of examining a wave by breaking it down into its constituent frequency components and mapping the amplitude of each component to frequency coordinates (spectral coordinates).The equation is

$F(\omega)=\int_{-\infty}^{\infty}e^{-i\omega t}f(t)dt.$

Then, \omega is the angular frequency (rad/s). In a manual calculation, the frequency components can be completely decomposed with this equation. Essentially, this should take us from negative infinity to positive infinity in the time range. However, computers are not capable of handling infinity. Therefore, in a computer, this is converted into a matrix operation to calculate only a finite time range. This is a technique called Discrete Fourier Transformation (DFT), which is represented by the following equation.

$F_j=\sum_{k=1}^{N}e^{-2i\pi jk/N}f_k$

Here, k corresponds to time, j to frequency, and N to time range (data length), respectively. In this case, the limit of frequencies that can be decomposed into frequency components is half of the length (resolution) of the data length to be prepared as a spectrum. The matrix with $e^{-2i\pi jk/N}$ as a component in this equation is the matrix of the Discrete Fourier Transform. However, it takes time on the order of $O(2^{2n})$ for the length of the data to generate this matrix and make it work. In classical computing, there is a Fast Fourier Transform algorithm (FFT) that improves on this. As mentioned above, the processing time is $O(n2^n)$ , which is currently the fastest on a classical computer. However, a faster speed-up than this has not been achieved in the classics.

In quantum computing, an algorithm has been devised to do this at high speed. This is the Quantum Fourier Transform (QFT). This algorithm is based on the fact that the calculation method and phase can be easily gated in a quantum computer, and can be calculated in the order of O(logn).

The formula is

$\mid j \rangle = \sum_{k=0}^{2^n-1}e^{-2i\pi jk/2^n-1}\mid k \rangle$

$= \sum_{k_1=0}^{1}\sum_{k_2=0}^{1}\cdots\sum_{k_n}^{1}e^{-2i\pi j(2^{n-1}k_1+2^{n-2}k_2+\cdots +k_n)/2^n}\mid k_1 k_2\cdots k_n\rangle$

using the binary representation,

$k = 0.k_1 k_2 \cdots k_{n}=\sum_{i=1}\frac{k_i}{2^i}$ .

This can be expressed as On a quantum circuit, $R_l\mid 0\rangle \rightarrow \mid 0\rangle , R_l\mid 1\rangle \rightarrow e^{-2i\pi / 2^l}\mid 1\rangle$ using an arbitrary phase gate R is represented as in Figure 1. The QFT result for the state $\mid 0001\rangle$ represented by four qubits using this is shown in Figure 2. In the Supplemental information, I have included the Fourier transform results for more states. As you can see, the narrower the width of the wave, the more high frequency components appear in the spectrum. Remembering this relationship is useful in many places. For example, if an electron is localized in coordinate space, it is widespread in wavenumber space due to Heisenberg's uncertainty relation.

Figure 1: A quantum circuit performing a quantum Fourier transform.

Figure 2: Result of the quantum Fourier transform of $\mid 0001 \rangle$ . ● represents the real part of the coefficients in each state and + represents the imaginary part.

Since the length of the input data can be easily increased by using QFT, it is expected that the demand for quantum computers will rapidly increase once error-tolerant quantum computation is introduced to the world. Not only that, but it is also the basis of error-tolerant quantum computation, as it is used in various algorithms for quantum phase estimation and other quantum algorithms for error-tolerant quantum computers. Research on error-tolerant quantum computers is about to begin, and it is very likely that they will be available to the world within two years. I encourage you to master it before then.

Here is the source.

Quantum Fourier Transform: Source by Hikaru Wakaura | blueqat