ショアの因数分解

今日は、量子コンピュータがいちばん世界を騒がせた理由に踏み込もう。まず問題から。2つの素数を掛け算するのと、掛け算の答えから元の2つの素数を当てるのと、どちらが大変かな。

その「片道は簡単、逆は困難」という性質の上に、いまのインターネットの安全が乗っている。RSA暗号という仕組みだ。ざっくり言えば、2つの大きな素数を掛けた数を公開して鍵にする。暗号を解くには元の2つの素数が要るけれど、それは掛け算の答えからは求められない――そういう賭けだね。
いま使われている鍵は2048ビット、10進数でおよそ617桁だ。世界中のコンピュータを総動員しても、素因数分解には宇宙の年齢を何度も超える時間がかかると見積もられている。

まったく別の作戦だ。1994年、ピーター・ショアが見つけたその作戦の第一歩は、意外にも量子力学とは無関係なんだ。数学者たちが昔から知っていた事実で、こういうもの。
「素因数分解は、あるくり返しの周期を求める問題に、書き換えることができる」

手を動かすのがいちばんだ。因数分解したい数を 15 にしよう。答えは知っているけれど、手順を確かめるためだ。
まず、15と共通の約数を持たない数を適当に選ぶ。7 にしよう。そして、7を1回、2回、3回……と掛けていって、そのたびに15で割った余りを書き出してごらん。

それが周期だ。ここでは4だね。余りは有限個しかないから、掛け続ければ必ずどこかで同じ値に戻ってきて、その先はずっとくり返しになる。
そして、ここからが数学の魔法だよ。周期が偶数のとき、その半分の回数――今回なら2回――掛けたところを見る。7を2回掛けた余りは4だったね。この4に1を足した数と、1を引いた数を作る。

種明かしをしよう。周期が4だったということは、7を4回掛けた余りが1ということだね。つまり「7を4回掛けた数 − 1」は15でちょうど割り切れる。
ここで、中学校で習う因数分解を使う。7を4回掛けた数を、7を2回掛けた数の2乗と見れば、
（7を2回掛けた数）² − 1 ＝（7を2回掛けた数 − 1）×（7を2回掛けた数 ＋ 1）
この左辺が15で割り切れるのだから、右辺も15で割り切れる。ところが右辺は2つの数の掛け算だ。15＝3×5 の3と5が、この2つの数に分かれて入っている可能性が高い。

そこは心配いらない。最大公約数にはユークリッドの互除法という2300年前からの高速な求め方があって、ふつうのコンピュータでも何百桁だろうと一瞬で計算できるんだ。では手順をまとめよう。
①因数分解したい数 N と共通の約数を持たない数 a を、適当に選ぶ
②a を1回、2回、3回…と掛けた余りの列の周期 r を求める
③r が偶数なら、a を r の半分だけ掛けた余りの、±1 と N の最大公約数を取る
これで N の因数が出る。運が悪いと（r が奇数だったり、うまくいかない場合が）あるが、a を選び直せばよくて、たいてい数回で成功する。
――さて、この手順の中で、ふつうのコンピュータにとって絶望的に重いのはどこかな。

そこが唯一の関門で、そこだけを量子コンピュータが担当する。ショアのアルゴリズムとは、正確には「周期を高速に見つける方法」なんだ。前後の手順はふつうのコンピュータの仕事だよ。
では、量子コンピュータはどうやって周期を見つけるのか。第一歩は、もう見慣れた形だ。

その通り。だから最後にひと工夫が要る。ここでも答えは同じだ――干渉だよ。
周期を読み取る干渉のさせ方を、身近なものでたとえよう。ブランコを押すときのことを考えてごらん。ブランコにはそれ自身の揺れる速さがある。それにぴったり合ったタイミングで押し続ければ、押した力が積み重なってどんどん大きく揺れる。合っていないタイミングで押すと、押す力どうしが打ち消し合って、大きくならない。

自分で組み立てたね。その操作には名前があって、量子フーリエ変換という。「くり返し模様を、その周期の情報に変える装置」だ。アダマールを何本もの量子ビットにまたがって仕掛けたようなもので、大量の回転を一気にやってのける。
ここが決定的なところだよ。ふつうのコンピュータで同じことをすると、候補の数だけ計算が要る。量子コンピュータでは、量子ビットの本数の2乗くらいの手間で済んでしまう。候補の個数ではなく、桁数の2乗だ。この差が、指数の壁を越えさせる。

それがこの旅を通じての、いちばん大事な教訓だよ。量子コンピュータが指数的に速くなるのは、問題の中に隠れた構造があって、その構造と共鳴する干渉を設計できたときだけ。どんな問題にも効く万能薬ではない。
いま、そういう指数加速が知られている問題は、実はそれほど多くない。因数分解や離散対数といった数論の問題、そして――こちらが本命かもしれないが――分子や材料の量子的なふるまいのシミュレーションだ。量子の世界を量子で真似るのだから、相性がいいのは当然だね。新しい薬や、より良い電池・触媒の設計に効くと期待されている。

まだ破られていない。実機でショアのアルゴリズムが本当に実行できたのは、15や21といったおもちゃのような数までだ。距離はまだ遠い。
2048ビットのRSAを破るには、誤りなく動く量子ビット――物理の部品を束ねて誤りを消した「正味」の量子ビットで、論理量子ビットと呼ぶ――が数千個必要だと見積もられている。ゲートを掛ける回数で言えば、何十億回という規模だ。ところが、いまの実機にあるのは誤りだらけの物理量子ビットが数百から千個ほど。しかも、論理量子ビット1個を作るのに、物理量子ビットが千個から数千個要る。掛け合わせると、必要な物理量子ビットは百万個規模だ。
なぜそんなに要るのか――その答えが、この旅の最後のステージになる。

よく気づいたね。その脅威には名前がついていて、「いま集めて、あとで解読する」と呼ばれている。だから世界は、量子コンピュータの完成を待たずに動いている。
解決策は、量子コンピュータでも速く解けないと考えられている別の数学問題に、暗号を乗せ替えることだ。これを耐量子計算機暗号という。アメリカの標準化機関NISTが公募と審査を重ねて、2024年に最初の標準規格を正式に発表した。格子（たくさんの点が規則正しく並んだ構造）にまつわる問題などが土台になっている。乗せ替えはもう始まっているんだ。