量子コンピュータに入門してるその2 量子フーリエ変換
κeenです。前回に引き続き量子コンピュータと量子通信を読んでいます。 今回は5章の量子フーリエ変換。勉強中の身で自分の理解を書いているのでみなさん内容は一切信用しないでくださいね。
$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $
フーリエ変換達
みんな大学の授業でやったフーリエ変換…って書こうとしたけど習った記憶がない。 いや、もちろん波動の授業ではやったけどああいういい加減な授業でなくてゃんとした習い方をしてない気がする。 まあ、おおざっぱには「周期関数は三角関数の和でかける」ってやつですね。
離散フーリエ変換変換はその離散版。 $N$ 個の点で標本をとるものです。
\[ F(t) = \frac{1}{\sqrt{N}}\sum^{N-1}_{x=0} f(x) e^{-2\pi{}i\frac{tx}{N}} \]
の式で表されます。 $e^{-2\pi{}i}$ の有理数乗なので心の目で三角関数が見えると思います。 ここで、 $x$ が $0$ から $N-1$ まで1刻みと決まっているので$f(x)$ は予め計算してベクトルか数列かなにかにしておくことができます(雑)。 これを $\{x_n\}_{n \in \{0, \cdots, N - 1\}}$ で表すことにすると
\[ F(t) = \frac{1}{\sqrt{N}}\sum^{N-1}_{j=0} x_j e^{-2\pi{}i\frac{jt}{N}} \]
とも書けます。実用上 $\{x_n\}$ を復元するには $N$ 個の点の値が知れればいいので$F(t)$も$N$個あればよく、 $k \in \{0,\cdots,N-1\}$に対して
\[ y_k = \sum^{N-1}_{j=0} x_j e^{-2\pi{}i\frac{jk}{N}} \]
がよく使う形になります。
そして量子フーリエ変換は正規直行基底$\ket{0}, \cdots ,\ket{N-1}$ 上の状態 $\sum^{N-1}_{j=0}x_j\ket{j}$ の各係数$x_j$を離散フーリエ変換したもの、すなわち
\[ \sum^{N-1}_{j=0}x_j\ket{j} \to \sum^{N-1}_{k=0}y_k\ket{k} \]
ですが各基底がどう変換されるのかを表示した方がわかりやすいようです。それがこちら。
\[ \ket{j} \to \frac{1}{\sqrt{N}}\sum^{N-1}_{k=0} e^{-2\pi{}i\frac{jk}{N}}\ket{k} \]
整数値 $j$ を位相にエンコードしてるイメージですね。
この変換はユニタリーなので(演習5.1)逆変換が存在します。 量子計算は観測以外が可逆なので簡単に逆変換が構成できるんですね。 計算アルゴリズムを与えたら回路の随伴をとればよし。計算量(ゲート数)も変わらないので解析がしやすいですね。
フーリエ変換は整数値を位相にエンコードするものですから逆変換は位相を整数値にデコードできるということになります。 位相といえばユニタリ行列の固有値。望ましい位相を持つユニタリを作って掛け回して量子フーリエ逆変換をすれば欲しい値が求められます。
位相推定
量子フーリエ逆変換の使い方の1つが位相推定で、ユニタリ行列の固有値の位相を得ることができます。 もちろん、位相は連続値を取るのに対して量子レジスタは有限長で離散値をとるので離散化に伴う誤差が生じます。
この位相をフーリエ逆変換に掛けられる形にエンコードする方法が面白かったので紹介します。
逆変換なので先の式の左右が入れ替わります。
\[ \frac{1}{\sqrt{N}}\sum^{N-1}_{k=0} e^{-2\pi{}i\frac{jk}{N}}\ket{k} \to \ket{j} \]
ここでで$\phi = -2\pi{}i\frac{j}{N}$とおくと
\[ \frac{1}{\sqrt{N}}\sum^{N-1}_{k=0} e^{\phi{}k}\ket{k} \to \ket{j} \]
となります。$\frac{1}{\sqrt{N}}\sum^{N-1}_{k=0} \ket{k}$ は重ね合わせ状態で、Hadamardゲートで簡単に作れるのであとは$k$が与えられたときに$e^{\phi{}k}$を計算する手段さえあれば左辺の式を簡単に作れます。 これは$U\ket{u} = e^{\phi}\ket{u}$ なるユニタリ $U$、固有値 $e^{\phi}$、固有ベクトル$\ket{u}$ を用いて $U^k\ket{u} = e^{\phi{}k}\ket{u}$のように構成できます。
(ツール表現力の問題でわかりにくいですが$q0$はn - qubitのレジスタ、制御 $U^k$ は $q0$から$k$を読み取って$U^k$を計算する、の意味です)
重ね合わせ状態ってこうやって使うんだな〜と感動しました。
因みにこの$U^j$を求めるのは、量子フーリエ変換も同様なのですが、qubit数に対して多項式ゲート数で可能です。n個のqubitで表現できる数は$2^n$までなので非常に効率的ですね。 「2進表記で$n$桁目が1ならば$2^{n-1}$足す、0ならば何もしない」が制御演算でできるので重ね合わせ状態のまま計算できるのが効いてるんですかね。
応用: 周期関数とか
フーリエ変換なのである種の周期関数の周期を発見できます。たとえば互いに素な$x$と$N$に対して
\[ x^r \equiv 1 \pmod{N} \]
を満たすような最小の正整数$r$を見つけることができます(こういう$r$を位数といいますね)。 これの周期性は$f(n) = x^n \pmod{N}$とすれば$f(n+r) = x^{n+r} \pmod{N} = x^n \pmod{N} = f(n)$から分かるかと思います。 教科書にはこれを量子フーリエ逆変換で求めるために周期$r$の計算を作ったり(剰余指数化)$r$に依存せずに固有ベクトルの和を作ったり(演習5.13)(正n角形の重心は原点みたいな話)観測した位相から$r$を復元したり(連分数展開)、と回路の構築に必要な構成方法が載っています。
さらに、位数が効率的に分かるならばそれをオラクル的に扱って古典的アルゴリズムで素因数分解が可能です(shorのアルゴリズム)。
他にも量子フーリエ逆変換で離散対数問題を解けたりだとか。より一般には隠れ部分群問題が解けます。 教科書では剰余類とか部分群とか難しそうな話をしてますが要は単純な(周期内では単射な)周期関数の周期を見つけられるというステートメントですかね。κeenは物事を単純化して捉えがちなので群論によるステートメントの方が周期関数によるステートメントより一般的かもしれませんがよく分からないです。
感想
4章までではユニタリ変換で生じる位相は全体位相だから消えてしまうのではないかと思っていたが位相推定のところでと制御演算を使うと$\ket{1}$のときにのみ位相がずれるので$\ket{0}+\ket{1}$が$\ket{0}+e^\phi\ket{1}$になるのに気づいて意味を理解した。同時に制御演算は制御に使う方のレジスタは変化しないと思っていたが「$\ket{1}$の場合のみ位相がずれる」という形でフィードバックを受けるのも新鮮だった。本当は4章で理解しておくべき内容だった気がするが…。
最初は位数発見問題とかは何をやってるのかあまり理解していなかったがこのブログにまとめるうちに理解できた。 5章は演習問題は紙には解かずに頭の中で考えるだけにしたが読むのは格段に速くなった。しかしプログにまとめるのが遅くなった。この辺うまくバランスを取りたい。
その他
$x^r \equiv 1 \pmod{N}$のレンダリングがキモいんですがそういうものですか？
追記
/ 追記(mod N)は \pmod{N}と書けば綺麗になるはずです
— koba(社畜化待ったなし) (@kobae964) 2018年5月19日
文章内でケットを表記するにあたって以下の記事を参考にしました。yyuさんありがとうございます。