【量子位相推定アルゴリズム②】量子フーリエ変換
今回も、量子位相推定アルゴリズムの記事の続きです。前回は、1量子ビットの量子位相推定について解説しました。
しかしこの手法では、小数$${n}$$桁位まで存在する位相に対しては、$${n}$$個の独立した量子回路を用意する必要がありました。一方で、一般的に量子位相推定アルゴリズムと呼ばれる量子アルゴリズムは、$${n}$$個の補助量子ビットを用いることで、一種類の量子回路で位相を推定することが可能となります。そしてこの量子位相推定アルゴリズムには、量子フーリエ変換と呼ばれる技術が活用されています。
今回の記事では、量子位相推定アルゴリズムにおいて重要な役割を果たす量子フーリエ変換について解説したいと思います。
量子フーリエ変換
量子フーリエ変換とは、離散フーリエ変換を量子コンピュータで実現する量子アルゴリズムです。
量子フーリエ変換の定義
さて、量子フーリエ変換の定義について確認してみましょう。量子フーリエ変換を表す演算子を$${U_{\rm QFT}}$$とすると、
$$
U_{\rm QFT}\ket{j} = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{i2\pi\frac{kj}{N}}\ket{k}
$$
となります。ここで$${\ket{j}}$$は、$${N}$$次元の基底ベクトルを表しています。当然$${n}$$量子ビットを考えている場合は$${N=2^n}$$です。さて量子フーリエ変換の定義は上式で与えられるのですが、かなり複雑ですね。そこで具体例を考えてみましょう。
具体例: 1個の量子ビットの場合
$${N=2^1=2}$$なので、基底ベクトルは、$${\ket{j}=\ket{0}, \ket{1}}$$の二つだけです。さて、これらの基底ベクトルが、量子フーリエ変換によってどのように変換されるのかを見ていきましょう。
$$
U_{\rm QFT}\ket{j} = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{i2\pi\frac{kj}{N}}\ket{k} = \frac{1}{\sqrt{2}}\sum_{k=0}^{1}e^{i2\pi\frac{kj}{2}}\ket{k}
$$
$$
= \frac{1}{\sqrt{2}}\sum_{k=0}^{1}e^{i\pi kj}\ket{k} = \frac{1}{\sqrt{2}}(e^{i\pi 0j}\ket{0}+e^{i\pi 1j}\ket{1})= \frac{1}{\sqrt{2}}(\ket{0}+e^{i\pi j}\ket{1})
$$
つまり、$${\ket{j}=\ket{0}}$$の場合は、
$$
U_{\rm QFT}\ket{0} = \frac{1}{\sqrt{2}}(\ket{0}+\ket{1})=H\ket{0}
$$
となり、$${\ket{j}=\ket{1}}$$の場合は、
$$
U_{\rm QFT}\ket{1} = \frac{1}{\sqrt{2}}(\ket{0}+e^{i\pi}\ket{1})= \frac{1}{\sqrt{2}}(\ket{0}-\ket{1})=H\ket{1}
$$
となります。つまり、量子ビットが1個の場合はアダマール変換と同等になります。
具体例: 2個の量子ビットの場合
$$
U_{\rm QFT}\ket{j} = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{i2\pi\frac{kj}{N}}\ket{k} = \frac{1}{2}\sum_{k=0}^{3}e^{i2\pi\frac{kj}{4}}\ket{k}
$$
$$
= \frac{1}{2}\sum_{k=0}^{3}e^{i\pi \frac{kj}{2}}\ket{k} = \frac{1}{2}(e^{i\pi \frac{0j}{2}}\ket{0}+e^{i\pi \frac{1j}{2}}\ket{1}+e^{i\pi \frac{2j}{2}}\ket{2}+e^{i\pi \frac{3j}{2}}\ket{3})
$$
$$
= \frac{1}{2}(\ket{0}+e^{i\pi \frac{j}{2}}\ket{1}+e^{i\pi j}\ket{2}+e^{i\pi \frac{3j}{2}}\ket{3})
$$
つまり、$${\ket{j}=\ket{0}}$$の場合は、
$$
U_{\rm QFT}\ket{0} = \frac{1}{2}(\ket{0}+\ket{1}+\ket{2}+\ket{3})
$$
$${\ket{j}=\ket{1}}$$の場合は、
$$
U_{\rm QFT}\ket{1} = \frac{1}{2}(\ket{0}+e^{i\pi \frac{1}{2}}\ket{1}+e^{i\pi }\ket{2}+e^{i\pi \frac{3}{2}}\ket{3})
$$
$$
= \frac{1}{2}(\ket{0}+i\ket{1}-\ket{2}-i\ket{3})
$$
$${\ket{j}=\ket{2}}$$の場合は、
$$
U_{\rm QFT}\ket{2} = \frac{1}{2}(\ket{0}+e^{i\pi }\ket{1}+e^{i2\pi }\ket{2}+e^{i3\pi}\ket{3})
$$
$$
= \frac{1}{2}(\ket{0}-\ket{1}+\ket{2}-\ket{3})
$$
$${\ket{j}=\ket{3}}$$の場合は、
$$
U_{\rm QFT}\ket{3} = \frac{1}{2}(\ket{0}+e^{i\pi \frac{3}{2}}\ket{1}+e^{i3\pi }\ket{2}+e^{i\pi \frac{9}{2}}\ket{3})
$$
$$
= \frac{1}{2}(\ket{0}-i\ket{1}-\ket{2}+i\ket{3})
$$
となります。上記からなんとなく基底ベクトルの情報が位相にエンコードされているような印象を受けますね。
量子フーリエ変換の原理
さて具体例を計算してイメージが少しついたところで、$${n}$$量子ビットの一般的な例について考えてみましょう。もう一度量子フーリエ変換の定義に戻ります。
$$
U_{\rm QFT}\ket{j} = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{i2\pi\frac{kj}{N}}\ket{k}
$$
量子フーリエ変換の一般的な変換を考えるために、この定義式を計算していきます。ここで少し前準備を導入します。これまでは$${N}$$という10進数での表現を扱ってきましたが、量子コンピュータで扱う、つまり量子ビットで表現するには、2進数での表現が必要となります。そこで、
$$
j = j_0*2^{n-1}+j_1*2^{n-2}+\cdots+j_{n-1}*2^{0}
$$
$$
k = k_0*2^{n-1}+k_1*2^{n-2}+\cdots+k_{n-1}*2^{0}
$$
を利用して、10進数表示から2進数表示に変換します。ただし、上式における$${j_i}$$と$${k_i}$$は、0または1に対応します。例えば、$${\ket{j=5}}$$の場合は、
$$
\ket{j=5}=\ket{1*2^{2}+0*2^{1}+1*2^{0}}
$$
となるので、
$$
\ket{j=5}=\ket{j_0}\otimes\ket{j_1}\otimes\ket{j_2}=\ket{1}\otimes\ket{0}\otimes\ket{1}
$$
と記述することができます。さて準備ができたところで実際に定義式から計算していきましょう。
$$
U_{\rm QFT}\ket{j} = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{i2\pi\frac{kj}{N}}\ket{k}=\frac{1}{\sqrt{2^n}}\sum_{k=0}^{N-1}e^{i2\pi\frac{kj}{2^n}}\ket{k}
$$
ここで、明示的に2進数表示に変換します。$${k = k_0*2^{n-1}+k_1*2^{n-2}+\cdots+k_{n-1}*2^{0}}$$を利用して、
$$
\frac{1}{\sqrt{2^n}}\sum_{k=0}^{N-1}e^{i2\pi\frac{kj}{2^n}}\ket{k}=\frac{1}{\sqrt{2^n}}\sum_{k_0=0,1}\sum_{k_1=0,1}\cdots \sum_{k_{n-1}=0,1}e^{i2\pi j(k_0*2^{n-1}+k_1*2^{n-2}+\cdots+k_{n-1}*2^{0})/{2^n}}\ket{k_0k_1\cdots k_{n-1}}
$$
$$
=\frac{1}{\sqrt{2^n}}\sum_{k_0=0,1}\sum_{k_1=0,1}\cdots \sum_{k_{n-1}=0,1}e^{i2\pi j(\frac{k_0}{2}+\frac{k_1}{2^2}+\cdots+\frac{k_{n-1}}{2^{n}})}\ket{k_0k_1\cdots k_{n-1}}
$$
$$
=\frac{1}{\sqrt{2^n}}\sum_{k_0=0,1}\sum_{k_1=0,1}\cdots \sum_{k_{n-1}=0,1}e^{i2\pi j\frac{k_0}{2}}e^{i2\pi j\frac{k_1}{2^2}}\cdots
e^{i2\pi j\frac{k_{n-1}}{2^n}}\ket{k_0k_1\cdots k_{n-1}}
$$
$$
=\frac{1}{\sqrt{2^n}}\sum_{k_0=0,1}e^{i2\pi j\frac{k_0}{2}}\ket{k_0}\otimes
\sum_{k_1=0,1}e^{i2\pi j\frac{k_1}{2^2}}\ket{k_1}\otimes
\cdots \otimes\sum_{k_{n-1}=0,1} e^{i2\pi j\frac{k_{n-1}}{2^n}}\ket{k_{n-1}}
$$
$$
=\frac{1}{\sqrt{2^n}}(\ket{0}+e^{i2\pi \frac{j}{2}}\ket{1})\otimes(\ket{0}+e^{i2\pi \frac{j}{2^2}}\ket{1})\otimes
\cdots \otimes
(\ket{0}+e^{i2\pi \frac{j}{2^n}}\ket{1})
$$
を得ます。ここで、$${j = j_0*2^{n-1}+j_1*2^{n-2}+\cdots+j_{n-1}*2^{0}}$$に対して、$${j2^{-m}}$$を計算すると、
$$
j2^{-m} = j_0j_1\cdots j_{n-1-m}.j_{n-m}\cdots j_{n-2}j_{n-1}
$$
となります。そして、$${e^{i2\pi \frac{j}{2^m}}}$$は、
$$
e^{i2\pi \frac{j}{2^m}} = e^{i2\pi (j_0j_1\cdots j_{n-1-m}.j_{n-m}\cdots j_{n-2}j_{n-1})} = e^{i2\pi (0.j_{n-m}\cdots j_{n-2}j_{n-1})}
$$
となります。最後の式変換は、$${e^{i2\pi}=1}$$より$${j}$$の整数部分を無視しています。この結果、
$$
=\frac{1}{\sqrt{2^n}}(\ket{0}+e^{i2\pi \frac{j}{2}}\ket{1})\otimes(\ket{0}+e^{i2\pi \frac{j}{2^2}}\ket{1})\otimes
\cdots \otimes
(\ket{0}+e^{i2\pi \frac{j}{2^n}}\ket{1})
$$
$$
=\frac{1}{\sqrt{2^n}}(\ket{0}+e^{i2\pi 0.j_{n-1}}\ket{1})\otimes(\ket{0}+e^{i2\pi 0.j_{n-2}j_{n-1}}\ket{1})\otimes \cdots \otimes(\ket{0}+e^{i2\pi 0.j_{0}j_{1}\cdots j_{n-1}}\ket{1})
$$
が最終的に得られます。つまり、量子フーリエ変換は、
$$
\ket{j_0}\otimes\ket{j_1} \otimes \cdots \otimes \ket{j_{n-1}} \rightarrow \frac{1}{\sqrt{2^n}}(\ket{0}+e^{i2\pi 0.j_{n-1}}\ket{1})\otimes(\ket{0}+e^{i2\pi 0.j_{n-2}j_{n-1}}\ket{1})\otimes \cdots \otimes(\ket{0}+e^{i2\pi 0.j_{0}j_{1}\cdots j_{n-1}}\ket{1})
$$
という作用になります。これを量子回路で表現するとこんな感じになります。
さてこのような変換を実現する$${U_{\rm QFT}}$$は、具体的にどんな量子回路で実現することができるでしょうか。ここでも、同じように具体例で考えてみましょう。
具体例: 1個の量子ビットの場合
量子ビット1個の場合($${n=1}$$)は、
$$
U_{\rm QFT}\ket{j_0} = \frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}}\ket{1})
$$
となります。ここで、$${{j_0}=0, 1}$$なので、
$$
U_{\rm QFT}\ket{0} = \frac{1}{\sqrt{2}}(\ket{0}+\ket{1})
$$
$$
U_{\rm QFT}\ket{1} = \frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.1}\ket{1}) = \frac{1}{\sqrt{2}}(\ket{0}-\ket{1})
$$
となります。つまり、アダマールゲートと同じになります。
具体例: 2個の量子ビットの場合
量子ビット2個の場合($${n=2}$$)は、
$$
U_{\rm QFT}(\ket{j_0}\otimes\ket{j_1}) = \frac{1}{\sqrt{2^2}}(\ket{0}+e^{i2\pi 0.j_{0}}\ket{1})\otimes(\ket{0}+e^{i2\pi 0.j_{1}j_{0}}\ket{1})
$$
となります。さて、$${n=2}$$の量子フーリエ変換は結果から書くと、以下のような量子回路で実現することができます。
一つずつ、回路を追っていきましょう。まず初期状態$${\ket{j_0}\otimes\ket{j_1}}$$に対して、アダマールゲートが一つ目の量子ビットに作用します。
$$
H\ket{j_0}\otimes\ket{j_1} = \frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}}\ket{1})\otimes\ket{j_1}
$$
そして、次に$${R_2}$$という制御ゲートがかかります。このゲートは、制御量子ビットが$${\ket{0}}$$の時はなにも作用せず、制御量子ビットが$${\ket{1}}$$の時は
$$
R_2 = \begin{pmatrix}
1 & 0 \\
0 & e^{i2\pi/2^2}
\end{pmatrix}
$$
という位相ゲートが作用します。それでは、実際にどのようになるか見てみましょう。まず、制御量子ビットである$${\ket{j_1}}$$が$${\ket{0}}$$の場合は
$$
\frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}}\ket{1})\otimes\ket{0}=\frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}0}\ket{1})\otimes\ket{0}
$$
となります。一方で、$${\ket{j_1}}$$が$${\ket{1}}$$の場合は、
$$
\frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi/2^2}e^{i2\pi 0.j_{0}}\ket{1})\otimes\ket{1}=\frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}1}\ket{1})\otimes\ket{1}
$$
となります。以上の結果をまとめると、
$$
R_2 \frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}}\ket{1})\otimes\ket{j_1} = \frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}j_1}\ket{1})\otimes\ket{j_1}
$$
となります。そして、最後に$${\ket{j_1}}$$に対して、アダマールゲートが作用します。その結果、
$$
\frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}j_1}\ket{1})\otimes H\ket{j_1} = \frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}j_1}\ket{1})\otimes\frac{1}{\sqrt{2}} (\ket{0}+e^{i2\pi 0.j_1}\ket{1})
$$
が得られます。しかし、この式をよく見ると、本来得たい結果と少し違うことがわかります。具体的には、量子ビットの順番が反対になっています。しかし、これは量子ビット間を入れ替えるSWAPゲートを作用させることで、簡単に修正することができます。その結果、
$$
U_{\rm SWAP} \frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}j_1}\ket{1})\otimes \frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_1}\ket{1}) = \frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_1}\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}+e^{i2\pi 0.j_{0}j_1}\ket{1})
$$
となり、正しい結果を得ることができます。
一般化: n個の量子ビットの場合
さてここまで具体例を見てきたところで、量子ビット$${n}$$個の場合に一般化をしてみましょう。$${n}$$量子ビットの量子フーリエ変換を実装するための量子回路は、以下のようなものになります。
具体例
それでは、量子フーリエ変換の具体例を計算してみましょう。
2量子ビットの場合
2量子ビットの量子フーリエ変換を考えてみます。まず、2量子ビットの量子フーリエ変換の回路は、以下のようになります。
ここで、具体例として入力$${\ket{0}\otimes\ket{0}}$$を考えます。
(0) 初期状態
$$
\ket{0}\otimes\ket{0}
$$
(1) 1番目の量子ビットにアダマールゲート
$$
\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\otimes\ket{0}
$$
(2) 1番目の量子ビットに制御位相ゲート
制御ビットが$${\ket{0}}$$のため、位相シフトはかからないので
$$
\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\otimes\ket{0}
$$
となります。
(3) 2番目の量子ビットにアダマールゲート
$$
\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})
$$
(4) 1番目と2番目の量子ビットにSWAPゲート
$$
\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})
$$
この式を整理すると、
$$
\frac{1}{2}(\ket{00}+\ket{01}+\ket{10}+\ket{11})=\frac{1}{2}(\ket{0}+\ket{1}+\ket{2}+\ket{3})
$$
となります。そして元の定義式より、
$$
U_{\rm QFT}\ket{0} = \frac{1}{\sqrt{2^2}}\sum_{k=0}^{2^2-1}e^{i2\pi\frac{k*0}{2^2}}\ket{k}=\frac{1}{2}(\ket{0}+\ket{1}+\ket{2}+\ket{3})
$$
となり、正しいことがわかります。
3量子ビットの場合
もう少し複雑な例として、3量子ビットの量子フーリエ変換の回路を考えます。
ここで、入力として$${\ket{0}\otimes\ket{1}\otimes\ket{1}}$$を考えます。
(0) 初期状態
$$
\ket{0}\otimes\ket{1}\otimes\ket{1}
$$
(1) 1番目の量子ビットにアダマールゲート
$$
\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\otimes\ket{1}\otimes\ket{1}
$$
(2) 1番目の量子ビットに制御位相ゲート
$$
\frac{1}{\sqrt{2}}(\ket{0}+e^{i\frac{\pi}{2}}\ket{1})\otimes\ket{1}\otimes\ket{1}
$$
(3) 1番目の量子ビットに制御位相ゲート
$$
\frac{1}{\sqrt{2}}(\ket{0}+e^{i(\frac{\pi}{2}+\frac{\pi}{2^2})}\ket{1})\otimes\ket{1}\otimes\ket{1}
$$
(4) 2番目の量子ビットにアダマールゲート
$$
\frac{1}{\sqrt{2}}(\ket{0}+e^{i(\frac{\pi}{2}+\frac{\pi}{2^2})}\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\otimes\ket{1}
$$
(5) 2番目の量子ビットに制御位相ゲート
$$
\frac{1}{\sqrt{2}}(\ket{0}+e^{i(\frac{\pi}{2}+\frac{\pi}{2^2})}\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}-e^{i\frac{\pi}{2}}\ket{1})\otimes\ket{1}
$$
(6) 3番目の量子ビットにアダマールゲート
$$
\frac{1}{\sqrt{2}}(\ket{0}+e^{i(\frac{\pi}{2}+\frac{\pi}{2^2})}\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}-e^{i\frac{\pi}{2}}\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})
$$
(7) 1番目と3番目の量子ビットにSWAPゲート
$$
\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}-e^{i\frac{\pi}{2}}\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}+e^{i(\frac{\pi}{2}+\frac{\pi}{2^2})}\ket{1})
$$
$$
=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}-e^{i\frac{\pi}{2}}\ket{1})\otimes\frac{1}{\sqrt{2}}(\ket{0}+e^{i\frac{3\pi}{4}}\ket{1})
$$
整理すると
$$
=\frac{1}{\sqrt{2^3}}(\ket{000}+e^{i\frac{3\pi}{4}}\ket{001}-e^{i\frac{\pi}{2}}\ket{010}-e^{i\frac{5\pi}{4}}\ket{011}-\ket{100}-e^{i\frac{3\pi}{4}}\ket{101}+e^{i\frac{\pi}{2}}\ket{110}+e^{i\frac{5\pi}{4}}\ket{111})
$$
$$
=\frac{1}{\sqrt{2^3}}(\ket{0}+e^{i\frac{3\pi}{4}}\ket{1}+e^{i\frac{3\pi}{2}}\ket{2}+e^{i\frac{9\pi}{4}}\ket{3}+e^{i\pi}\ket{4}+e^{i\frac{7\pi}{4}}\ket{5}+e^{i\frac{9\pi}{2}}\ket{6}+e^{i\frac{21\pi}{4}}\ket{7})
$$
$$
=\frac{1}{\sqrt{2^3}}(\ket{0}+e^{i\frac{3\pi}{4}}\ket{1}+e^{i\frac{3\pi}{2}}\ket{2}+e^{i\frac{9\pi}{4}}\ket{3}+e^{i3\pi}\ket{4}+e^{i\frac{15\pi}{4}}\ket{5}+e^{i\frac{9\pi}{2}}\ket{6}+e^{i\frac{21\pi}{4}}\ket{7})
$$
元の定義式より、
$$
U_{\rm QFT}\ket{011} = \frac{1}{\sqrt{2^3}}\sum_{k=0}^{2^3-1}e^{i2\pi\frac{k*3}{2^3}}\ket{k}
$$
$$
=\frac{1}{\sqrt{2^3}}(\ket{0}+e^{i2\pi\frac{3}{2^3}}\ket{1}+e^{i2\pi\frac{2*3}{2^3}}\ket{2}+e^{i2\pi\frac{3*3}{2^3}}\ket{3}+e^{i2\pi\frac{4*3}{2^3}}\ket{4}+e^{i2\pi\frac{5*3}{2^3}}\ket{5}+e^{i2\pi\frac{6*3}{2^3}}\ket{6}+e^{i2\pi\frac{7*3}{2^3}}\ket{7})
$$
$$
=\frac{1}{\sqrt{2^3}}(\ket{0}+e^{i\pi\frac{3}{4}}\ket{1}+e^{i\pi\frac{3}{2}}\ket{2}+e^{i\pi\frac{9}{4}}\ket{3}+e^{i3\pi}\ket{4}+e^{i\pi\frac{15}{4}}\ket{5}+e^{i\pi\frac{9}{2}}\ket{6}+e^{i\pi\frac{21}{4}}\ket{7})
$$
となり、量子フーリエ変換で得られた結果と等しいことがわかります。
量子フーリエ変換の凄さ
さて、ここまで量子フーリエ変換の原理について解説してきましたが、そもそも量子フーリエ変換はなにがすごいのでしょうか。結論から申し上げますと、古典のフーリエ変換と比較して、必要な計算量が大きく減ることが分かっています。
$${n}$$量子ビットの量子フーリエ変換に必要な量子ゲートの数について考えてみましょう。上図の量子回路で考えてみると、$${1}$$番目の量子ビットには、1個のアダマールゲートと$${(n-1)}$$個の制御位相ゲートの計$${n}$$個の量子ゲートが必要になります。同様にして、2番目の量子ビットには、$${(n-1)}$$個の量子ゲートが必要となります。最後の量子ビットには、1個のアダマールゲートが必要となり、その結果
$$
n+(n-1)+\cdots+1=\frac{1}{2}n(n+1)
$$
個の量子ゲートが必要となります。さらに、SWAPゲートが必要となります。SWAPゲートは、CNOTゲート3個の実現することができ、$${n}$$量子ビットに対しては、およそ$${n/2}$$個のSWAPゲートが必要となるので、結局CNOTゲートの数に換算すると、$${3n/2}$$個程度のCNOTゲートが必要となります。つまり結局のところ、計算量としては$${\mathcal{O}(n^2)}$$となることになります。つまり、$${n}$$量子ビットで扱える要素数である$${2^n}$$個のサンプル数に対して、$${\mathcal{O}(n^2)}$$という計算量でフーリエ変換を実行することができます。
一方で、離散的なデータのフーリエ変換を行う際には、高速フーリエ変換が用いられます。高速フーリエ変換は、$${N}$$個のデータ$${x_j \,(j=0,1,\cdots,N-1)}$$に対して、
$$
y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j {\rm exp}[i\frac{2\pi k j}{N}]
$$
という変換を実現するようなものです。$${N}$$個のデータに対して、$${\mathcal{O}(N\rm log \it N)}$$という計算量が必要となります。$${n}$$量子ビットで扱えるデータ数である$${N=2^n}$$を使って考えてみると、$${n2^n}$$という計算量が必要となります。この意味で、高速フーリエ変換と計算量を単純に比較して量子フーリエ変換は非常に高速だといえるということになります。
しかし、これには落とし穴があります。それは、量子フーリエ変換後の量子状態を正確に把握するには、指数関数回数の計算量が必要となることです。つまり、量子フーリエ変換後の量子状態は、
$$
\ket{j_0}\otimes\ket{j_1} \otimes \cdots \otimes \ket{j_{n-1}} \rightarrow
$$
$$
\frac{1}{\sqrt{2^n}}(\ket{0}+e^{i2\pi 0.j_{n-1}}\ket{1})\otimes(\ket{0}+e^{i2\pi 0.j_{n-2}j_{n-1}}\ket{1})\otimes \cdots \otimes(\ket{0}+e^{i2\pi 0.j_{0}j_{1}\cdots j_{n-1}}\ket{1})
$$
となります。このそれぞれの係数が、フーリエ係数$${y_k}$$に相当するものとなります。これらの係数を測定によって取り出すには、結局指数関数的な計算操作が必要となることになります。つまり、量子フーリエ変換によって得られた量子状態をどのように活用するかというのも、研究分野として非常に大切であることがわかります。