導入
Nielsen & Chuangのp.240に有限アーベル群の量子フーリエ変換について次のように書かれている。
“This means that the quantum Fourier transform of f over G is well defined (see Section A2.3),
and can still be done efficiently.”
この “well defined” と “can still be done efficiently” の意味を、
群フーリエ変換の構造から数式的に確認する。素人による個人的なメモ。
量子フーリエ変換の定義
量子フーリエ変換(QFT)は次の式で定義される。
F|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk / N} |k\rangle
ここで |j\rangle は計算基底。
この式は「|j\rangle をフーリエ変換行列 F の j列ベクトル（フーリエ基底）に写す操作」と見なせる。
加法群 \mathbb{Z}_N の量子フーリエ変換
アーベル群 \mathbb{Z}_N の既約表現はすべて1次元であり、その数は N に等しい。
ExerciseA2.24より、フーリエ変換行列は次のように書ける。
F =
\frac{1}{\sqrt{N}}
\begin{bmatrix}
\rho_0(x_1) & \rho_0(x_2) & \cdots & \rho_0(x_N) \\
\rho_1(x_1) & \rho_1(x_2) & \cdots & \rho_1(x_N) \\
\vdots & \vdots & \ddots & \vdots \\
\rho_{N-1}(x_1) & \rho_{N-1}(x_2) & \cdots & \rho_{N-1}(x_N)
\end{bmatrix}
便宜上、インデックスは0始まりとする。
量子フーリエ変換の定義に基づき、j列ベクトルを取り出すと\mathbb{Z}_N の量子フーリエ変換は
F|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \rho_k(j) |k\rangle
となる。\rho_k(j) = e^{2\pi i jk / N} とすると標準的な量子フーリエ変換の形に一致する。
直積群 \mathbb{Z}_N \times \mathbb{Z}_Mの量子フーリエ変換
群の元を (x, y) とする。
|G| = NM より、変換は
F|(x, y)\rangle = \frac{1}{\sqrt{NM}}
\sum_{k=0}^{N-1}\sum_{l=0}^{M-1}
\rho_{k,l}(x, y)|(k, l)\rangle
と書ける。
|(a,b)\rangle = |a\rangle|b\rangle とみなせば、
F|x\rangle|y\rangle
= \frac{1}{\sqrt{NM}} \sum_{k,l} \rho_{k,l}(x, y) |k\rangle|l\rangle
具体的な既約表現の一つは
\rho_{k,l}(x, y) = \exp\left(2\pi i\left(\frac{kx}{N} + \frac{ly}{M}\right)\right)
よりこれを代入すると
\begin{aligned}
F|x\rangle|y\rangle
&= \frac{1}{\sqrt{NM}} \sum_{k,l}
e^{2\pi i(kx/N + ly/M)} |k\rangle|l\rangle \
&=
\left(\frac{1}{\sqrt{N}}\sum_k e^{2\pi i kx/N}|k\rangle\right)
\otimes
\left(\frac{1}{\sqrt{M}}\sum_l e^{2\pi i ly/M}|l\rangle\right)
\end{aligned}
よって
F = \text{QFT}_N \otimes \text{QFT}_M
となる。
\mathbb{Z}_N \times \mathbb{Z}_Mの量子フーリエ変換は、それぞれの巡回群のQFTのテンソル積として表せる。
有限アーベル群全体への拡張とユニタリ性
有限アーベル群 G は次のように直積分解できる。
G \simeq \mathbb{Z}_{N1} \times \mathbb{Z}_{N2} \times \cdots
したがって量子フーリエ変換も
F_G = \text{QFT}_{N1} \otimes \text{QFT}_{N2} \otimes \cdots
と書ける。
各 \text{QFT}_{N_i} はユニタリ行列であり、ユニタリ行列のテンソル積もユニタリとなる。
したがって F_G 全体もユニタリであり、有限アーベル群上の量子フーリエ変換は well defined となる。
「can still be done efficiently」
有限アーベル群のQFTはテンソル積構造を持つ。
各巡回群のQFTは多項式サイズで実装できるため、
群の位数が多項式オーダーである限り、全体も多項式時間で実行可能。
これが “can still be done efficiently” の意味になる。
まとめ
有限アーベル群の量子フーリエ変換は
- 数学的には：テンソル積によるユニタリ構造（＝well defined）
- 計算的には：多項式時間で実行可能な構成（＝efficiently）
を持つ。
量子回路だけ見ると、各量子ビットをQFTゲートに通しているだけの単純な操作に見える。
しかし抽象的に見ると、その回路上では 有限アーベル群のフーリエ変換 を計算している。
量子アルゴリズムの内部で群構造そのものが動いている点が興味深い。
Discussion