論文の概要: Resource analysis of Shor's elliptic curve algorithm with an improved quantum adder on a two-dimensional lattice

• arxiv url: http://arxiv.org/abs/2510.23212v1
• Date: Mon, 27 Oct 2025 11:02:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 15:28:15.528153
• Title: Resource analysis of Shor's elliptic curve algorithm with an improved quantum adder on a two-dimensional lattice
• Title（参考訳）: 2次元格子上に量子加算器を改良したショア楕円曲線アルゴリズムの資源解析
• Authors: Quan Gu, Han Ye, Junjie Chen, Xiongfeng Ma,
• Abstract要約: 量子コンピュータは古典的な暗号システムを壊す可能性がある。 toffoli depth $log n + loglog n + O(1)$ with only $O(n)$ ancillas。 2次元格子上のショア楕円曲線アルゴリズムの網羅的資源解析を行う。
• 参考スコア（独自算出の注目度）: 7.999752490202695
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computers have the potential to break classical cryptographic systems by efficiently solving problems such as the elliptic curve discrete logarithm problem using Shor's algorithm. While resource estimates for factoring-based cryptanalysis are well established, comparable evaluations for Shor's elliptic curve algorithm under realistic architectural constraints remain limited. In this work, we propose a carry-lookahead quantum adder that achieves Toffoli depth $\log n + \log\log n + O(1)$ with only $O(n)$ ancillas, matching state-of-the-art performance in depth while avoiding the prohibitive $O(n\log n)$ space overhead of existing approaches. Importantly, our design is naturally compatible with the two-dimensional nearest-neighbor architectures and introduce only a constant-factor overhead. Further, we perform a comprehensive resource analysis of Shor's elliptic curve algorithm on two-dimensional lattices using the improved adder. By leveraging dynamic circuit techniques with mid-circuit measurements and classically controlled operations, our construction incorporates the windowed method, Montgomery representation, and quantum tables, and substantially reduces the overhead of long-range gates. For cryptographically relevant parameters, we provide precise resource estimates. In particular, breaking the NIST P-256 curve, which underlies most modern public-key infrastructures and the security of Bitcoin, requires about $4300$ logical qubits and logical Toffoli fidelity about $10^{-9}$. These results establish new benchmarks for efficient quantum arithmetic and provide concrete guidance toward the experimental realization of Shor's elliptic curve algorithm.
• Abstract（参考訳）: 量子コンピュータは、ショアのアルゴリズムを用いて楕円曲線離散対数問題などの問題を効率的に解き、古典的な暗号システムを壊す可能性がある。 ファクタリングに基づく暗号解析のリソース推定は十分に確立されているが、現実的なアーキテクチャ制約下でのショアの楕円曲線アルゴリズムの同等の評価は限られている。 そこで本研究では,Toffoli depth $\log n + \log\log n + O(1)$を$O(n)$ ancillasで実現し,既存のアプローチの空間オーバーヘッドを抑えつつ,最先端のパフォーマンスを深くマッチングするキャリーヘッド量子加算器を提案する。 重要なことは、我々の設計は2次元の最も近いアーキテクチャと自然に互換性があり、定数要素のオーバーヘッドしか導入しないということです。 さらに,改良した加算器を用いて2次元格子上のショア楕円曲線アルゴリズムの網羅的資源分析を行う。 中間回路計測と古典的に制御された演算による動的回路技術を活用することで、窓ガラス方式、モンゴメリー表現、量子テーブルを導入し、長距離ゲートのオーバーヘッドを大幅に低減する。 暗号的に関連するパラメータに対しては、正確なリソース推定を提供する。 特に、最新の公開鍵インフラストラクチャとBitcoinのセキュリティの根底にあるNIST P-256曲線を破るには、論理キュービット約4300ドル、論理Toffoliフィリティ約10〜9ドルが必要だ。 これらの結果は、効率的な量子演算のための新しいベンチマークを確立し、ショアの楕円曲線アルゴリズムの実験的な実現に向けた具体的なガイダンスを提供する。

関連論文リスト

• Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited [4.843809993270313]
  2次元格子における最短ベクトル問題(SVP)の効率的な解法は、暗号や計算幾何学において実際的な重要性を持つ。 我々は、ユークリッドアルゴリズムを次元にわたって戦略的に適用する効率的な適応格子削減アルゴリズム textbfCrossEuc を開発した。 textbfHVecを反復的に呼び出すことによって、最適化されたアルゴリズム textbfHVecSBP は、ビット長$n$の任意の入力ベースに対して$O(log n M(n) )$ time の還元基底を得る。
  論文  参考訳（メタデータ） (2025-04-17T13:50:51Z)
• Quantum resource estimates for computing binary elliptic curve discrete logarithms [0.0]
  我々は、Shorのアルゴリズムの回路実装を設計するために、ウィンドウ化されたアプローチを採用する。 暗号的に関連するバイナリフィールドサイズに対するアルゴリズムの正確な論理ゲートと量子ビットカウントを提供する。 サーフェスコードマターベースの量子コンピュータ上で実行されるアルゴリズムのハードウェアフットプリントとランタイムを推定する。
  論文  参考訳（メタデータ） (2025-03-04T20:18:50Z)
• Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing [47.32366699399839]
  近似第二エピシロン依存(SOSP)の発見は、よく研究され基礎的な問題である。 本稿では,低次元センサマシン最適化問題に適用する。
  論文  参考訳（メタデータ） (2024-03-12T01:27:44Z)
• New Space-Efficient Quantum Algorithm for Binary Elliptic Curves using the Optimized Division Algorithm [1.2183405753834562]
  より少ない量子ビット数を用いる二進体上の新しい量子除算アルゴリズムを提案する。 2n$のフィールドの要素に対して、$lceil n/2 rceil - 1$ qubits を 8n2+4n-12+ 16n-8)lfloorlog(n)rfloor$ more Toffoli gates の代わりに保存できる。
  論文  参考訳（メタデータ） (2023-03-12T05:00:46Z)
• Digital-analog co-design of the Harrow-Hassidim-Lloyd algorithm [0.0]
  方程式の線形系を解くために、Harrow-Hassidim-Lloyd量子アルゴリズムが提案された。 問題行列の逆行列である$A$を補助量子ビットにマッピングするサブルーチンに対する明示的な量子回路は存在しない。 本稿では,アルゴリズムの深さを減らした共設計量子プロセッサを提案する。
  論文  参考訳（メタデータ） (2022-07-27T13:58:13Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)

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

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