この記事は Fujitsu Advent Calendar 2018 22日目の記事です。
この記事は素因数分解の現状をまとめた一連の記事の一つです。
(2020年06月07日変更：アニーリング計算編を作成したため、リンクを追加しました)
量子ゲート計算による素因数分解
量子計算とは、量子物理学によって説明される物理原理を用いた計算、もっと簡単に言うと、量子ビットを用いた計算のことです。通常の計算機（量子計算機との比べるために古典計算機と呼ぶことが多い）の記憶単位はビットと表され、0 と 1 という 2 種類の状態を記憶できます。これに対し量子ビットは 0 と 1 を同時に重ね合わせた状態を記憶することが可能です。このため、古典計算機では手に負えなかったような問題でも、量子計算機によって解くことができる可能性があります。反面、量子ビットを読み出した値は確率的（毎回同じとは限らない）であるため、量子計算機を読み出す値が高い確率で一致するような工夫が必要となります。このような工夫を量子アルゴリズムと呼びます。任意の量子アルゴリズムを実装可能な計算機を、特に、量子ゲート計算機、または量子ユニバーサル計算機と呼びます。以前は「量子計算＝量子ゲート計算」だったのですが、近年は必ずしもそうでないので、注意が必要です。本記事では、量子ゲート計算機を用いた素因数分解アルゴリズムと、その実験状況を紹介します。なお、筆者は量子計算の専門家ではないので、正確で詳細な技術内容については他記事を参照下さい 1。
1994 年に Shor が考案した素因数分解アルゴリズム (Shor アルゴリズム) は、合成数 $N$ を $N$ のサイズの多項式時間で分解できるため、注目を集めました。というのも、Shor アルゴリズムを量子計算機上に実現することで、巨大な合成数を素因数分解することが可能となり、RSA 暗号が容易に解読できてしまうからです。しかし現時点では、Shor アルゴリズムは大きな脅威にはなっていません。これは、量子ゲート計算機の実現が想像以上に困難であり、多量子ビット化が思うように進んでいないからです。以下では Shor アルゴリズムによる素因数分解の概要と、その実装状況について紹介します。
Shor アルゴリズムの概要
Shor アルゴリズムとは、量子ゲート計算機を用いた素因数分解アルゴリズムです。合成数 $N$ を分解するには、以下の手順を処理します。
- $N$ と互いに素な (2 以上の) 自然数 $a$ を生成する
- $\bmod{N}$ における $a$ の位数 $r$、つまり $a^r \equiv 1 \pmod{N}$ となる最小の自然数 $r$ を求める
- $r$ が奇数なら 1．からやり直す
- $\gcd(a^{r/2-1}-1,N)$ を計算し、出力値が $1, N$ 以外ならば終了、そうでなければ 1. からやり直す
上の処理のうち、2. 以外は古典計算機で簡単に処理できますので、Shor アルゴリズムの本質は 2. の処理です。残念ながら古典計算機はこの処理を効率的に計算することができません。そこで古典ゲート計算機の出番となります。量子ゲート計算による位数計算の具体的な方法は、本記事では扱いませんので、他記事を参照下さい。
Shor アルゴリズムによる素因数分解実験
Shor アルゴリズムを実装した素因数分解結果を以下にまとめます。
| 年 | 実装方法| 合成数 | サイズ | 使用量子ビット数 | 文献 | 備考 |
|:---:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
|2001年12月|核磁気共鳴|15|4|7|[VSB+01]|最初の素因数分解報告|
|2007年12月|光子|15|4|4|[LWL+07]| |
|2007年12月|光子|15|4|4|[LBY+07]| |
|2009年09月|光集積回路|15|4|5|[PMO'B09]||
|2012年08月|ジョセフソン素子|15|4|3|[LBC+12]| |
|2012年11月|光子|21|5|1+$\log{3}$|[MLL+12]| |
|2016年03月|イオントラップ|15|4|5|[NMM+16]| |
Shor アルゴリズムによる最初の実験報告は 2001 年であり、核磁気共鳴 (NMR)を用いた物理環境下で 4 ビットの合成数 $N = 15$ (4 ビット) の素因数分解に成功しました。
この実験では 7 量子ビットが必要でしたが、核磁気共鳴による多量子ビット化は困難だったため、以降は他の物理現象を利用した実験が同じ合成数 $N = 15$ に対して行われてきました。具体的には、光子、光集積回路、ジョセフソン素子、イオントラップの利用結果が報告されています。素因数分解できた合成数のサイズという観点での現時点での記録は、光子を用いた $N = 21$ の分解です。なお、Shor アルゴリズムを用いて合成数 $N$ を素因数分解するには、理論的には約 $2 \log{N}$ 量子ビットが必要であるのに対し、近年の実験報告では必要量子ビット数が削減傾向にあります。これは、$N=15$ に対する Shor アルゴリズムが最適化されたためであり、Shor アルゴリズム自体が改良されたわけではないことに注意が必要です。
備考
2010年代に入り、量子ゲート計算機の本格的な開発が進み、数十量子ビットを処理可能な量子ゲート計算機が実現されています。しかし同時に、多量子ビット化した際のノイズが無視できず、量子的な誤り訂正が想像以上に重要であることがわかってきました。従って、例えば50量子ビットが処理可能な量子ゲート計算機であっても、計算結果が保証されるような実行性のある量子ビット数はもっと小さくなることに注意が必要です。
まとめ
量子ゲート計算による素因数分解アルゴリズムとして、Shor アルゴリズムの概要と、その実験状況をまとめました。現時点ではまだ 5 ビット合成数しか素因数分解できていないため、Shor アルゴリズムがセキュリティに与える影響は小さいです。しかし、理論的な Shor アルゴリズムの優位性は保証されていますので、数千量子ビットが処理可能な量子ゲート計算機が実現された場合には、RSA の安全性は揺らぐことになります。Keep Factoring!