論文の概要: Implementation and Analysis of Regev's Quantum Factorization Algorithm

• arxiv url: http://arxiv.org/abs/2502.09772v1
• Date: Thu, 13 Feb 2025 21:02:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-17 14:46:45.808743
• Title: Implementation and Analysis of Regev's Quantum Factorization Algorithm
• Title（参考訳）: Regevの量子分解アルゴリズムの実装と解析
• Authors: Przemysław Pawlitko, Natalia Moćko, Marcin Niemiec, Piotr Chołda,
• Abstract要約: 本稿では,合成数を分解するRegevのアルゴリズムの実装について述べる。 Regevの理論的優位性にもかかわらず、我々の実装は小さな整数因数分解のためのShorのアルゴリズムよりも長い実行時間を示した。
• 参考スコア（独自算出の注目度）: 0.2874893537471256
• License:
• Abstract: Quantum computing represents a significant advancement in computational capabilities. Of particular concern is its impact on asymmetric cryptography through, notably, Shor's algorithm and the more recently developed Regev's algorithm for factoring composite numbers. We present our implementation of the latter. Our analysis encompasses both quantum simulation results and classical component examples, with particular emphasis on comparative cases between Regev's and Shor's algorithms. Our experimental results reveal that Regev's algorithm indeed outperforms Shor's algorithm for certain composite numbers in practice. However, we observed significant performance variations across different input values. Despite Regev's algorithm's theoretical asymptotic efficiency advantage, our implementation exhibited execution times longer than Shor's algorithm for small integer factorization in both quantum and classical components. These findings offer insights into the practical challenges and performance characteristics of implementing Regev's algorithm in realistic quantum computing scenarios.
• Abstract（参考訳）: 量子コンピューティングは、計算能力の大幅な進歩を示している。 特に懸念されているのは、Shorのアルゴリズムとより最近開発されたRegevの合成数分解アルゴリズムによる非対称暗号への影響である。 我々は後者の実装を提示する。 我々の分析は量子シミュレーション結果と古典的成分例の両方を含み、特にRegevのアルゴリズムとShorのアルゴリズムの比較事例に重点を置いている。 我々の実験結果から、レゼフのアルゴリズムは、実際にある合成数に対してショアのアルゴリズムより優れていることが判明した。 しかし,異なる入力値にまたがる有意な性能変化が観察された。 リーゼフのアルゴリズムの理論的漸近効率の利点にもかかわらず、我々の実装は量子および古典的成分の小さな整数分解のためのショアのアルゴリズムよりも長い実行時間を示した。 これらの知見は、現実的な量子コンピューティングシナリオにおけるRegevのアルゴリズムの実装の実践的課題と性能特性に関する洞察を与える。

関連論文リスト

• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  本研究は、4つの異なる最適化問題にまたがっていくつかの非フォールト耐性量子コンピューティングアルゴリズムを体系的にベンチマークする。 我々のベンチマークには、変分量子固有解法など、ノイズの多い中間スケール量子(NISQ)アルゴリズムが含まれている。 以上の結果から,FTQC以外のアルゴリズムは全ての問題に対して最適に動作しないことが明らかとなり,アルゴリズム戦略の調整の必要性が浮き彫りになった。
  論文  参考訳（メタデータ） (2024-10-30T08:41:29Z)
• A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography [0.0]
  我々はRegevの量子アルゴリズムを、一方のEkeraa-G"artnerの拡張と、他方の離散対数分解と計算のための既存の最先端量子アルゴリズムと比較する。 我々の結論は、空間節約最適化のないRegevのアルゴリズムは、非計算量子メモリが安価であれば、ラン当たりの優位性を得るが、全体的な優位性は得られないということである。
  論文  参考訳（メタデータ） (2024-05-23T09:59:00Z)
• On the Finite-Time Performance of the Knowledge Gradient Algorithm [1.713291434132985]
  知識勾配(KG)アルゴリズムは、ベストアーム識別(BAI)問題に対して人気があり効果的なアルゴリズムである。 KGアルゴリズムの有限時間性能に関する新しい理論的結果を示す。
  論文  参考訳（メタデータ） (2022-06-14T13:42:05Z)
• Performance Evaluations of Noisy Approximate Quantum Fourier Arithmetic [1.1140384738063092]
  量子コンピュータ上でQFTベースの整数加算と乗算を実装した。 これらの演算は様々な量子応用に基本的である。 我々はこれらの実装をIBMの超伝導量子ビットアーキテクチャに基づいて評価する。
  論文  参考訳（メタデータ） (2021-12-17T06:51:18Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations [9.134244356393665]
  群畳み込みと相互相関は、与えられた問題設定に固有の対称性を解析または活用するために一般的に数学で使用される。 ここでは,量子状態として格納されたデータの線形群畳み込みと相互相関を行うための効率的な量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T12:21:31Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。 本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
  論文  参考訳（メタデータ） (2021-06-23T16:33:33Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Coded Distributed Computing with Partial Recovery [56.08535873173518]
  部分回復型符号化計算(CCPR)と呼ばれる新しい符号化行列ベクトル乗法を導入する。 CCPRは計算時間と復号化の複雑さを減らし、精度と計算速度のトレードオフを可能にする。 次に、この手法をより一般的な計算タスクの分散実装に拡張し、部分的回復を伴う符号化通信方式を提案する。
  論文  参考訳（メタデータ） (2020-07-04T21:34:49Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)

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

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