量子フーリエ変換
修正履歴
・19Mar.2023: Eq.(4)周辺の軽微な誤りを修正
量子フーリエ変換の"パラドックス"
量子フーリエ変換は、ユニタリ変換を量子状態に施すことでフーリエ変換を実現する方法です。古典的なアルゴリズムによるフーリエ変換と比較し、本質的に高速なアルゴリズムと言われます。この変換は、他の量子アルゴリズムの構成要素として使用され、重要な役割を果たします。
ところが大変逆説的なことに、ある関数のフーリエ変換を、量子フーリエ変換により具体的に数値として得るのは現実的ではありません。
このパラドキシカルな状況の理由は
$$
\begin{aligned}
&量子状態にフーリエ係数の情報を埋め込むのは非常に高速であるが、\\
&その状態から実際にフーリエ係数を読み出すのは非常に大変である
\end{aligned}
$$
ことに由来します。本記事では量子フーリエ変換を解説し、この不思議な状況に関して説明したいと思います。
以下に略称をまとめておきます:
・CC 古典コンピュータ（Classical Computer）
・QC 量子コンピュータ（Quantum Computer）
・FT フーリエ変換（Fourier Transform）
・DFT 離散フーリエ変換（Discrete Fourier Transform）
・FFT 高速フーリエ変換（Fast Fourier Transform）
・QFT 量子フーリエ変換（Quantum Fourier Transform）
以下、$${:=}$$は「左辺を右辺で定義する」、$${=:}$$はその逆を意味します。また$${\sigma_z}$$はスピン$${z}$$成分の演算子を表します。
離散フーリエ変換
本記事で扱うのは離散フーリエ変換（DFT）です。これはある$${\{x_i\}_{i=0\text{ -- }N-1}, \ \ x_i\in {\mathbb C}}$$が与えられたとき、以下の$${\{y_i\}_{i=0\text{ -- }N-1}, , \ \ y_i\in {\mathbb C}}$$を計算する操作です：
$$
\begin{aligned}
&y_j=\sum_{k=0}^{N-1}\exp(-2\pi i j k/N)x_k,\ \ N\in {\mathbb N}, \ \ 0\le j\le N-1\\
&\hspace{2cm}(iは虚数単位)
\end{aligned}
$$
これは「関数を波の重ね合わせで表す」「音をドレミで表す」ような操作に対応します（トップ画像が海の波なのはそのためです）。DFTは様々な分野の情報処理において使用されています。身近な音楽、写真、動画、さらにはCTスキャンや超音波エコー等の医学においても使われています。
量子フーリエ変換の基本的なアイディア
量子フーリエ変換（QFT）の話に移ります。以下ではRef.[1]に従い、DFTを
$$
\displaystyle
y_j = \sum_{k=0}^{N-1} \exp(2\pi i j k/N)x_k \hspace{1cm} (1)
$$
で定義します（$${\exp}$$の肩の符号を逆にしました）。QFTでは適切な変換により$${\boldsymbol y_j}$$を量子状態に埋め込みます。
そのために、ラベルをつけた何らかの正規直交基底$${|j)}$$（$${0\le j\le N-1}$$）を用意します。ここでケットの右側が丸括弧 ")" なのは、このあと登場するスピンの量子状態と区別するためです。これに$${x_j}$$をかけて$${j}$$について和をとります：
$$
x_0|0)+x_1|1)+\ldots+x_{N-1}|N-1)=\sum_{j=0}^{N-1}
x_j |j)
$$
ここで、基底$${|j)}$$に次の変換を施します：
$$
|j)\rightarrow\sum_{k=0}^{N-1} \exp(2\pi i j k/N)|k)
$$
すると状態$${\sum_{j=0}^{N-1}x_j |j)}$$は
$$
\sum_{j=0}^{N-1}x_j |j) \rightarrow \sum_{k=0}^{N-1}y_k|k)
$$
のように変換することはすぐにわかります。すなわち$${\displaystyle\sum_{j=0}^{N-1}x_j|j)}$$に上記の基底の変換を行えば、各基底の係数としてDFTが現れます。
以下$${|j)}$$としてスピン状態を用いることにします。$${j}$$をバイナリ表示(=2進数表示)して各々のビットにスピンup とdownを対応させます。つまり
$$
j=j_1+j_22^1+j_32^2+\ldots+j_N2^{N-1} \ \ (j_i\in \{0,1\}, 1\le i\le N-1)
$$
に対し
$$
\begin{aligned}
&|j)\leftrightarrow |j_1\rangle_1\otimes|j_2\rangle_2\otimes\ldots \otimes |j_{N-1}\rangle_{N-1}
\end{aligned}
$$
のように状態を対応させます。ただし$${|j_i=0\rangle_i}$$は$${i}$$番目のスピンup状態（$${\sigma_z}$$の固有値が正）、$${|j_i=1\rangle_i}$$は$${i}$$番目のスピンdown状態（$${\sigma_z}$$の固有値が負）とします。
表記の簡約化のため、以下では
$$
\begin{aligned}
|j_1j_2\ldots j_{N-1}\rangle&:=|j_1\rangle_1\otimes|j_2\rangle_2\otimes\ldots \otimes |j_{N-1}\rangle_{N-1}, \\
|j\rangle&:=|j_1j_2\ldots j_{N-1}\rangle, \\ (j=j_1+j_22^1+j_32^2+&\ldots+j_N2^{N-1}, \ \ j_i\in \{0,1\}, \ \ 1\le i\le N-1)
\end{aligned}
$$
とします。そして、スピン系における基底の変換
$$
|j\rangle\rightarrow\sum_{k=0}^{N-1} \exp(2\pi i j k/N)|k\rangle \hspace{1cm} (2)
$$
を実現する量子回路の構築を行います。
スピンの直積による表示
Eq.(2)の右辺を、各スピン状態の直積で表示します。
$${N=2^n}$$として、$${n}$$スピン系を考えます。するとEq.(2)の右辺は
$$
\displaystyle
\frac{1}{2^{n/2}}\sum_{k=0}^{2^n-1}\exp(2\pi ijk/2^n)|k\rangle
$$
ですが（Ref.[1]に合わせるためnormalizationの$${\displaystyle\frac{1}{\sqrt{N}}=\frac{1}{2^{n/2}}}$$をかけた）、これに$${k}$$のバイナリ表示を代入するとEq.(2)の変換は以下のようになります：
$$
\begin{aligned}
|j\rangle&\rightarrow\frac{1}{2^{n/2}}\sum_{k=0}^{2^n-1}e^{2\pi i jk/2^n}|k\rangle \\
&=\frac{1}{2^{n/2}}
\sum_{k_1=0}^1\sum_{k_2=0}^1\ldots \sum_{k_n=0}^1
e^{2\pi ij \left(\sum_{l=1}^nk_l 2^{-l}\right)}|k_1\ldots k_n\rangle\\
&=\frac{1}{2^{n/2}}
\sum_{k_1=0}^1\sum_{k_2=0}^1\ldots \sum_{k_n=0}^1
\bigotimes_{l=1}^n e^{2\pi i j k_l 2^{-l}}|k_l\rangle_l\\
&=\frac{1}{2^{n/2}}\bigotimes_{l=1}^n
\left[\sum_{k_l=0}^1e^{2\pi i j k_l 2^{-l}}|k_l\rangle_l\right]\\
&=\frac{1}{2^{n/2}}\bigotimes_{l=1}^n
\left[|0\rangle_l+e^{2\pi i j 2^{-l}}|1\rangle_l\right] \hspace{1cm} (3)
\end{aligned}
$$
ここで$${\displaystyle \bigotimes_{l=1}^m|k_l\rangle_l:=|k_1\rangle_1\otimes|k_2\rangle_2\otimes\ldots\otimes|k_m\rangle_m}$$です。
次に小数バイナリ表示を導入します：
$$
j/2^n=j_1/2^1+j_2 2^2+\ldots +j_N/2^n=: 0.j_1j_2\ldots j_n
$$
Eq.(3)に現れる指数の肩の$${j/2^l}$$をバイナリ表示すると
$$
\begin{aligned}
j/2^{l} &=(j_1 2^{n-1}+j_2 2^{n-2}+\ldots+j_n 2^0)/2^{l}\ \ \ \ \ \ (l=1,2,\ldots, n)\\
&=j_1 2^{n-1-l}+j_2 2^{n-2-l}+\ldots+j_n 2^{-l}
\end{aligned}
$$
です。ここで$${\exp(2\pi i (j/2^{-l}))}$$において$${j/2^{-l}}$$の整数部分は周期性により無視できます。よって$${\exp(2\pi i (j/2^{-l}))}$$の肩を小数バイナリ表示すると
$$
\begin{aligned}
l&=1\text{ では } j/2^{-l}=j_n/2^{1}=0.j_n\\
l&=2\text{ では } j/2^{-l}=j_{n-1} /2^2+j_n/2^{1}=0.j_{n-1}j_n\\
\vdots\\
l&=n\text{ では } j/2^{-l}=j_1 /2^1+j_2/2^{2}+\ldots+j_n/2^n=0.j_1j_2\ldots j_n
\end{aligned}
$$
となります。ゆえに Eq.(3)は
$$
\displaystyle
=\frac{1}{2^{n/2}}(|0\rangle+e^{2\pi i0.j_n}|1\rangle)
(|0\rangle+e^{2\pi i0.j_{n-1}j_n}|1\rangle)
\ldots
(|0\rangle+e^{2\pi i 0.j_1j_2\ldots j_n}|1\rangle)
$$
と書けます。ここで直積の記号$${\otimes}$$は省略しました。丸括弧ごとに、左からスピン1、2、3…の状態であり、それらの直積だとみなします。以降$${|a\rangle|b\rangle|c\rangle…}$$はスピン1が状態$${|a\rangle}$$、スピン2が$${|b\rangle}$$、スピン3が$${|c\rangle}$$…という直積を表すと了解してください。
まとめると以下のようになります：
$$
\begin{aligned}
&\{x_j\}_{j=1,\ldots, N} \ (N=2^n) \ の{\rm DFT}を得るには、\sum_{j=0}^{N-1}x_j|j\rangleに対して\\
&以下の変換:\\
&{}\\
&|j\rangle\rightarrow \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\exp(2\pi ijk/N)|k\rangle\\
& \ \ \ \ \ =\frac{1}{2^{n/2}}(|0\rangle+e^{2\pi i0.j_n}|1\rangle)
(|0\rangle+e^{2\pi i0.j_{n-1}j_n}|1\rangle)\\
&\hspace{4cm}\ldots (|0\rangle+e^{2\pi i 0.j_1j_2\ldots j_n}|1\rangle) \hspace{1cm} (4)\\
&{}\\
&を施せばよい。これにより\\
&{}\\
&\ \ \ \ \ \ \sum_{j=0}^{N-1}x_j|j\rangle\rightarrow\sum_{k=0}^{N-1}y_k|k\rangle , \ \ \ y_k=\sum_{l=0}^{N-1}\exp(2\pi i k l/N)x_l\\
&{}\\
&を得る。\\
&{}\\
&\{x_j\}の{\rm DFT}\{y_j\}のうちy_mを得たければ、{\rm Eq.}(4)に左から\langle m|を\\
&作用させればよい。
\end{aligned}
$$
あとはEq.(4)を実現する具体的な方法を考えればよいのですが、これを「量子力学的なユニタリー変換=量子ゲート」の組み合わせで実現するのが量子フーリエ変換です。そして次の章で見るように、Eq.(4)の形に書き直しておくと、アダマールゲート及び制御$${R_k}$$ゲートという量子ゲートの組み合わせによりフーリエ変換を実現できることが分かります。
QFTの量子回路
量子回路は「量子ゲート」と呼ばれる「量子状態をユニタリ変換する部品」から構成されます。本章ではEq.(4)の変換を実現する量子回路を構築します。以下qubitとはスピン状態のことを指します。
QFTでは次の2種類の量子ゲートを用います:
アダマール（Hadamard）ゲート
これは1 qubitに作用するゲートであり、以下のように状態を変換します:
$$
\begin{aligned}|0\rangle&\mapsto\frac{|0\rangle+|1\rangle}{\sqrt{2}},\\ |1\rangle&\mapsto\frac{|0\rangle-|1\rangle}{\sqrt{2}}
\end{aligned}
$$
制御$${R_k}$$（controlled-$${R_k}$$）ゲート$${\\ }$$
これは2 qubitに作用するゲートです。そのうち1つは制御用のqubit、もうひとつが制御されるqubitです。制御用qubitが$${|1\rangle}$$のときのみ、制御されるqubitの$${|1\rangle}$$に$${e^{2\pi i/2^k}}$$の位相をかけます。
アダマールゲートを$${\hat H}$$で表します。$${\alpha |0\rangle+\beta |1\rangle}$$にアダマールゲートが作用すると
$$
\begin{aligned}
\hat H (\alpha |0\rangle +\beta |1\rangle)=\frac{1}{\sqrt{2}}(\alpha+\beta)|0\rangle +\frac{1}{\sqrt{2}}(\alpha-\beta)|1\rangle
\end{aligned}
$$
となります。
制御$${R_k}$$ゲートを$${\hat R_k^{(lm)}}$$で表します。上の添字の左側$${l}$$は制御qubitのラベル、$${m}$$は制御されるqubitのラベルとします。このとき
$$
\hat R_k^{(lm)} |j_l\rangle(\alpha|0\rangle_m+\beta|1\rangle_m)=|j_l\rangle(\alpha|0\rangle_m+e^{2\pi i j_l/2^k}\beta |1\rangle_m)
$$
となります（これが正しいことを確認してみてください）。
以上の準備のもと、次のようなゲートのシーケンスがどのように状態に作用するかを考えます：
$$
\begin{aligned}
\hat H |j_1\rangle&=\frac{1}{2^{1/2}}(|0\rangle + e^{\pi i j_1}|1\rangle)\\
&=\frac{1}{2^{1/2}}(|0\rangle + e^{2\pi i j_1/2^1}|1\rangle)\\
&=\frac{1}{2^{1/2}}(|0\rangle + e^{2\pi i 0.j_1}|1\rangle)\\
R_2^{(j_2j_1)}\hat H |j_1\rangle|j_2\rangle&=
\frac{1}{2^{1/2}}(|0\rangle + e^{2\pi i (0.j_1+j_2/2^2)}|1\rangle)|j_2\rangle\\
&=\frac{1}{2^{1/2}}(|0\rangle + e^{2\pi i 0.j_1j_2}|1\rangle)|j_2\rangle\\
R_3^{(j_3j_1)}R_2^{(j_2j_1)}\hat H |j_1\rangle|j_2\rangle|j_3\rangle&=
\frac{1}{2^{1/2}}(|0\rangle + e^{2\pi i (0.j_1j_2+j_3/2^3)}|1\rangle)|j_2\rangle|j_3\rangle\\
&=\frac{1}{2^{1/2}}(|0\rangle + e^{2\pi i (0.j_1j_2j_3)}|1\rangle)|j_2\rangle|j_3\rangle\\
&\hspace{0.5cm} \vdots
\end{aligned}
$$
上記の考察から、以下の関係がわかります：
$$
\begin{aligned}
R_k^{(j_{i+k}j_i)}R_{k-1}^{(j_{i+k-1}j_i)}\ldots R_2^{(j_{i+1}j_i)}\hat H^{(i)}|j_1\rangle|j_2\rangle\ldots|j_{i-1}\rangle|j_i\rangle|j_{i+1}\rangle\ldots |j_{i+k}\rangle\\
=(|j_1\rangle|j_2\rangle\ldots|j_{i-1}\rangle)\frac{1}{2^{1/2}}(|0\rangle_i+e^{2\pi i 0.j_ij_{i+1}\ldots j_{i+k}}|1\rangle_i)|j_{i+1}\rangle\ldots |j_{i+k}\rangle
\end{aligned}
$$
ここでは$${\hat H^{(i)}}$$は$${|j_i\rangle}$$に作用するアダマールゲートとしました。この操作をいくつか組み合わせればEq.(4)の状態を作れそうです。いま演算子$${\hat K(i;k)}$$を
$$
\hat K(i;k):=\hat R_k^{(j_{i+k}j_i)}\hat R_{k-1}^{(j_{i+k-1}j_i)}\ldots R_2^{(j_{i+1}j_i)}\hat H^{(i)}
$$
で定義すると、Eq.(4)の量子状態は、$${\hat K}$$の組み合わせにより、以下のように与えられることがわかります：
$$
\begin{aligned}
{\rm Eq.}(4)&=\frac{1}{2^{n/2}}(|0\rangle+e^{2\pi i0.j_n}|1\rangle)
(|0\rangle+e^{2\pi i0.j_{n-1}j_n}|1\rangle)
\ldots
(|0\rangle+e^{2\pi i 0.j_1j_2\ldots j_n}|1\rangle)\\
&=\hat K(n;0)\cdots\hat K(2;n-2)\hat K(1;n-1)|j_1j_2\ldots j_n\rangle
\end{aligned}
$$
$${\hat K}$$の順番に注意してください。可換ではありません。
これを図にすると以下のようになります (Ref.[1]より引用)：
以上で量子フーリエ変換を行う量子回路が構成できました。
量子フーリエ変換の計算量
QFTの計算量を、古典計算機（CC）で行う高速フーリエ変換（FFT）と比較します。
以下長さ$${N=2^n}$$（$${n}$$スピン系）のFTを考えます。このとき、DFT、FFT、QFTの計算量は以下のようになります：
DFT: $${N^2=2^{2n}}$$程度。定義式からわかるかと思います。
FFT: $${N\log N=n\times 2^n}$$程度。これに関しては例えばRef.[2]参照のこと。
QFT: 前章の図には、量子ゲートが$${O(n^2)}$$コ存在する。これら1つ1つのゲートにおける操作の計算量を1とすれば、計算量は$${O(n^2)}$$
前章の量子回路の図をみると、特定のスピン固有状態$${|m\rangle}$$のみ扱っているように見えますが、実際には状態を$${x_j}$$のウェイトで重ね合わせて初期状態$${\sum_j x_j|j\rangle}$$を用意することで、$${x_j|j\rangle}$$すべてに対して一度に計算を行えます。よって、計算量を見積もるときには、これを考慮する必要はありません。このような計算の並列性は「量子並列性」と言われます。また、フーリエ変換の表現をスピンの基底の直積に分解することができましたが、このような「テンソル積分解」もQFTの計算量が減る理由です。ただし「テンソル積分解」はFFTでも使われているので、QFT特有の性質ではありません。
QFTにおいて1つのゲートの計算量を1とするのは乱暴ではないか？と思うかもしれません。私にはそれを本当のところどう見積もるのかはよくわかりません。ここに述べた計算量の大小がそのまま計算速度の大小と対応しているかは非自明です。
まあでも、いろいろあるかもしれませんが、上の計算量の見積もりだけで言えば、FFTより本質的に高速な計算ができそうにも思います。
量子フーリエ変換は本当に速い？
前章で行った計算量により「QFTはFFTよりも高速」と結論するのは早計です。なぜなら
$${量子状態{\rm Eq.(4)}の構成は高速だが、その量子状態からフーリエ係数の\\ 情報を得るのが大変}$$
だからです。
Eq.(4)の下で、私はサラッと「$${y_m}$$を求めたいならEq.(4)の状態に左から$${\langle m|}$$を作用させろ」と書きました。これは実際の量子回路では、Eq.(4)の状態を何度も観測し、$${\boldsymbol |m\rangle}$$がどのくらいの確率で出現するかを測定することに対応します。そしてこれは大変時間のかかる作業です。
QFTの量子回路で作られた状態を$${|\psi\rangle}$$で表すと、これと$${\langle m|}$$との内積をとった量$${\langle m|\psi\rangle}$$は、$${|m\rangle}$$表示（$${\sigma_z^{(i)} \ (1\le i\le n)}$$の固有状態の直積による表示）の波動関数です。つまりは変換後の状態の$${|m\rangle}$$表示の波動関数がフーリエ係数です。$${|\psi\rangle}$$を観測して状態$${|m\rangle}$$を得る確率は波動関数の絶対値の２乗$${|\langle m|\psi\rangle|^2}$$に比例します。よって、この波動関数(=フーリエ係数)を求めるには、量子状態を観測した時に$${|m\rangle}$$が相対的にどのくらい見いだせるかを調べる必要があるのです。しかも悲しいかな、一度観測したらもう一度同じ状態を作り直して観測する必要があります。何回観測するかはどの程度フーリエ係数を精度よく求めるかにも依存すると思いますが、観測まで考慮するとFFTよりかなり計算が遅くなり（おそらく計算機としては使えないほど）、現実的ではないようです。
個人的な感覚ですが、波動関数を実験で知るという行為は「箱の中身はなんだろな」ゲームに近いように感じます。何度も何度も手で触ってそれを推測しなければなりません。しかも量子力学の場合それが確率的であり、触るたびに違うことが起きる。その統計から中身を知るしかありません。「クイズの正解は箱の中に入っています！触ってもいいけど見てはダメ」と言われたら、それは答えというよりヒントです。
QFTを「実際にDFTとして使う」には、さらに他の困難もあるようです。Ref.[1]では、フーリエ変換したい元の状態$${\sum_j x_j|j\rangle}$$を効率よく作る方法がないことも、難しさのひとつであることを指摘しています。
ということで、QFTがFFTに取って代わる日はそう簡単には来ないようです。ただし冒頭にも述べたように、他の量子アルゴリズムにおいてQFTは部品として使われ大事な役割を果たします。例えば因数分解の量子アルゴリズムとして有名な「Shorのアルゴリズム」にもQFTが使われています。
まとめ
本記事では、量子フーリエ変換 (QFT) の解説をしました。QFTの基本的な考え方、量子回路の構成に都合の良いQFTの表示を示し、その後量子回路を具体的に構成しました。そのうえで、QFTにより実際にフーリエ係数を求めるのは、QFTの量子回路により構成された状態の観測の困難さにより現実的ではないことを述べました。
QFTは「高速で量子状態にフーリエ変換の情報を埋め込む方法」というのが正しい表現のように思います。量子計算一般に言えると思うのですが、何らかの問題の正解をエンコードした波動関数を構成するだけではあまり意味がないです。その中から如何にして正解の状態を抜き出すか（例えば不正解に対応する状態を量子干渉により打ち消し合わせることで抜き出す）、というのが本質的で難しい点だと思います。
「量子並列性」という言葉を使うときは気をつけなくてはいけないように思います。QFTでは、$${x_j |j\rangle}$$の$${j}$$を重ね合わせ$${\sum_j x_j |j\rangle}$$を入力することで、$${j}$$それぞれで計算することなく一度にフーリエ変換を行うことはできます。この事実をもって「量子並列性」と言うのはかまわないと思います。しかし「量子並列性があるから量子計算は速い」というような、計算の速さに関する主観を入れる際には慎重になるべきです。実際「フーリエ係数を人間が知る」という目的において、量子並列性があるからQFTが速いとは言えません。「量子並列性」という言葉は、量子状態の重ね合わせを量子計算において利用している、という事実を表す言葉として用いるべきように思います。
量子コンピュータの「速さ」という概念は、その数学的・情報学基礎論と大きく関わっており、話が大変込み入っているようです。こんな記事を書いておきながら、私はこれに関してほとんど知らないです。このあたりの理論的なことに興味のある方は例えばRef.[3]をご参照ください。また量子コンピュータ実機のことも私にはわかりません。本記事に述べたことは、量子コンピュータのほんの一部の側面だけであることを断っておきます。
Acknowledgment
この記事は、2023年1月ごろ「ゆるコンピュータ科学ラジオ」というYouTubeチャンネルで特集された量子コンピュータの話題に触発されて書いたものです（Ref.[4]）。量子コンピュータはたくさんの誤解にまみれているため、その誤解を少しでも払拭しようという切り口で作られた動画でした。大変楽しく聴かせて頂きました。
おしまい。$${{}_\blacksquare}$$
References
[1] Michael A. Nielsen, Isaac L. Chuang, "Quantum Computation and Quantum Information -10th Anniversary Edition- ," Cambridge University Press (2011).
[2] puremoru, 「高速フーリエ変換 その1」、「高速フーリエ変換その2（+少し量子力学）」
[3] 森前智行 (京都大学基礎物理学研究所）「量子スプレマシーと量子計算の検証」.
[4] ゆるコンピュータ科学ラジオ「量子コンピュータのエアプを撃墜しまくる動画 with 物理学者（見込）【量子コンピュータ1】#56」https://www.youtube.com/watch?v=vkmbLbiLomU&t=1886s
この記事が気に入ったらサポートをしてみませんか？