はじめに
RSA暗号は、巨大な整数の素因数分解の困難性を安全性の根拠とする公開鍵暗号方式です。特にRSA-2048は、2048ビット長の合成数（10進数で約600桁）を利用しており、現代のスーパーコンピューターをもってしても、既存の素因数分解アルゴリズムでは現実的な時間内での分解は困難です。しかし、もし非常に大規模な量子コンピューターが実現すれば、素因数分解は古典コンピューターと比較して飛躍的に高速化されると予想されています。
では、RSA-2048を解読するためには、どの程度の規模の量子コンピューターが必要になるのでしょうか？
2019年、GidneyとEkeråは、誤り率0.1%以下の2000万量子ビットを持つ量子コンピューターがあれば、RSA-2048を8時間で解読できるという推定を発表しました[1]。この件に関する日本語の解説は、以下の記事にまとめられています。
近年、量子コンピューターの進展は目覚ましく、特に素因数分解計算に必要な量子誤り訂正や誤り耐性量子計算(FTQC)は急速に発展しています。そのため、現在でも2000万量子ビットが必要なのかどうかについては疑問の声もあり、Gidney自身も同様の質問をよく受けているようです。
そして、2025年5月、新たな論文が発表されました。
今回の論文では、計算時間をある程度犠牲にする代わりに、より少ない量子ビット数で2048ビットの整数を素因数分解することを目指しています。その結果、ハードウェアの誤り率や動作速度などの条件が同じであれば、100万量子ビット未満で、1週間以内にRSA-2048を解読できるという推定が示されました。
なお、この論文で仮定しているハードウェアのスペックは以下の通りです。
- ハードウェア構成
- 量子ビットの配置は正方格子状：Googleが開発している超伝導方式のハードウェアと同等
- 量子ゲートのエラー率は0.1%：Googleが2024年に報告した超伝導方式のハードウェアのエラーレートは0.157%[2]であり、それよりもエラーが少ない
- 表面符号のサイクル時間は1μs、制御システムの反応時間は10μs：超伝導方式のハードウェアの時間として現実的
構成
この記事では、まず量子コンピューターでの素因数分解に馴染みのない読者に向けて、その概要を説明します。量子コンピューターに詳しい方には、既知の内容も含まれるかもしれません。
次に、量子コンピューターに興味のある読者向けに、この論文で使用された技術について簡単に解説します。これらの個別技術は詳細にまでは踏み込みませんが、元論文を文献として引用しているので、参照したり、AIを用いて深掘りしていただければと思います。この記事の目的には、読者の興味を深め、AIと共に参考文献を探すためのガイドとして活用することも含まれています。
最後に、量子コンピューターの今後の展望について、私自身の考えを述べたいと思います。
量子コンピューターでの素因数分解
通常のコンピューターでの素因数分解アルゴリズム
通常のコンピューターでは、巨大な整数を素因数分解する計算時間は、桁数の増加に伴い指数関数的に増大します。そこで、まず現状最も高速とされる古典的アルゴリズムの概要と限界を確認し、その上で量子コンピューターがどのようにこの問題を解決しようとしているのかを解説します。
試し割り法
最も単純な方法は試し割り法で、対象となる合成数
一般数体篩法（GNFS）
一般数体篩法（GNFS）は、現在の通常のコンピューター上での大規模整数の素因数分解において最速とされる手法であり、以下の準指数関数の計算量を持っています[3]。
GNFSによって、NTTなどの研究チームは、2010年に768ビット(232桁)の素因数分解に成功しました[4]。しかし、2048ビットの素因数分解は、現在のスーパーコンピューターを用いても現実的な時間内には計算できません。
量子コンピューターを用いた素因数分解アルゴリズム
量子コンピューターによる素因数分解アルゴリズムは、通常、Shorのアルゴリズムを指します[5]。Shorのアルゴリズムは、素因数分解問題を関数
物理量子ビットと論理量子ビット
量子ビットとは、通常のコンピューターのビットにあたる、量子コンピューターの情報の基本単位です。
量子ビットの数は、ハードウェアの構成により決められています。各ハードウェアベンダーや量子コンピューターの実装方式ごとに量子ビット数は大きく異なりますが、この論文の著者が所属しているGoogleは、2024年に超伝導を用いた105量子ビットの量子コンピューターチップを発表しています[6]。
量子コンピューターは、ミクロな物理現象を用いて情報の保持や計算を行うため、微弱な熱などのノイズの影響を受けやすく、計算結果に誤りが発生します。そこで、多数の量子ビットを用いて誤り訂正符号を構成することで、誤りの影響を受けずに情報の保持や計算を行うことが出来ます。このような量子計算の方式を誤り耐性量子計算（FTQC）と呼びます。また、このとき、ハードウェア上の実際の量子ビットのことを物理量子ビットと呼び、多数の物理量子ビットを束ねて作った、誤りの影響を受けない理想的な量子ビットのことを論理量子ビットと呼びます。そのため、たとえ計算に必要な論理量子ビットは少数であっても、複雑な計算を行う必要がある場合、ハードウェアに必要な物理量子ビットは膨大になります。
この論文で示したこと
この論文では、RSA-2048を解読するために必要な量子ビット数の推定値を示しました。
著者らは2019年に、エラー率が0.1%、物理量子ビット数が2000万の量子コンピューターがあれば、RSA-2048が8時間で解けるという推定値を示しました。
今回の論文では、問題分割などを行い、実行時間は犠牲にしながらも必要な物理量子ビット数を減らしたアルゴリズムを用いたとき、エラー率は前回と同じ0.1%を仮定すると、100万物理量子ビットの量子コンピューターがあれば、RSA-2048が1週間以内(4.96日だが、余裕を持たせるためにそのように見積もった)で解けるという推定値を示しました。
よくある質問
Q: 楕円曲線暗号やAES暗号など、RSA以外の暗号は量子コンピューターで解けますか？
A: RSA暗号の他に、楕円曲線暗号もShorのアルゴリズムによって効率的に解読できることが知られています[7]。一方、AES暗号については、従来のコンピューターと比較して効率的に解く方法は見つかっていません[8]。
Q: 量子コンピューターによってRSA暗号や楕円曲線暗号が解読されるようになると、公開鍵暗号方式は成り立たなくなるのでしょうか？
A: 現在、量子コンピューターでも効率的に解読できない新しい公開鍵暗号の研究開発が進められており、標準化のプロセスが進んでいます。これらは耐量子計算機暗号(PQC: Post-Quantum Cryptography)と呼ばれています。
NTTデータでは、サイバーセキュリティに特化したチームがPQC移行に向けたコンサルティングサービスを提供しています。
Q: 耐量子計算機暗号(PQC)と量子暗号は同じものですか？
A: いいえ、耐量子計算機暗号(PQC)と量子暗号は全く異なるものです。
PQCは、通常のコンピューターで動作し、量子コンピューターを使用しても解読が困難であると考えられる暗号化アルゴリズムを用いた公開鍵暗号です。現在、標準化のプロセスが進められており、今後は公開鍵暗号はRSA暗号や楕円曲線暗号からPQCに置き換えられていくと考えられます。
量子暗号は、特殊な装置を利用し、光子などの量子を用いて情報通信を行うことで、量子が複製できないという性質を利用して盗聴を不可能にする暗号技術です。現在の技術動向としては、量子暗号は研究開発段階にあり、専用の装置が必要となるため、一般的な用途での実用化にはまだ時間がかかると考えられています。
arXiv:2505.15917 で用いられた技術
ここからは、量子コンピューターに詳しい人に向けて、この論文で言及されている技術をいくつか紹介したいと思います。
近似剰余演算 (2.1 Approximate Residue Arithmetic)[9]
通常、2048ビットの素因数分解を行うためには、2048ビットの算術演算が必要となり、2048論理量子ビットの量子レジスタが必要となります。しかし、中国剰余定理を用いて問題を分割することで、それよりも少ない1399論理量子ビットでの計算を可能にしました。
ただし、問題を分割すると、トータルで必要となる計算時間は増大します。
また、問題を分割した後の乗算を、中国剰余定理の係数を用いて加算に変換し、さらに、加算の下位ビットは寄与が小さいため、切り捨てて近似します。
近似周期発見 (2.2 Approximate Period Finding)
通常は、演算を行った後、量子フーリエ逆変換を行うことで、周期を見つけることができます。
しかし、量子フーリエ逆変換で周期を発見するには、演算結果が誤差なく正確であることが必要です。上述のように近似計算を行った場合、量子フーリエ逆変換による周期発見は行えません。
近似した下位ビットを単純に捨ててしまうこともできますが、その場合は精度や計算速度の面で問題が発生します。
そこで、Superposition masking[10]と呼ばれる手法で下位ビットを隠すことで、これらの問題を回避できます。
Ekerå-Håstad の周期発見アルゴリズム (2.3 Ekerå-Håstad Period Finding)[11]
発見したい周期が、群全体の位数(この場合は
算術演算の最適化 (3.4 Arithmetic Optimizations)
その他、様々な算術演算を高速にする工夫を行っています。
- 乗算の加算への置き換え：事前計算により、モジュラー乗算をモジュラー加算に置き換えられる
- Windowing[12]：量子ビットを1つずつ処理するのではなく、複数のウィンドウ単位で処理できる
- 繰り返しでの計算の統合：量子計算には、計算の終わりに逆計算過程が入るが、類似の繰り返し計算を行うときは、その差分を計算することで統合できる
- 位相補正の遅延と統合：測定で補助量子ビットを消去した際、測定結果に応じて位相の補正が必要となるが、その処理を後回しにして、他の補正操作とまとめることで、処理の回数が減る
- モジュラー加算回路の改良：オーバーフロー検出を簡単にしている
空間効率のいい量子誤り訂正符号
量子誤り訂正に用いられるSurface Codeは、論理量子ビットを作るために膨大な数の物理量子ビットを必要とします。Yoked Surface Codes[13]は、通常のSurface Codeで作った論理量子ビットを用いて、より空間効率のいい量子パリティチェック符号を作ることで、論理量子ビットを作るために必要な物理量子ビットの数を削減しています。Yoked Surface Codesは通常のSurface Codeを実装する場合と同じハードウェア構成で実装でき、また、エラーレートが0.1%のときに物理量子ビット当たりの論理量子ビット数は通常のSurface Codeの約3倍になると元論文で主張されています。一方で、操作性は通常のSurface Codeよりも悪くなるため、あまり操作を行う必要のない量子ビット（cold storage）のために用いられます。
魔法状態栽培[14]
TゲートやToffoliゲートなどのNon-Cliffordゲートのためには、魔法状態が必要となり、その作成のために魔法状態蒸留（Magic State Distillation）という、たくさんの量子ビットとステップ数を要する操作が必要でした。魔法状態栽培（Magic State Cultivation）は、それを大幅に削減する手法です。
おわりに
量子コンピューターがハードウェアだけでなくソフトウェア面でも進展していることが非常によくわかる、とてもエキサイティングな論文でした。
また、この論文を通じて以下のようなことを改めて感じました。
- 量子コンピューターは通常のコンピューターを置き換えるのではなく、共存する：従来のShorのアルゴリズムと比べて、前計算や分割など、通常のコンピューターの役割がより増しています。今後も、量子コンピューターは、通常のコンピューターを置き換えるのではなく、特に通常のコンピューターで計算が難しい部分を担うという役割になっていくでしょう。
- 量子版ムーアの法則が続くと信じるなら、意外と素因数分解が解ける日は近いかもしれない：これまで、量子コンピューターでの素因数分解は夢のまた夢、という考えもあったかと思います。一方で、ハードウェアはまるでムーアの法則のように量子ビット数が増加してきており、ソフトウェア面でも、最新の知見を元に構成すると、量子ビット数の大幅な削減が行えました。この傾向が今後も続くと考えられるなら、素因数分解が量子コンピューターで解ける日は思ったよりも近いかもしれません。
- ソフトウェア面でも泥臭い工夫が必要：量子コンピューターは非常に強力ですが、とはいえ、富豪的プログラミングのように量子ビットや量子ゲート操作を湯水のように行えるほどの巨大な量子コンピューターは存在しません。この論文のように、様々な技術を寄せ集めて、泥臭い工夫を行った者が、最初の量子コンピューターの実用的なアプリケーションを開発することになるのではないでしょうか。
NTT DATA公式アカウントです。 技術を愛するNTT DATAの技術者が、気軽に楽しく発信していきます。 当社のサービスなどについてのお問い合わせは、 お問い合わせフォーム nttdata.com/jp/ja/contact-us/ へお願いします。
Discussion
古典コンピュータと量子コンピュータの役割分担が進めば進むほど、古典コンピュータの新しいアルゴリズムを開発するためのヒントになってそうだなと感じました。