論文の概要: How to factor 2048 bit RSA integers with less than a million noisy qubits

• arxiv url: http://arxiv.org/abs/2505.15917v1
• Date: Wed, 21 May 2025 18:11:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-23 17:12:47.855053
• Title: How to factor 2048 bit RSA integers with less than a million noisy qubits
• Title（参考訳）: 100万量子ビット未満の2048ビットRSA整数の分解法
• Authors: Craig Gidney,
• Abstract要約: Gidney+Ekeraa 2019では、2048ビットRSAを2000万のノイズ量子ビットを持つ量子コンピュータで8時間で分解できるという推定を共同で発表しました。 2048ビットのRSA整数は、100万のノイズ量子ビット未満の量子コンピュータによって1週間以内に分解できると見積もっています。
• 参考スコア（独自算出の注目度）: 0.03922370499388702
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Planning the transition to quantum-safe cryptosystems requires understanding the cost of quantum attacks on vulnerable cryptosystems. In Gidney+Eker{\aa} 2019, I co-published an estimate stating that 2048 bit RSA integers could be factored in eight hours by a quantum computer with 20 million noisy qubits. In this paper, I substantially reduce the number of qubits required. I estimate that a 2048 bit RSA integer could be factored in less than a week by a quantum computer with less than a million noisy qubits. I make the same assumptions as in 2019: a square grid of qubits with nearest neighbor connections, a uniform gate error rate of $0.1\%$, a surface code cycle time of 1 microsecond, and a control system reaction time of $10$ microseconds. The qubit count reduction comes mainly from using approximate residue arithmetic (Chevignard+Fouque+Schrottenloher 2024), from storing idle logical qubits with yoked surface codes (Gidney+Newman+Brooks+Jones 2023), and from allocating less space to magic state distillation by using magic state cultivation (Gidney+Shutty+Jones 2024). The longer runtime is mainly due to performing more Toffoli gates and using fewer magic state factories compared to Gidney+Eker{\aa} 2019. That said, I reduce the Toffoli count by over 100x compared to Chevignard+Fouque+Schrottenloher 2024.
• Abstract（参考訳）: 量子セーフ暗号システムへの移行を計画するには、脆弱な暗号システムに対する量子攻撃のコストを理解する必要がある。 Gidney+Eker{\aa} 2019では、2048ビットRSA整数が2000万のノイズ量子ビットを持つ量子コンピュータによって8時間で分解できるという推定を共同で発表しました。 本稿では,必要な量子ビット数を大幅に削減する。 2048ビットのRSA整数は、100万のノイズ量子ビット未満の量子コンピュータによって1週間以内に分解できると見積もっています。 私は2019年と同じ仮定をしている: 近接する近接接続を持つ量子ビットの正方形グリッド、一様ゲートエラー率0.1\%$、1マイクロ秒の表面コードサイクル時間、制御システムの反応時間10$マイクロ秒。 量子ビットカウントの削減は、おもに近似剰余演算(Chevignard+Fouque+Schrottenloher 2024)、ヨードされた曲面符号を持つアイドル論理キュービットの保存(Gidney+Newman+Brooks+Jones 2023)、マジックステートの栽培(Gidney+Shutty+Jones 2024)などである。 より長いランタイムは、主に、Gidney+Eker{\aa} 2019と比較してToffoliゲートの数が増え、マジックステートファクトリが少なくなるためである。 とは言っても、2024年のChevignard+Fouque+Schrottenloherと比べて、Toffoliの数を100倍以上削減します。

関連論文リスト

• Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
  ウィンドウ演算は、空間時間トレードオフを伴う量子回路のコストを削減する手法である。 この作業では、ウィンドウ化されたモジュラー指数に4つの最適化を導入する。 これにより、暗号化アプリケーションに関連するモジュール型指数回路において、Toffoli数とToffoli深度が3%向上する。
  論文  参考訳（メタデータ） (2025-02-24T16:59:16Z)
• Quantum error correction below the surface code threshold [107.92016014248976]
  量子誤り訂正は、複数の物理量子ビットを論理量子ビットに結合することで、実用的な量子コンピューティングに到達するための経路を提供する。 本研究では, リアルタイムデコーダと統合された距離7符号と距離5符号の2つの面符号メモリを臨界閾値以下で動作させる。 以上の結果から,大規模なフォールトトレラント量子アルゴリズムの動作要件を実現する装置の性能が示唆された。
  論文  参考訳（メタデータ） (2024-08-24T23:08:50Z)
• SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
  クビットCSSコード間の手術を自動化するための,オープンソースの軽量PythonパッケージであるSSIP(Identifying Pushouts)による安全手術について述べる。 ボンネットの下では、鎖複体の圏における普遍構成によって支配される$mathbbF$上の線型代数を実行する。 高い符号距離を犠牲にすることなく,手術によって様々な論理的測定を安価に行うことができることを示す。
  論文  参考訳（メタデータ） (2024-07-12T16:50:01Z)
• A comment on "Factoring integers with sublinear resources on a superconducting quantum processor" [0.0]
  そこで我々はSchnorr's lattice-based integer factorizationアルゴリズムのオープンソース実装について述べる。 我々の実装は、シュノーラーの整数を70ビットまでしか持たないハイブリッド量子+古典版に対する主張された部分線型格子次元が示している。 我々は、我々の実装が、他のハイブリッド量子/古典的整数分解アルゴリズムのアイデアをテストするための、コミュニティの場として機能することを願っている。
  論文  参考訳（メタデータ） (2023-07-18T21:46:54Z)
• Performance Analysis of a Repetition Cat Code Architecture: Computing 256-bit Elliptic Curve Logarithm in 9 Hours with 126133 Cat Qubits [0.0]
  キャットキュービットは量子コンピューティングに魅力的なビルディングブロックを提供する。 反復符号のコストを定量化し,キャットキュービットを用いた大規模アーキテクチャの選択のための貴重なガイダンスを提供する。
  論文  参考訳（メタデータ） (2023-02-13T19:01:05Z)
• Factoring integers with sublinear resources on a superconducting quantum processor [11.96383198580683]
  Shorのアルゴリズムは、公開鍵暗号システムに基づく情報セキュリティに深刻な挑戦をしている。 広く使われているRSA-2048スキームを破るためには、数百万の物理量子ビットが必要である。 本稿では,古典的格子削減法と量子近似最適化アルゴリズムを組み合わせることで,整数分解のための普遍量子アルゴリズムについて報告する。
  論文  参考訳（メタデータ） (2022-12-23T14:45:02Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• SMYRF: Efficient Attention using Asymmetric Clustering [103.47647577048782]
  本稿では,注目度を近似する新しいタイプのバランスクラスタリングアルゴリズムを提案する。 SMYRFは、再トレーニングすることなく、高密度の注意層をドロップインで置き換えることができる。 SMYRFは,訓練前後の集中的注意と相互に使用できることが示唆された。
  論文  参考訳（メタデータ） (2020-10-11T18:49:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。