量子コンピュータ入門 #6：ショアのアルゴリズムと量子フーリエ変換

量子コンピュータが世界的に注目されるきっかけとなったのが、1994年にピーター・ショアが発表した素因数分解アルゴリズムです。 今回は、このアルゴリズムがどのようにして「古典コンピュータで宇宙の年齢以上かかる計算」を数時間で終わらせるのか、その数学的トリックを解明します。

1. ターゲット：RSA暗号

現代のインターネット通信（HTTPS）の安全性を支えているのが RSA暗号 です。

RSAの安全性

RSAの安全性は、「巨大な整数 $N$ を素因数分解する（$N = p \times q$ となる素数 $p, q$ を見つける）のは極めて困難」という仮定に基づいています。

• 公開鍵：$N$
• 秘密鍵：$p$ と $q$ から計算される値

もし $N$ を高速に分解できれば、秘密鍵が復元され、暗号は解読されてしまいます。

2. アルゴリズムの構造：問題を変換する

ショアのアルゴリズムの核心は、素因数分解を 位数発見問題（Order Finding Problem） に変換することにあります。

ステップ1：古典的な前処理

素因数分解したい整数を $N$ とします。 ランダムに $1 < a < N$ なる整数 $a$ を選びます（ただし $\gcd(a, N) = 1$）。

このとき、 $a^r \equiv 1 \pmod N$ を満たす最小の正の整数 $r$ を 位数（周期） と呼びます。

なぜ位数が重要か？

もし偶数の位数 $r$ が見つかれば、 $a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod N$ となります。これは、$a^{r/2} \pm 1$ が $N$ と共通因数を持つ可能性が高いことを意味します。 実際、$\gcd(a^{r/2} \pm 1, N)$ を計算（ユークリッドの互除法で高速に可能）することで、$N$ の素因数 $p, q$ が求まります。

つまり、「$f(x) = a^x \mod N$ の周期 $r$ を見つける」 ことができれば、素因数分解は解けたも同然なのです。

3. 量子フーリエ変換（QFT）

この「周期 $r$」を見つける部分を、量子コンピュータが担います。 ここで使われる道具が 量子フーリエ変換（Quantum Fourier Transform: QFT） です。

定義

基底状態 $|j\rangle$ ($j=0, \dots, M-1$) に対するQFTは以下のユニタリ変換として定義されます。

$QFT|j\rangle = \frac{1}{\sqrt{M}} \sum_{k=0}^{M-1} \omega^{jk} |k\rangle$

ここで $\omega = e^{2\pi i / M}$ は1の原始 $M$ 乗根です。 これを行列で書くと、ヴァンデルモンド行列になります。

$F = \frac{1}{\sqrt{M}} \begin{pmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{M-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(M-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{M-1} & \omega^{2(M-1)} & \cdots & \omega^{(M-1)^2} \end{pmatrix}$

周期の抽出

古典的な離散フーリエ変換（DFT）と同様、QFTも「信号に含まれる周波数成分（周期性）」を抽出します。 違いは計算速度です。

• 高速フーリエ変換（FFT）：$O(M \log M) = O(2^n \cdot n)$
• 量子フーリエ変換（QFT）：$O((\log M)^2) = O(n^2)$

データ数 $M=2^n$ に対して、指数関数的な高速化 が実現されています。

4. ショアのアルゴリズムの全貌

量子回路の流れ

1. 重ね合わせの準備: 第1レジスタを全状態の重ね合わせにする。 $|\psi_0\rangle = \frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle |0\rangle$

2. モジュロ指数演算（オラクル）: 関数 $f(x) = a^x \mod N$ を計算し、第2レジスタに格納（エンタングルさせる）。 $|\psi_1\rangle = \frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle |a^x \mod N\rangle$

3. 第2レジスタの測定: 測定値 $y = a^l \mod N$ を得たとします。すると第1レジスタは、$a^x \equiv y$ となるような $x$ だけの重ね合わせになります。これらは周期 $r$ で並んでいます。 $|\psi_2\rangle \propto \sum_{k} |l + kr\rangle$ ※ 実際には測定しなくても、第1レジスタの密度行列は周期的混合状態になります。

4. 逆QFTの適用: 第1レジスタに $QFT^\dagger$ を適用します。 周期的な状態（くし型関数）をフーリエ変換すると、逆数（周波数）にピークを持つ状態になります。 つまり、$\frac{k}{r}$ に相当する状態が高い確率で観測されます。

5. 連分数展開: 測定結果から、連分数展開という古典的な数学手法を用いて、周期 $r$ を推定します。

5. 実用化への最大の壁：エラー訂正

理論上は完璧なショアのアルゴリズムですが、実際にRSA-2048（2048ビットの整数）を分解するには、まだ長い道のりがあります。

論理量子ビット vs 物理量子ビット

現在の量子コンピュータ（NISQ）はエラーが多すぎます。 ショアのアルゴリズムのように深い（ステップ数の多い）回路を実行するには、エラーを訂正しながら計算する必要があります。

• 物理量子ビット: 実際のハードウェア上の素子（エラー率が高い）。
• 論理量子ビット: 多数の物理量子ビットを組み合わせて、エラーを訂正した理想的な1ビット。

RSA-2048を分解するには、約 4,000個の論理量子ビット が必要と見積もられています。 これを実現するには、現在の技術レベル（エラー率）では、数百万〜数千万個の物理量子ビット が必要です。 （現在の最先端は数百〜1000物理量子ビット程度）

まとめ：未来への展望

ショアのアルゴリズムは、量子コンピュータが特定の数学的問題に対して圧倒的なパワーを持つことを証明しました。 現在、世界中の研究者が「誤り耐性型汎用量子コンピュータ（FTQC）」の実現に向けて、ハードウェアのスケールアップとエラー訂正技術の開発にしのぎを削っています。

私たちが生きている間に、この技術が完成し、暗号技術のパラダイムシフトが起こる可能性は十分にあります。その時、この数式の意味を理解していることは、新しい時代を生きるための大きな力となるでしょう。

[完] 量子コンピューティング入門シリーズ

これにて全6回の入門シリーズは完結です。 さらに深く学びたい方は、線形代数の教科書を片手に、以下の専門書に挑戦してみてください。

参考資料

• IBM Quantum Roadmap: https://www.ibm.com/quantum/roadmap
• Google AI Quantum: https://quantumai.google/
• NIST Post-Quantum Cryptography: https://csrc.nist.gov/projects/post-quantum-cryptography
• 量子技術イノベーション戦略（内閣府）

更新履歴

ご注意: 本記事は2025年12月時点の情報に基づいています。最新情報は公式サイトをご確認ください。