巨大な整数を二つの素数に分解する「素因数分解」。現在のコンピュータでは途方もない時間がかかるこの難問が、私たちが日々使う暗号技術の安全性を支えています。しかし量子コンピュータは、その前提を覆す可能性があります。1994年に発表された「ショアのアルゴリズム」は、なぜ世界に衝撃を与えたのでしょうか。『 量子革命 量子コンピュータからネット、ハード、AIまで ― すべてを変える新技術 』より抜粋します。
「素数と合成数を区別し、さらに合成数をその素因数へ分解する問題は、算術全体の中でもっとも重要かつ有用な問題の一つである。この有名で美しい問題の解決に役立つあらゆる手段は、熱意をもって追求されなければならない。」
1801年、偉大な数学者カール・フリードリッヒ・ガウスは、その著書『Disquisitiones Arithmeticae』の中で、このように書きました。しかし、素数にいったいどのような実用的価値があるのでしょうか。少なくともガウスの時代には、素数に実用的な用途は存在しませんでした。実際、私たち自身も学校で素数を学んだとき、それは現実の生活とは無関係な数学上の珍しい性質にすぎないと思っていました。素数とは、1と自分自身でしか割り切れない数のことです。したがって、2、3、5、7、11、13、17、23……などが素数です。言い換えれば、素数は1以外の二つの整数の積として表すことができません。
一見すると単なる数学的な遊びに見えるかもしれません。しかし時がたつにつれて、素数には非常に重要な秘密が隠されていることがわかってきました。そして今日、その秘密は現代社会に巨大な影響を与えています。
素因数分解の「難しさ」が現代社会を守っている
なぜでしょうか。その答えは、ある驚くべき性質にあります。二つの素数（p）と（q）を考えてみましょう。両者の積N＝p×qを計算することは簡単です。しかし、もし（p）と（q）を忘れてしまい、積（N）だけが残された場合、そこから元の素数（p）と（q）を見つけ出すことは極めて困難です。たとえば、97と109を掛ければ10573になります。これは簡単に計算できます。しかし、10573という数だけを与えられて、それが97と109の積であることを見抜くのは、それほど簡単ではありません。そして数が大きくなるほど、この難易度は急激に増していきます。
ここに問題の本質があります。数の桁数が増えるほど（あるいはそれを表現するために必要なビット数が増えるほど）、その数を素因数分解する作業は飛躍的に難しくなるのです。実際、現在知られている大きな整数を素因数分解するための最良のアルゴリズムであっても、必要な演算回数（あるいは論理ゲートの数）は、その整数の桁数に対して指数関数的に増加します。
これは、チェス盤と麦粒の逸話によく似ています。最初は単純に見える問題が、あっという間に手に負えないほど巨大になるのです。15の素因数が3と5であることを見つけるのは子供でもできます。しかし、250桁の整数（829ビット）の素因数分解が成功したのは2020年になってからであり、そのためには多数のプロセッサを備えたスーパーコンピュータを必要としました。その計算量は、現在の最先端技術による単一プロセッサで換算すると2700年間動かし続けるのに相当します。もし300桁の数を素因数分解しようとすれば、現在の技術では百万年以上かかると見積もられています。事実上、それは人類全体の計算能力をもってしても不可能な問題なのです。
機密情報を安全に送るための暗号技術は、まさにこの「巨大整数の素因数分解が極めて難しい」という性質の上に成り立っています。これは、軍事機密や外交文書だけの話ではありません。インターネット時代の現代では、暗号技術は私たちの日常生活の中心にあります。オンラインショッピングをするときも、旅行を予約するときも、個人的なメッセージを送るときも、私たちは知らず知らずのうちに暗号技術に守られているのです。
私たちは誰も、自分のクレジットカード情報が犯罪組織の手に渡ったり、個人情報が漏洩したりすることを望みません。そのため、コンピュータはメッセージを暗号化し、途中で盗み見られても読めない形に変換します。そして、そのメッセージが正しい相手に届いたときだけ、復号されて再び理解可能な内容になります。この暗号化と復号の仕組みは、現在では主要な通信プロトコルやオペレーティングシステムの奥深くに組み込まれています。その安全性は、「巨大整数の素因数分解が現実的には不可能である」という事実によって支えられているのです。たとえ最新鋭のコンピュータを用いたとしても、解読には非現実的なほどの長い時間がかかってしまいます。
量子コンピュータが暗号の前提を覆す
では、これらのことと量子力学、あるいは量子コンピュータにはどのような関係があるのでしょうか。量子コンピュータが量子系のシミュレーションに役立つことは直感的に理解できます。しかし、一見すると量子力学とは関係のなさそうな素因数分解問題を、なぜ量子コンピュータが古典コンピュータより圧倒的に効率よく解けるのかは、それほど自明ではありません。リチャード・ファインマンが量子コンピュータを提案してから長い間、それは魅力的ではあるものの、単なる理論的アイデアにすぎないと思われていました。しかし1994年、その状況は劇的に変わります。数学者ピーター・ショアが、整数の素因数分解を効率的に行う量子アルゴリズムを発表したのです。
ショアのアルゴリズムは、量子コンピュータ上で実行可能であり、古典コンピュータには対処できない大きな整数の素因数を、極めて効率的に見つけ出すことができます。この発見によって、量子コンピュータに対する認識は一変しました。そして2022年、ショアはチャールズ・ベネット、ジル・ブラッサール、デイヴィッド・ドイッチュらとともに、量子情報科学への貢献に対して基礎物理学ブレイクスルー賞を受賞しています。
ショアのアルゴリズムの詳細をここで説明する必要はありませんが、その基本的な考え方は次のようなものです。ショアは、素因数分解問題を「周期関数の周期（r）を見つける問題」に変換しました。周期関数とは、ある間隔（r）ごとに同じ値を繰り返す関数です。このアルゴリズムの効率性は、量子並列性を利用して、その関数を大量の入力値に対して同時に評価できる点にあります。そして最大の工夫は、それらすべての並列計算の結果をうまく組み合わせることによって、最終的に量子ビットを測定したときに、その関数の周期が得られるようにした点にあります。周期がわかれば、その後は普通の古典コンピュータを使って素因数分解を高速に行えることが示されています。
ショアのアルゴリズムは非常に強力で、数千量子ビット規模の量子コンピュータが実現すれば、現在使われている暗号方式を破れる可能性があります。もちろん、現時点ではその段階には達していません。研究室で成功しているのは、まだ小さな数の素因数分解に限られています。しかし量子技術の急速な進歩を考えれば、そう遠くない未来に、現在の暗号体系が本当に危機にさらされる可能性があります。もっとも、幸いなことに、量子力学そのものが解決策も提供してくれます。後で見るように、量子力学は機密情報を伝送するための、別の本質的に安全な方法を提供しているのです。まるで量子力学自身が、私たちの安全を脅かすと同時に、その安全を守る鍵も与えてくれているかのようです。
桁外れの計算能力を持つコンピュータ、盗聴を検知する通信、超高精度センサー。夢のような革命を「量子技術」が実現します。科学の最前線を、誰もが理解できる言葉で描いた一冊。
ジュリアーノ・ベネンティ（著）、ジュリオ・カサティ（著）、シモーネ・モンタンジェロ（著）、森弘之（訳）／日経BP／2750円（税込み）