Alice & Bob、約2万3000個のキャット量子ビットでRSA-2048を解読可能とする新たな試算

パリとボストンに拠点を置き、キャット量子ビット（cat qubit）による量子コンピューターを開発する Alice & Bob は10月29日、自社のアーキテクチャで構築した誤り耐性マシンが、22,593個の物理量子ビットを使って3.14日で2048ビットのRSA鍵を素因数分解できるとするリソース見積もりを公表した。同社はこの結果を、現在の公開鍵暗号に対してShorのアルゴリズムを実行するのに必要な総量子リソース（量子ビット数×実行時間）の新たな最低記録だとしている。これはプレプリントとして公開された理論的な予測であり、ハードウェア上での実証ではない。

発表の内容

数値の出典は論文 "Shor's algorithm compiled on cat qubits: 22 593 qubits for RSA-2048 in 3.14 days" で、Alice & Bobの研究チームとInriaおよびレンヌ大学の共著者1名が、IACRのCryptology ePrint Archiveに投稿した。RSA-2048に加え、チームはBitcoinやEthereumの署名の数学的基盤である256ビット楕円曲線離散対数問題（ECDLP）が、最大29,588個の物理量子ビットで61.8分で解けると見積もった。さらに小規模なベンチマークとして、約6,700量子ビット・21分のFFDLP-512も提案している。

同社の発表によると、このRSAの数値は、Google Quantum AI のCraig Gidneyによる2025年の見積もりと比べて物理量子ビット数が40分の1である。Gidneyの見積もりは、表面符号マシン上でRSA-2048に100万個未満のノイズあり量子ビットと1週間未満の実行時間が必要だとしていた。

DesignQuantum ニュースレターを購読

量子コンピューティングのニュースと解説を無料でお届けします。すべての記述に出典リンク付き。毎日・毎週・毎月から選べます。

Website

メールアドレス 配信頻度毎日毎週毎月 言語EnglishEspañol简体中文हिन्दीالعربيةPortuguês (Brasil)FrançaisDeutsch日本語Русский한국어Bahasa IndonesiaTürkçeItalianoTiếng ViệtPolskiNederlandsไทยفارسیУкраїнськаবাংলাاردوKiswahiliBahasa Melayuעברית 無料で購読する

無料。いつでもワンクリックで配信停止できます。 プライバシーポリシー

技術的な詳細

著者らは論理量子ビット数に平均的なオーバーヘッドを掛けるのではなく、アルゴリズムで最もコストのかかる部分を個々の物理量子ビットの操作レベルまでコンパイルし、チップの完全なレイアウトとスケジュールを作成した。Alice & Bobは削減の要因として3点を挙げる。第一に、キャット量子ビットがハードウェア上でビット反転エラーを抑制するため、誤り訂正は位相反転エラーだけを扱えばよいこと。第二に、LDPC-cat符号で、同社によれば従来の繰り返し符号による手法と比べてRSA-2048に必要な量子ビット数を半分以下（49,649から22,593）に減らすこと。第三に、誤り訂正を待たずに一定のペースで動作するよう、キャット量子ビット向けに再設計した加算器である。アルゴリズム面では、GoogleとInriaの研究者による最近の成果を取り入れている。

前提条件は重要だ。論文は、誤り訂正サイクル1マイクロ秒、反応時間10マイクロ秒、位相エラー確率5 × 10⁻⁴、そしてビット反転がまったく起きないこと（ビット反転時間およそ100年に相当）を仮定している。ビット反転が1時間に1回程度起きる場合は追加の符号化層が必要となり、RSA-2048の見積もりは約45,000量子ビットに増える。この設計は空間と時間のトレードオフも可能で、約611,000量子ビットならRSAの実行は1.25時間に短縮され、約21,188量子ビットなら8.08日に延びる。

なぜ重要か

誤り訂正とアルゴリズム設計の進歩に伴い、Shorのアルゴリズムのリソース見積もりは下がり続けており、そのたびにセキュリティチームが計画に用いる時間軸が縮まっている。Alice & Bobは、ハードウェアの進歩と下がり続ける必要リソースが2030年代初頭に交わると予想しているが、大きな工学的課題が残っていることも認めている。PQShield の創業者兼CEOであるAli El Kaafaraniは声明の中で、政府や企業は「最も重要なところで直ちにPQCを導入する」べきだと述べた。

今後の注目点

主要な数値は、まだ大規模には実証されていない極めて長いビット反転時間を持つキャット量子ビットを前提としており、本当の試金石はハードウェアがその前提に向けてどこまで進歩するかだ。プレプリントの査読や、コンパイル上の選択に対する独立した検証も注目に値する。Alice & Bobは政府や業界の関係者に説明を行っているとし、米国と英国の指針がいずれも2035年までの移行完了を目標としていることに触れながら、組織に対して今すぐ耐量子計算機暗号への移行を始めるよう呼びかけている。