Quick summary: Except a special class of quantum states where quantum Fourier transform can exponentially speedup, in general it is not faster than classical Fourier transform.
where $y_k \; \left( k = 0, 1, \ldots, 2^n-1\right)$ are components of the output vectors $y$. Eq. (\ref{classicalFT}) implies that for each transformation of a component, it requires $2^n$ multiplications and $2^n - 1$ additions. Therefore, if Eq. (\ref{classicalFT}) is used directly, the number of required computational steps to perform DFT as a function of $n$ satisfies
In this section, I will show how a fast Fourier transform (FFT) reduces the computational resources to $\Theta \left( n 2^n\right)$. Note that so far, no published FFT has achieved fewer than $\Theta\left( n 2^n\right)$ so we might say that Fourier transform is regarded as exponential complexity for classical computer.
A FFT algorimth can be induced by representing the indices $j$ and $k$ in Eq. (\ref{classicalFT}) in binary form
According to the above equation, transforming one component requires $3n$ operations so transforming all components totally needs $3n \cdot 2^n$ ones. Therefore, the FFT algorithm reduces the computational resources to $\Theta\left( n2^n\right)$.
Quantum Fourier transform
This section will explain why quantum Fourier transform (QFT) only requires a polynomial resources of$\Theta\left( n^2\right)$.
As for a $2^n$-dimensional Hilbert space, the basis of $\left\{ \ket{0}, \ket{1} \ldots ,\ket{2^n-1} \right\}$ is transformed in the same fashion with FFT
The QFT circuit realizing such transformation is depicted in Figure 1. Total number of Hadamards and controlled-rotation operators are $n + \left( n-1\right) + \cdots + 1 = n \left( n+1\right)/2$. At the end of the circuit, we need $n/2$ SWAP gates realized by $3n/2$ CNOTs, to reverse the order of output qubits. Hence, the circuit of realizing QFT one basis vector in total requires $n^2/2 + 2n$ operators.
Figure 1: Quantum Fourier transform circuit
The reason that QFT requires substantially less resources is quantum parallelism. Given an input state, the circuit acts to each of the component of the superposition simultaneously and hence, perform QFT to the input state at once. Therefore, to QFT an arbitrary $n$-qubit state, total number of quantum gates remains $n^2/2 + 2n$, which is $\Theta\left( n^2\right)$ for large $n$.
On the speed-up of QFT
Because the amplitudes of quantum states cannot be directly accessed, in general QFT does not speed up the computation of Fourier transform. However, for winding-monofrequency inputs, i.e.,
\[ \overrightarrow{x}=\frac{1}{2^{n/2}} \left(\underbrace{1}_{0^{\text{th}}}, e^{-2 \pi i \varphi}, \ldots,e^{-2 \pi i j\varphi},\ldots, \underbrace{e^{-2 \pi i \left( 2^n-1\right) \varphi}}_{2^n-1^{\text{th}}}\right) \quad \left( 0 \le \varphi <1\right), \]
QFT can be exponentially faster than DFT and FFT.
A compact form of QFT acting on a basis state and an arbitrary state can be respectively written as
Hence, QFT of an arbitrary state is equivalent to DFT of amplitudes $x_j$.
Even though quantum parallelism enables the simultaneous actions on amplitudes, the amplitudes are probabilistic so they cannot be directly determined by measurements. That is why QFT in general does not speed up the computation of Fourier transform. However, there exist special inputs that the transformed vectors' amplitudes are deterministic, and thus they can be used to demonstrate exponential speedup of QFT. The aforementioned state results from the fact that Fourier transform of a winding-monofrequency data returns to a Kronecker delta.
To illustrate the point we consider an example as follows. Suppose we have an input vector $\overrightarrow{x}$ of which components have winding frequency of $\varphi$ $\left( 0 \le \varphi <1\right)$
\[ \begin{aligned} \overrightarrow{x}&=\frac{1}{2^{n/2}} \left(\underbrace{1}_{0^{\text{th}}}, e^{-2 \pi i \varphi}, \ldots,e^{-2 \pi i j\varphi},\ldots, \underbrace{e^{-2 \pi i \left( 2^n-1\right) \varphi}}_{2^n-1^{\text{th}}}\right) \\ &= \frac{1}{2^{n/2}} \underbrace{\begin{pmatrix} 1\\ e^{-2 \pi i \varphi 2^{n-1}} \end{pmatrix}}_{0^{\text{th}}} \otimes \begin{pmatrix} 1\\ e^{-2 \pi i \varphi 2^{n-2}} \end{pmatrix} \otimes \cdots \otimes \underbrace{\begin{pmatrix} 1\\ e^{-2 \pi i \varphi 2^{0}} \end{pmatrix}}_{n-1^{\text{th}}} \end{aligned} \label{classicalinput} \]
We expect the Fourier transform of $\overrightarrow{x}$ to be a Kronecker delta
\[ \begin{aligned} y_k &= \frac{1}{2^{n/2}} \sum_{j=0}^{2^n-1} x_j \exp\left( 2 \pi i \frac{j k }{2^n}\right) = \frac{1}{2^{n}} \sum_{j=0}^{2^n-1} \exp\left( -2 \pi i \varphi j + 2 \pi i \frac{j k }{2^n}\right)\\ &= \frac{1}{2^{n}} \sum_{j=0}^{2^n-1} \exp\left[ 2 \pi i j \left( \frac{k}{2^n} - \varphi\right) \right] = \delta \left( \frac{k}{2^n} - \varphi\right), \end{aligned} \]
where $k = 2^n \varphi$ indicates the the position of component having nontrivial value. Here we have an additional constraint for $\varphi$ such that $k = 2^n \varphi \in \mathbb{N}$. The transformed vector is written as
For later convenience, suppose $k$ is represented by $t$-bit in the binary form, $k=k_0 k_1 \ldots k_{ n-1}$, the transformed vector can be furthermore written in tensor-product formalism as follows
where $ \begin{pmatrix} 1\\ 0 \end{pmatrix}$ and $ \begin{pmatrix} 0\\ 1 \end{pmatrix} $ respectively replace $0$ and $1$.
As analyzed above, it respectively requires DFT and FFT $\Theta\left( 2^{2n}\right)$ and $\Theta\left( n2^n\right)$ operations to perform the transformation.
Equivalently, QFT of such monofrequency must have the same result. In quantum formalism, the input state described in Eq. (\ref{classicalinput}) is written as
\[ \ket{j} = \frac{1}{2^{n/2}}\underbrace{\left( \ket{0} + e^{-2\pi i \varphi 2^{n-1}}\right)}_{0^{\text{th}}} \otimes \left( \ket{0} + e^{-2\pi i \varphi 2^{n-2}}\right) \otimes \cdots \otimes \underbrace{\left( \ket{0} + e^{-2\pi i \varphi 2^0}\right)}_{n-1^{\text{th}}}. \]
QFT of $\ket{j}$ gives an output in the same fashion with Eq. (\ref{tensorproduct})
Performing $n$ measurements at the end of QFT circuit, we deterministically obtain the output state and could determine the value of $\varphi$. Take $n$ measurements into account, for large $n$ QFT in total still requires $\Theta\left( n^2\right)$ operations, and thus is exponentially faster than DFT and FFT.
Useful reference: Chapter 5, Quantum computation and quantum information (Nielsen MA, Chuang I.)
Exponential speed-up of quantum Fourier transform
Quick summary: Except a special class of quantum states where quantum Fourier transform can exponentially speedup, in general it is not faster than classical Fourier transform.
Definition of classical Fourier transform
\( \def\ket#1{{ \left| #1 \right> }} \) \( \def\bracket#1{{ \left( #1 \right) }} \)
A discrete Fourier transform (DFT) of a $2^n$-length vector $x= \left( x_0, x_1, \ldots, x_{2^n-1}\right)$ is defined as follows
$$ y_k \equiv \frac{1}{2^{n/2}} \sum_{j=0}^{2^n -1} x_j \exp \left( \frac{2 \pi i}{2^n} k j\right), \label{classicalFT} $$
where $y_k \; \left( k = 0, 1, \ldots, 2^n-1\right)$ are components of the output vectors $y$. Eq. (\ref{classicalFT}) implies that for each transformation of a component, it requires $2^n$ multiplications and $2^n - 1$ additions. Therefore, if Eq. (\ref{classicalFT}) is used directly, the number of required computational steps to perform DFT as a function of $n$ satisfies
\[ \left( 2^{n+1} -1 \right)2^n \in \Theta \left( 2^{2n}\right) \; \text{for} \; n\rightarrow \infty. \]
Fast Fourier transform
In this section, I will show how a fast Fourier transform (FFT) reduces the computational resources to $\Theta \left( n 2^n\right)$. Note that so far, no published FFT has achieved fewer than $\Theta\left( n 2^n\right)$ so we might say that Fourier transform is regarded as exponential complexity for classical computer.
A FFT algorimth can be induced by representing the indices $j$ and $k$ in Eq. (\ref{classicalFT}) in binary form
\[ \begin{aligned} j &= j_1 j_2 \ldots j_n = j_1 2^0 + j_2 2^1 + \cdots + j_n 2^{n-1} ,\\ \frac{k}{2^n} &= 0.k_1 k_2 \ldots k_n = \frac{k_1}{2} + \frac{k_2}{2^4} + \cdots + \frac{k_n}{2^n}. \end{aligned} \]
Eq. (\ref{classicalFT}) is straightforwardly written as
\[ \begin{aligned} y_{k_1 k_2 \ldots k_n} &= \frac{1}{2^{n/2}} \sum_{j_1= 0}^{1} \sum_{j_2= 0}^{1} \cdots \sum_{j_n= 0}^{1} x_{j_1 j_2 \ldots j_n} \exp \left( 2 \pi i \; j_1 j_2 \ldots j_n \; 0.k_1 k_2 \ldots k_n\right) \\
&= \frac{1}{2^{n/2}} \sum_{j_1= 0}^{1} x_{j_1} \exp \left( 2 \pi i j_1 2^0 0.k_1 k_2 \ldots k_n \right) \sum_{j_2= 0}^{1} x_{j_2} \exp \left( 2 \pi i j_2 2^1 0.k_1k_2 \ldots k_n \right)\\
& \cdots \sum_{j_n= 0}^{1} x_{j_n} \exp \left( 2 \pi i j_n 2^{n-1} 0.k_1k_2 \ldots k_n \right) \end{aligned} \]
We then collect every $j_i$ to the binary fraction $0.k_1 k_2 \ldots k_n$ and further simplify the exponential function as follows
\[ \begin{aligned} &\exp \left( 2 \pi i \; j_i 2^{i-1} \; 0.k_1 k_2 \ldots k_n\right) \\
&= \exp \left[ 2\pi i j_i \left( \underbrace{ k_1 2^{i-2} + \cdots + k_{i-1} 2^0}_{\in \mathbb{N} \text{ so } \exp\left( \ldots\right) =1} + k_i 2^{-1} + \cdots k_n2^{-n-i-1} \right)\right]\\
& = \exp \left( 2 \pi i \; j_i \; 0.k_i k_{i+1} \ldots k_n\right), \end{aligned} \]
This method helps to rewrite the transformation as
\[ \begin{aligned}
y_{k_1 k_2 \ldots k_n} &= \frac{1}{2^{n/2}} \sum_{j_1= 0}^{1} x_{j_1} \exp \left( 2 \pi i j_1 0.k_1 k_2 \ldots k_n \right) \sum_{j_2= 0}^{1} x_{j_2} \exp \left( 2 \pi i j_2 0.k_2 \ldots k_n \right)\\
& \cdots \sum_{j_n= 0}^{1} x_{j_n} \exp \left( 2 \pi i j_n 0.k_n \right)\\
&= \frac{1}{2^{n/2}} \left( x_0 + e^{2 \pi i 0.k_1 k_2 \ldots k_n }x_1\right) \left( x_0 + e^{2 \pi i 0.k_2 k_3 \ldots k_n }x_1\right) \cdots \left( x_0 + e^{2 \pi i 0.k_n }x_1\right) . \label{FFT}\\
\end{aligned} \]
According to the above equation, transforming one component requires $3n$ operations so transforming all components totally needs $3n \cdot 2^n$ ones. Therefore, the FFT algorithm reduces the computational resources to $\Theta\left( n2^n\right)$.
Quantum Fourier transform
This section will explain why quantum Fourier transform (QFT) only requires a polynomial resources of $\Theta\left( n^2\right)$.
As for a $2^n$-dimensional Hilbert space, the basis of $\left\{ \ket{0}, \ket{1} \ldots ,\ket{2^n-1} \right\}$ is transformed in the same fashion with FFT
\[ \begin{aligned}
\ket{k_1 k_2 \ldots k_n} = \frac{1}{2^{n/2}} \left( \ket{0} + e^{2 \pi i 0.k_1 k_2 \ldots k_n }\ket{1}\right) &\left( \ket{0} + e^{2 \pi i 0.k_2 k_3 \ldots k_n }\ket{1}\right) \\
&\cdots \left( \ket{0} + e^{2 \pi i 0.k_n }\ket{1}\right).
\end{aligned} \label{QFT1} \]
The QFT circuit realizing such transformation is depicted in Figure 1. Total number of Hadamards and controlled-rotation operators are $n + \left( n-1\right) + \cdots + 1 = n \left( n+1\right)/2$. At the end of the circuit, we need $n/2$ SWAP gates realized by $3n/2$ CNOTs, to reverse the order of output qubits. Hence, the circuit of realizing QFT one basis vector in total requires $n^2/2 + 2n$ operators.
The reason that QFT requires substantially less resources is quantum parallelism. Given an input state, the circuit acts to each of the component of the superposition simultaneously and hence, perform QFT to the input state at once. Therefore, to QFT an arbitrary $n$-qubit state, total number of quantum gates remains $n^2/2 + 2n$, which is $\Theta\left( n^2\right)$ for large $n$.
On the speed-up of QFT
Because the amplitudes of quantum states cannot be directly accessed, in general QFT does not speed up the computation of Fourier transform. However, for winding-monofrequency inputs, i.e.,
\[ \overrightarrow{x}=\frac{1}{2^{n/2}} \left(\underbrace{1}_{0^{\text{th}}}, e^{-2 \pi i \varphi}, \ldots,e^{-2 \pi i j\varphi},\ldots, \underbrace{e^{-2 \pi i \left( 2^n-1\right) \varphi}}_{2^n-1^{\text{th}}}\right) \quad \left( 0 \le \varphi <1\right), \]
QFT can be exponentially faster than DFT and FFT.
A compact form of QFT acting on a basis state and an arbitrary state can be respectively written as
\[ \begin{aligned}
QFT \ket{j} &= \frac{1}{2^{n/2}} \sum_{k=0}^{2^n-1} \exp\left( \frac{2 \pi i}{2^n}k j\right) \ket{k},\\
QFT \sum_{j=0}^{2^n-1} x_j \ket{j} &= \sum_{j=0}^{2^n-1} \underbrace{\left[ \frac{1}{2^{n/2}} \sum_{k=0}^{2^n-1} x_j \exp\left( \frac{2 \pi i}{2^n}k j\right) \right]}_{\text{DFT of } x_j} \ket{k}. \end{aligned} \]
Hence, QFT of an arbitrary state is equivalent to DFT of amplitudes $x_j$.
Even though quantum parallelism enables the simultaneous actions on amplitudes, the amplitudes are probabilistic so they cannot be directly determined by measurements. That is why QFT in general does not speed up the computation of Fourier transform. However, there exist special inputs that the transformed vectors' amplitudes are deterministic, and thus they can be used to demonstrate exponential speedup of QFT. The aforementioned state results from the fact that Fourier transform of a winding-monofrequency data returns to a Kronecker delta.
To illustrate the point we consider an example as follows. Suppose we have an input vector $\overrightarrow{x}$ of which components have winding frequency of $\varphi$ $\left( 0 \le \varphi <1\right)$
\[ \begin{aligned}
\overrightarrow{x}&=\frac{1}{2^{n/2}} \left(\underbrace{1}_{0^{\text{th}}}, e^{-2 \pi i \varphi}, \ldots,e^{-2 \pi i j\varphi},\ldots, \underbrace{e^{-2 \pi i \left( 2^n-1\right) \varphi}}_{2^n-1^{\text{th}}}\right) \\
&= \frac{1}{2^{n/2}}
\underbrace{\begin{pmatrix}
1\\
e^{-2 \pi i \varphi 2^{n-1}}
\end{pmatrix}}_{0^{\text{th}}}
\otimes
\begin{pmatrix}
1\\
e^{-2 \pi i \varphi 2^{n-2}}
\end{pmatrix}
\otimes \cdots
\otimes
\underbrace{\begin{pmatrix}
1\\
e^{-2 \pi i \varphi 2^{0}}
\end{pmatrix}}_{n-1^{\text{th}}}
\end{aligned}
\label{classicalinput} \]
We expect the Fourier transform of $\overrightarrow{x}$ to be a Kronecker delta
\[ \begin{aligned}
y_k &= \frac{1}{2^{n/2}} \sum_{j=0}^{2^n-1} x_j \exp\left( 2 \pi i \frac{j k }{2^n}\right) = \frac{1}{2^{n}} \sum_{j=0}^{2^n-1} \exp\left( -2 \pi i \varphi j + 2 \pi i \frac{j k }{2^n}\right)\\
&= \frac{1}{2^{n}} \sum_{j=0}^{2^n-1} \exp\left[ 2 \pi i j \left( \frac{k}{2^n} - \varphi\right) \right] = \delta \left( \frac{k}{2^n} - \varphi\right),
\end{aligned} \]
where $k = 2^n \varphi$ indicates the the position of component having nontrivial value. Here we have an additional constraint for $\varphi$ such that $k = 2^n \varphi \in \mathbb{N}$. The transformed vector is written as
\[ \overrightarrow{y} = \left( 0,0,\ldots,\underbrace{1}_{\text{kth}},\ldots,0\right).
\label{classicaloutput} \]
For later convenience, suppose $k$ is represented by $t$-bit in the binary form, $k=k_0 k_1 \ldots k_{ n-1}$, the transformed vector can be furthermore written in tensor-product formalism as follows
\[ \overrightarrow{y} = k_0 \otimes k_1 \otimes \cdots \otimes k_{ n-1},
\label{tensorproduct} \]
where $ \begin{pmatrix} 1\\ 0 \end{pmatrix}$ and $ \begin{pmatrix} 0\\ 1 \end{pmatrix} $ respectively replace $0$ and $1$.
As analyzed above, it respectively requires DFT and FFT $\Theta\left( 2^{2n}\right)$ and $\Theta\left( n2^n\right)$ operations to perform the transformation.
Equivalently, QFT of such monofrequency must have the same result. In quantum formalism, the input state described in Eq. (\ref{classicalinput}) is written as
\[ \ket{j} = \frac{1}{2^{n/2}}\underbrace{\left( \ket{0} + e^{-2\pi i \varphi 2^{n-1}}\right)}_{0^{\text{th}}} \otimes \left( \ket{0} + e^{-2\pi i \varphi 2^{n-2}}\right) \otimes \cdots \otimes \underbrace{\left( \ket{0} + e^{-2\pi i \varphi 2^0}\right)}_{n-1^{\text{th}}}. \]
QFT of $\ket{j}$ gives an output in the same fashion with Eq. (\ref{tensorproduct})
\[ \ket{k} = \ket{k_0} \otimes \ket{k_1} \otimes \cdots \otimes \ket{k_{n-1}}. \]
Performing $n$ measurements at the end of QFT circuit, we deterministically obtain the output state and could determine the value of $\varphi$. Take $n$ measurements into account, for large $n$ QFT in total still requires $\Theta\left( n^2\right)$ operations, and thus is exponentially faster than DFT and FFT.
Useful reference: Chapter 5, Quantum computation and quantum information (Nielsen MA, Chuang I.)
'Physics Corner' 카테고리의 다른 글