量子コンピューターはなぜ素因数分解が得意なのか？― ショアのアルゴリズムと「周期」の秘密をやさしく解説
量子コンピューターが実用化されると、現在のインターネットで利用されている暗号の一部が解読されてしまう、という話を聞いたことはないでしょうか。
特に有名なのが、RSA暗号です。
RSA暗号は、大きな数を素因数分解することの難しさを利用しています。
ところが、量子コンピューターには「ショアのアルゴリズム」という計算方法があり、これを利用すると素因数分解を効率よく行えることが数学的に証明されています。
では、量子コンピューターはどのようにして素因数を見つけるのでしょうか？
調べてみると、意外なことが分かりました。
量子コンピューターは、素因数を直接探すのではなく、数字の繰り返しパターン、つまり「周期」を探しているのです。
今回は、15という小さな数字を例にして、この不思議な仕組みを中学生でも理解できるように説明します。
1. そもそも素因数分解とは？
例えば、次の計算を考えます。
3 × 5 = 15
この計算は簡単です。
では逆に、「15はどんな素数の掛け算でできているでしょう？」と聞かれたらどうでしょうか。
答えは3と5です。
このように、ある整数を素数の掛け算に分解することを「素因数分解」といいます。
小さな数字なら簡単ですが、何百桁もある巨大な整数になると、素因数を見つけるのは非常に難しくなります。
RSA暗号は、この「掛け算は簡単なのに、逆の素因数分解は難しい」という性質を利用しています。
しかし、1994年にピーター・ショアという数学者が、量子コンピューターを使って素因数分解を効率よく行うアルゴリズムを発表しました。
それが「ショアのアルゴリズム」です。
2. ショアのアルゴリズムは「余り」に注目する
今回は15を素因数分解してみましょう。
まず、次の計算を行います。
2のx乗を15で割った余りを求める
文字で表すと、
f(x) = 2^x mod 15
となります。
「mod 15」は「15で割った余り」という意味です。
例えば、
- 2³ = 8 → 15で割った余りは8
- 2⁴ = 16 → 15で割った余りは1
- 2⁵ = 32 → 15で割った余りは2
です。
実際に表にしてみましょう。
| x | 2のx乗 | 15で割った余り |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 2 | 2 |
| 2 | 4 | 4 |
| 3 | 8 | 8 |
| 4 | 16 | 1 |
| 5 | 32 | 2 |
| 6 | 64 | 4 |
| 7 | 128 | 8 |
| 8 | 256 | 1 |
何か気づきませんか？
余りの部分を見ると、
1 → 2 → 4 → 8 → 1 → 2 → 4 → 8 → …
と繰り返されています。
つまり、4つ進むたびに同じパターンに戻っているのです。
この繰り返しの長さを「周期」と呼びます。
今回の周期は、
r = 4
です。
そして、この周期4を見つけることが、ショアのアルゴリズムの重要な仕事になります。
3. なぜ周期が分かると素因数が見つかるのか？
先ほど、2の4乗を15で割った余りが1になることが分かりました。
2⁴ = 16
16を15で割ると余りは1です。
したがって、16から1を引いた数は15で割り切れます。
2⁴ − 1 = 15
ここで中学校で学ぶ「平方差の公式」を利用します。
a² − b² = (a − b)(a + b)
これを当てはめると、
2⁴ − 1 = (2² − 1)(2² + 1)
となります。
計算してみましょう。
(4 − 1) × (4 + 1)
= 3 × 5
= 15
なんと、15の素因数である3と5が見つかりました。
この例では、周期4を求めたことで、素因数分解につなげることができたのです。
一般には、このあと「最大公約数」を計算して素因数を取り出します。また、選んだ数や周期によっては成功しないため、計算をやり直すこともあります。
では、肝心の周期4を、量子コンピューターはどのように発見するのでしょうか？
4. 量子コンピューターの出力は「3と5」ではない
ここからが今回の本題です。
実は、量子コンピューターが直接出力するのは、素因数の3と5ではありません。
周期を推定するための数値です。
例えば、測定用に8個の量子ビットを使うとします。
通常のコンピューターの1ビットは、0か1のどちらかを表します。
一方、量子ビットは0と1を重ね合わせた状態を作れます。
8個の量子ビットでは、
2⁸ = 256
通りの状態を扱えます。
つまり、0から255までの256通りです。
そして、量子フーリエ変換という処理を行ったあとに測定すると、今回の理想的な例では、次の4種類の数値が現れます。
0、64、128、192
不思議な数字ですね。
なぜ、これらの数字が出てくるのでしょうか？
5. 64、128、192が出てくる理由
今回のポイントは、次の2つの数字です。
- 量子ビットが扱う状態の数：256
- 探している周期：4
256を4で割ると、
256 ÷ 4 = 64
となります。
量子フーリエ変換を行うと、周期4に対応する情報が、64刻みの位置に現れます。
つまり、
- 0 × 64 = 0
- 1 × 64 = 64
- 2 × 64 = 128
- 3 × 64 = 192
ということです。
このように、量子コンピューターは周期の情報を、測定されやすい数値のパターンに変換しているのです。
もちろん、量子コンピューターが最初から周期4を知っているわけではありません。
周期が未知でも、量子計算によって作られた状態の規則性を、量子フーリエ変換が読み取れる形に変えるのです。
6. なぜ特定の数字だけが残るのか？ ― 波の不思議
ここで、量子コンピューターの重要な性質が登場します。
それが「波の干渉」です。
例えば、池に2つの石を投げ込んだ場面を想像してください。
それぞれの石から波紋が広がっていきます。
波が重なったときには、2つの現象が起こります。
① 波が強め合う
波の山と山が重なると、さらに大きな波になります。
② 波が打ち消し合う
波の山と谷が重なると、互いに弱め合います。
量子コンピューターでも、これと似た性質を利用できます。
量子状態には「確率振幅」と呼ばれる波のような性質があり、それらが強め合ったり、打ち消し合ったりします。
ただし、実際に水面の波が発生しているわけではありません。波のように計算できる数学的な性質を利用しています。
周期4の波を考えてみる
今回の例では、2の累乗を15で割った余りに、4つごとの繰り返しがありました。
量子フーリエ変換は、この繰り返しの規則性を「波の干渉」を利用して見つけ出します。
では、具体的にどのような計算が行われるのでしょうか。
まず、量子フーリエ変換では、数字の位置に応じて波の角度が変化します。
今回使用しているのは8量子ビットなので、扱える状態は0から255までの256通りです。
量子フーリエ変換では、測定候補を y、元の数字の位置を x とすると、波の角度は次の式で表せます。
波の角度 = 360° × (x × y) ÷ 256
ここで、測定候補が64の場合を考えてみましょう。
式の y に64を代入すると、
波の角度 = 360° × (x × 64) ÷ 256
となります。
64 ÷ 256 = 1/4 なので、
波の角度 = 90° × x
と計算できます。
つまり、元の数字 x が1つ増えるたびに、波の角度が90度ずれるということです。
実際に計算してみましょう。
| 元の数字 x | 波の角度 |
|---|---|
| 0 | 0度 |
| 1 | 90度 |
| 2 | 180度 |
| 3 | 270度 |
| 4 | 360度 |
| 5 | 450度 |
4つ進むと、波の角度は360度になります。
360度はちょうど1周なので、波は最初と同じ向きに戻ります。
ここで、先ほど見つけた周期4の規則性を思い出してください。
2の累乗を15で割った余りが1になるのは、
x = 0、4、8、12、16、…
という、4つずつ離れた位置でした。
測定候補64の場合、これらの位置に対応する波の角度は、
- x = 0 → 0度
- x = 4 → 360度
- x = 8 → 720度
- x = 12 → 1080度
となります。
どれも360度の整数倍なので、波はすべて同じ向きになります。
その結果、波同士が強め合い、測定候補64が観測されやすくなるのです。
では、ほかの測定候補ではどうなるのでしょうか。
同じ式で、数字が4つ進んだときの角度を計算すると、次のようになります。
| 測定候補 | 1つ進むごとの角度 | 4つ進んだときの角度 |
|---|---|---|
| 32 | 45度 | 180度 |
| 64 | 90度 | 360度 |
| 128 | 180度 | 720度 |
| 192 | 270度 | 1080度 |
測定候補128では720度、192では1080度になります。
どちらも360度の整数倍なので、4つ離れた位置の波は同じ向きになり、強め合います。
一方、測定候補32の場合は180度です。
180度は半周なので、4つ離れた位置の波は正反対の向きになります。
そのため、波同士が打ち消し合い、測定候補32は観測されなくなります。
なお、測定候補0では波の角度が変化しないため、こちらも波が強め合います。
このような仕組みによって、今回の理想的な計算では、
0、64、128、192
という4つの数値だけが測定結果として現れるのです。
ここで重要なのは、量子コンピューターが256通りの答えをすべて読み出しているわけではないということです。
元の計算結果に含まれる周期4という規則性と、量子フーリエ変換によって作られる波の周期が一致したとき、波は強め合います。
逆に、規則性が合わない波は打ち消し合います。
つまり量子コンピューターは、波の干渉という性質を利用して、元の数字の繰り返しパターンを、測定できる数値のパターンへと変換しているのです。
※実際の量子フーリエ変換では、波の角度を「位相」と呼びます。ここでは分かりやすく「波の角度」と表現しています。また、説明を簡単にするため、同じ計算結果に対応する位置の波を取り出した状態を考えています。
7. 量子フーリエ変換は「リズムを見つける装置」
量子フーリエ変換という名前は難しく聞こえますが、イメージとしては、音楽のリズムを分析する装置に似ています。
例えば、手拍子を
「タン、タン、タン、タン」
と一定の間隔で繰り返すとします。
その音のデータを分析すれば、一定のリズムがあることが分かります。
量子フーリエ変換も、量子状態に含まれる周期的な規則性を見つけるために利用されます。
数学的には、繰り返しのパターンを「周波数」という別の形で表現する処理です。
音楽のリズムを分析してテンポを見つけるように、量子状態の規則性を調べていると考えると、理解しやすいかもしれません。
8. 測定値から周期4を復元する
量子コンピューターが64を測定したとしましょう。
8量子ビットでは256通りの状態があるので、64を256で割ります。
64 ÷ 256 = 1/4
この分数の分母が4なので、周期4の候補が得られます。
同様に、
192 ÷ 256 = 3/4
でも、周期4の候補が得られます。
一方、
128 ÷ 256 = 1/2
では、分母が2になるため、周期4を直接特定できません。
また、0が出た場合も周期を推定する情報が不足しています。
| 測定結果 | 256で割った値 | 周期4を推定できる？ |
|---|---|---|
| 0 | 0 | できない |
| 64 | 1/4 | できる |
| 128 | 1/2 | この結果だけではできない |
| 192 | 3/4 | できる |
したがって、1回の量子計算で必ず周期が分かるわけではありません。
この例の理想的な回路では、4種類の測定結果がそれぞれ約25%の確率で現れるため、64または192を得られる確率は約50%です。
正しい周期が分からなければ、必要に応じて計算を繰り返します。
なお、巨大な数を扱う場合には、測定値から周期を求めるために「連分数展開」という数学的な方法も使います。
9. 実際にRSA暗号を解読できるのか？
では、現在の量子コンピューターでRSA暗号を簡単に解読できるのでしょうか？
答えは、まだできません。
2026年10月現在、一般的に利用されているRSA-2048のような暗号を実用的に解読できる量子コンピューターは実現していません。
今回の15という数字とは違い、実際の暗号では非常に大きな整数を扱う必要があります。
また、量子コンピューターは計算中にエラーが起こりやすいため、大規模な誤り訂正技術も必要です。
その一方で、将来の量子コンピューターに備えて「耐量子計算機暗号（PQC）」と呼ばれる新しい暗号技術の導入が進められています。
米国のNISTは、2024年に最初の3つの耐量子計算機暗号標準を正式に公開しています。
つまり、現在の暗号がすべて今すぐ危険というわけではありませんが、将来に向けた準備はすでに始まっているのです。
10. まとめ ― 量子コンピューターが得意なのは「規則性を利用する計算」
今回の内容を整理してみましょう。
- RSA暗号は、大きな整数の素因数分解が難しいことを利用している。
- ショアのアルゴリズムでは、素因数を直接探す代わりに、計算結果の周期を探す。
- 15を例にすると、2の累乗を15で割った余りには周期4の規則性がある。
- 量子フーリエ変換を使うと、この周期4の情報が0、64、128、192という測定結果に現れる。
- 得られた数値から周期を推定し、通常の計算で素因数3と5を取り出せる。
私が特に面白いと感じたのは、量子コンピューターが単に大量の計算を高速に処理しているのではなく、波の干渉を利用して問題の規則性を取り出しているという点です。
今までのコンピューターとは異なる考え方で問題を解いていることが、量子コンピューターの大きな特徴なのだと思います。
そして今回の「15」という小さな数字の例でも、量子計算の重要な仕組みを垣間見ることができました。