量子アルゴリズム概観

量子情報入門　第1章 §1.6

代表的な量子アルゴリズムを、詳細な回路よりも「なぜ量子的優位性が生まれるか」に焦点を絞って概観する。

Deutsch–Jozsaアルゴリズム

関数 $f:\{0,1\}^n\to\{0,1\}$ が「定数」か「バランス($0$と$1$を半々に返す)」のどちらかであることが約束されているとき、どちらか判定したい。古典決定的アルゴリズムでは最悪 $2^{n-1}+1$ 回の $f$ の評価が必要だが、量子アルゴリズムでは1回で判定できる。鍵は、$f$ の値を全ての $x$ で同時に「重ね合わせで」計算し、Hadamard変換で干渉させることで大域的な性質を1回の測定で読み出す点にある。

Groverアルゴリズム(振幅増幅)

$N=2^n$ 個の要素のうちマーク付き要素を1つ探す問題。古典的には最悪 $N$ 回、平均 $N/2$ 回のクエリが必要だが、Grover のアルゴリズムでは$O(\sqrt N)$ 回で高確率で見つかる。この2乗の高速化は、量子アルゴリズムが非構造的探索に対して達成できる最良の一般的高速化であることが知られている(BBBV下界)。

幾何学的描像

全 $N$ 個の状態を「マーク要素の張る部分空間」と「その直交補空間」に分けて2次元平面を考える:

$$\ket\beta = \ket{x_\ast}\ \text{(マーク要素)},\qquad \ket\alpha = \frac{1}{\sqrt{N-1}}\sum_{x\neq x_\ast}\ket x\ \text{(非マーク)}.$$

初期の一様重ね合わせ

$$\ket s = \frac{1}{\sqrt N}\sum_x \ket x = \cos\frac{\theta}{2}\ket\alpha + \sin\frac{\theta}{2}\ket\beta,\qquad \sin\frac\theta2 = \frac{1}{\sqrt N}$$

はこの2次元平面内のベクトルで、$\ket\alpha$ 軸のごく近く(角度 $\theta/2\approx 1/\sqrt N$)に位置する。振幅としてはマーク要素は $1/\sqrt N$ しか含まれていない。

Groverの1反復 $G$ は「マーク要素の位相反転(オラクル)」と「$\ket s$ に関する反転(拡散変換)」の合成で、これは幾何学的にはこの2次元平面内での角度 $\theta$ の回転になる(2つの鏡映の合成は回転)。

$\ket s$ から $\ket\beta$ に到達するまでに必要な回転角は約 $\pi/2$。1回で $\theta \approx 2/\sqrt N$ しか回らないので、必要な反復回数は

$$k \approx \frac{\pi/2}{\theta} \approx \frac{\pi}{4}\sqrt N.$$

「ステップサイズ $\sim 1/\sqrt N$ で目的地まで距離 $\sim 1$ を歩くから、$\sqrt N$ 歩必要」という描像である。

Shorの因数分解アルゴリズム

RSA暗号の安全性の基礎となる整数の素因数分解問題は、古典的には多項式時間アルゴリズムが知られていない($O(\exp(n^{1/3}\log^{2/3} n))$ 程度)。しかしShorのアルゴリズムは $n=\log N$ ビットの数 $N$ を多項式時間 $O(n^3)$ で因数分解する。

構造は以下の3段階からなり、核心の量子計算は最後のQFT に集約されている:

各ステップの意味:

1. 古典帰着(因数分解 → 位数発見):$1<a<N$ をランダムに選び、$a^r\equiv 1\pmod N$ を満たす最小の $r$($a$ の $N$ を法とした位数)が求められれば、$r$ が偶数かつ $a^{r/2}\not\equiv -1\pmod N$ である確率が十分高く、そのとき $\gcd(a^{r/2}\pm 1, N)$ を計算すれば $N$ の非自明な因数が得られる。ここまでは古典計算。
2. 量子帰着(位数発見 → 位相推定):モジュラー乗算ユニタリ

$$U_a\ket x = \ket{ax\bmod N}$$

の固有値は $e^{2\pi i s/r}$($s=0,1,\ldots,r-1$)の形をしている。したがって $U_a$ の位相推定で $s/r$ を精度良く求めれば、連分数展開で $r$ が復元できる。3. 核心(位相推定 → QFT):位相推定の最終段は QFT。古典 FFT が $O(N\log N)$ なのに対し、QFT は $O(\log^2 N)$ ゲート — 指数的に速い。

補遺:$U_a$ の固有構造を精密に見る

上の段階2「位数発見 → 位相推定」を支える代数構造を詳しく調べる。以下 $\gcd(a,N)=1$ とする(そうでなければ $\gcd$ 自体が因数を与えるので量子計算は不要)。

$U_a$ のユニタリ性

$$U_a\ket x=\ket{ax\bmod N}$$

は計算基底を計算基底に写す置換型の演算子である。$\gcd(a,N)=1$ ならば $a$ は $\bmod\,N$ で乗法逆元 $a^{-1}$ を持ち、写像 $x\mapsto ax\bmod N$ は $\mathbb Z/N\mathbb Z$ 上の全単射になる。基底を基底に写す全単射は置換行列であり、置換行列はユニタリである。もし $\gcd(a,N)>1$ なら写像は単射でなくなり($ax\equiv ax'$ が $x\neq x'$ で起こる)、$U_a$ はユニタリにならない——量子回路としてそもそも実装できない。ユニタリ性は「可逆な古典計算の埋め込み」の量子力学的な表現であり、$\gcd(a,N)=1$ という数論的条件と正確に対応している。

固有ベクトルの構成

位数を $r$($a^r\equiv 1\bmod N$)とすると、軌道 $\{1,a,a^2,\ldots,a^{r-1}\}$($\bmod\,N$)は $U_a$ で巡回的に置換される。この $r$ 次元不変部分空間の上で $U_a$ を対角化するのが

$$\ket{u_s} \equiv \frac{1}{\sqrt r}\sum_{k=0}^{r-1} e^{-2\pi i sk/r}\,\ket{a^k\bmod N},\qquad s=0,1,\ldots,r-1$$

である。実際、

$$U_a\ket{u_s} = \frac{1}{\sqrt r}\sum_{k=0}^{r-1}e^{-2\pi isk/r}\ket{a^{k+1}\bmod N} = e^{2\pi is/r}\,\frac{1}{\sqrt r}\sum_{k'=1}^{r}e^{-2\pi isk'/r}\ket{a^{k'}\bmod N} = e^{2\pi is/r}\ket{u_s}$$

となる($k'=k+1$ と置換した;最後の等号で $k'=r$ の項が $a^r\equiv 1$ により $k'=0$ の項と同一視できることを使った。$N=15,a=2,r=4$ で数値的にも全 $s$ について確認済み)。すなわち固有値は $e^{2\pi is/r}$、位相は $\varphi_s=s/r$ である。

ここで $s$ が整数であることは仮定ではなく帰結である点に注意したい。巡回置換を対角化する位相 $e^{i\theta}$ は、$r$ 回作用させると恒等に戻る($U_a^r\ket{a^k}=\ket{a^k}$)という周期性から $e^{ir\theta}=1$ を満たさねばならず、$\theta=2\pi s/r$($s\in\mathbb Z$)に離散化される。有限次元の巡回構造が位相を量子化するのであって、連続な $s$ を許すには無限次元が必要になる。

固有ベクトルを用意できない問題とその解決

位相推定には固有ベクトル $\ket{u_s}$ が必要だが、$\ket{u_s}$ を書き下すには $r$ を知らねばならず、$r$ こそが求めたい未知量である——一見循環している。これを破るのが恒等式

$$\frac{1}{\sqrt r}\sum_{s=0}^{r-1}\ket{u_s} = \ket 1$$

である(幾何級数 $\sum_s e^{-2\pi isk/r}=r\delta_{k0}$ による;数値確認済み)。準備が自明な状態 $\ket 1$ が、全固有ベクトルの一様な重ね合わせになっている。$\ket 1$ を入れて位相推定を走らせると、線形性により「各 $\ket{u_s}$ に対する位相推定の重ね合わせ」が走り、測定するとランダムな $s$ に対する $\varphi_s = s/r$ の近似値が得られる。

連分数展開による $r$ の復元

位相推定の出力は $m/2^t \approx s/r$ という有理近似である($t$ は補助レジスタのビット数)。$t$ を十分大きく($t\ge 2\log_2 N+1$ 程度)取れば、$s/r$ は $m/2^t$ の連分数展開の近似分数(convergent)として一意に復元できる(分母 $\le N$ の有理数は互いに $1/N^2$ 以上離れているため)。$\gcd(s,r)=1$ となる $s$ を引き当てれば分母がそのまま $r$ を与え、そうでなくても数回の繰り返しで $r$ が得られる。ここまで来れば段階1の古典後処理 $\gcd(a^{r/2}\pm1,N)$ に接続して因数分解が完了する。