論文の概要: Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA

• arxiv url: http://arxiv.org/abs/2502.17325v1
• Date: Mon, 24 Feb 2025 16:59:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:53:31.538936
• Title: Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA
• Title（参考訳）: 窓付きモジュラー演算のための最適化回路とRSAに対する量子攻撃への応用
• Authors: Alessandro Luongo, Varun Narasimhachar, Adithya Sireesh,
• Abstract要約: ウィンドウ演算は、空間時間トレードオフを伴う量子回路のコストを削減する手法である。 この作業では、ウィンドウ化されたモジュラー指数に4つの最適化を導入する。 これにより、暗号化アプリケーションに関連するモジュール型指数回路において、Toffoli数とToffoli深度が3%向上する。
• 参考スコア（独自算出の注目度）: 45.810803542748495
• License:
• Abstract: Windowed arithmetic [Gidney, 2019] is a technique for reducing the cost of quantum arithmetic circuits with space--time tradeoffs using memory queries to precomputed tables. It can reduce the asymptotic cost of modular exponentiation from $O\left(n^3\right)$ to $O\left(n^3/\log^2 n\right)$ operations, resulting in the current state-of-the-art compilations of quantum attacks against modern cryptography. In this work we introduce four optimizations to windowed modular exponentiation. We (1) show how the cost of unlookups can be reduced by $66\%$ asymptotically in the number of bits, (2) illustrate how certain addresses can be bypassed, reducing both circuit depth and the overall lookup cost, (3) demonstrate that multiple lookup--addition operations can be merged into a single, larger lookup at the start of the modular exponentiation circuit, and (4) reduce the depth of the unary conversion for unlookups. On a logical level, this leads to a $3\%$ improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications. This translates to some improvements on [Gidney and Eker\r{a}, 2021]'s factoring algorithm: for a given number of physical qubits, our improvements show a reduction in the expected runtime from $2\%$ to $6\%$ for factoring $\mathsf{RSA}$-$2048$ integers.
• Abstract（参考訳）: ウィンドウド算術 [Gidney, 2019] は,メモリクエリを用いた空間時間トレードオフによる量子演算回路のコスト削減手法である。 これは、モジュラー指数の漸近コストを$O\left(n^3\right)$から$O\left(n^3/\log^2 n\right)$オペレーションに削減し、現代の暗号に対する量子攻撃の最先端のコンパイルをもたらす。 この作業では、ウィンドウ化されたモジュラー指数に4つの最適化を導入する。 1) ビット数の漸近的にアンルックアップのコストが 66 % の漸近的に減少すること,(2) 特定のアドレスをバイパスし,回路深さと全体的なルックアップコストの両方を削減できること,(3) モジュラー指数回路の開始時に複数のルックアップ付加操作を単一の大きなルックアップにマージできること,(4) アンルックアップのユニタリ変換の深さを下げること,を示す。 論理レベルでは、これは暗号アプリケーションに関連するモジュラー指数回路に対して、Toffoli数とToffoli深度を$3\%向上させる。 これは、[Gidney and Eker\r{a}, 2021] のファクタリングアルゴリズムに関するいくつかの改善点である: 与えられた物理キュービット数に対して、我々の改善は、期待されるランタイムを$\%$から$6\%$に減らし、$\mathsf{RSA}$-2048$整数にすることを示している。

関連論文リスト

• Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost [3.129187821625805]
  本稿では,$GF(2n)$を$mathcalO(nlog_(n))ビットで乗算する量子回路を構築するアルゴリズムを提案する。 トリノミアル (trinomials) のようなプリミティブでは、掛け算は対数深さと $mathcalO(nlog_(n)) ビットで行うことができる。
  論文  参考訳（メタデータ） (2025-01-27T15:26:11Z)
• Demonstrating dynamic surface codes [138.1740645504286]
  曲面符号の3つの時間力学的実装を実験的に実証した。 まず、曲面コードを六角格子上に埋め込んで、キュービットあたりの結合を4つから3つに減らした。 第二に、サーフェスコードを歩き、データの役割を交換し、各ラウンドごとにキュービットを測定し、蓄積した非計算エラーの組込み除去による誤り訂正を達成する。 第3に、従来のCNOTの代わりにiSWAPゲートを用いた表面コードを実現し、追加のオーバーヘッドを伴わずに、エラー訂正のための実行可能なゲートセットを拡張した。
  論文  参考訳（メタデータ） (2024-12-18T21:56:50Z)
• Space-Efficient and Noise-Robust Quantum Factoring [10.974556218898435]
  我々はRegevの最近の量子ファクタリングアルゴリズム(arXiv:2308.06572)を改善する。 我々は独立に$approx sqrtn$ timesを実行し、Regevの古典的な後処理手順を適用する。 第二の貢献は、レゲフの古典的な後処理手順が量子回路の一定の部分の誤りを許容するために修正可能であることを示すことである。
  論文  参考訳（メタデータ） (2023-10-02T04:31:21Z)
• Low-depth Gaussian State Energy Estimation [0.0]
  基底状態エネルギー推定(GSEE)は、量子化学や材料において重要なサブルーチンである。 我々は、O(logDelta)$としてスケールする多数の操作を使用する新しいGSEEアルゴリズムについて詳述する。 このアルゴリズムは、Delta$を$Delta$と$epsilon$の何れかに置き換えることで、低深度とフル深度との間を補間するように適応する。
  論文  参考訳（メタデータ） (2023-09-28T18:29:14Z)
• INR-Arch: A Dataflow Architecture and Compiler for Arbitrary-Order Gradient Computations in Implicit Neural Representation Processing [66.00729477511219]
  計算グラフとして表される関数を考えると、従来のアーキテクチャはn階勾配を効率的に計算する上で困難に直面している。 InR-Archは,n階勾配の計算グラフをハードウェア最適化データフローアーキテクチャに変換するフレームワークである。 1.8-4.8x と 1.5-3.6x の高速化を CPU と GPU のベースラインと比較した結果を示す。
  論文  参考訳（メタデータ） (2023-08-11T04:24:39Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Halving the width of Toffoli based constant modular addition to n+3 qubits [69.43216268165402]
  本稿では,Toffoli ゲートの深さが $mathcalO(n)$ の固定モジュラ加算を行う演算回路を提案する。 これは、最先端のToffoliベースの定数モジュラー加算器の幅と比較して2倍の改善である。
  論文  参考訳（メタデータ） (2021-02-06T17:07:48Z)
• Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication [1.9518237361775532]
  大規模ニューラルネットワークハードウェアの最近の進歩は、その実践的実装を短期的可能性にしている。 しきい値ゲート論理を統合する2つの$N$を$N$行列に乗算する理論的アプローチについて述べる。 デンス行列乗算は畳み込みニューラルネットワークトレーニングにおけるコア演算である。
  論文  参考訳（メタデータ） (2020-06-25T18:28:10Z)
• Improved quantum circuits for elliptic curve discrete logarithms [6.058525641792685]
  楕円曲線スカラー乗算のための改良された量子回路を提案する。 可逆整数やモジュラ演算などの低レベル成分を最適化する。 Q#量子プログラミング言語における点加算の完全な実装を提供する。
  論文  参考訳（メタデータ） (2020-01-27T04:08:49Z)

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

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