論文の概要: From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms

• arxiv url: http://arxiv.org/abs/2606.17647v1
• Date: Tue, 16 Jun 2026 08:06:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-17 17:15:32.344179
• Title: From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms
• Title（参考訳）: 周期探索から格子サンプリング:ShorとRegevのファクタリングアルゴリズムの実験的考察
• Authors: Daniela Falcó, Arturo Rodríguez, Guillermo Rivas, Ricardo S. Alonso,
• Abstract要約: 本稿では、実量子ハードウェア上に実装されたRegevの量子ファクタリングアルゴリズムの実験的検討を行い、その挙動をShorのアルゴリズムと比較する。 我々の分析は、ShorとRegevのアルゴリズムが算術構造を量子状態にエンコードする様々な方法を強調している。 どちらのアルゴリズムも小さなN状態において実用上の優位性を示していないが、現代の量子デバイスにおける相対的堅牢性と障害モードについての洞察を提供する。
• 参考スコア（独自算出の注目度）: 0.7233065479782753
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum algorithms for integer factorization represent one of the most prominent applications of quantum computation, with far-reaching implications for modern cryptography. While Shor's algorithm provides a polynomial-time solution in the ideal quantum model, its practical implementation is severely constrained by the limitations of current noisy intermediate-scale quantum (NISQ) hardware. These constraints have motivated the exploration of alternative factoring algorithms with different structural and resource trade-offs. In this work, we present an experimental study of Regev's quantum factoring algorithm, implemented on real quantum hardware, and compare its behavior with that of Shor's algorithm under analogous conditions. Focusing on the case N = 15, we execute both algorithms on the QMIO quantum computer at the Centro de Supercomputacion de Galicia (CESGA) and contrast the results with one of IBM's open-access quantum computers and ideal simulations. This parallel execution enables a low-level comparison of the two algorithms, highlighting how their respective quantum implementations interact with hardware noise, limited circuit depth, and finite sampling. Our analysis emphasizes the different ways in which Shor's and Regev's algorithms encode arithmetic structure into quantum states through Fourier sampling in one and higher dimensions, respectively, and how these differences manifest in experimental outcomes. Although neither algorithm demonstrates a practical advantage in the small N regime, the results provide insight into their relative robustness and failure modes on contemporary quantum devices. This study illustrates the value of experimental benchmarking of alternative quantum factoring algorithms as a means of understanding the practical implications of algorithmic design choices in the NISQ era.
• Abstract（参考訳）: 整数因数分解のための量子アルゴリズムは、量子計算の最も顕著な応用の1つであり、現代の暗号に大きく影響している。 Shorのアルゴリズムは理想的な量子モデルにおいて多項式時間解を提供するが、その実践的実装は現在のノイズの多い中間スケール量子(NISQ)ハードウェアの限界によって厳しく制約されている。 これらの制約は、異なる構造とリソースのトレードオフを持つ代替ファクタリングアルゴリズムの探索を動機付けている。 本研究では、実量子ハードウェア上に実装されたRegevの量子ファクタリングアルゴリズムの実験的検討を行い、類似条件下でのShorのアルゴリズムの挙動と比較する。 N = 15の場合に着目して、我々はQMIO量子コンピュータ上でCESGA(Centro de Supercomputacion de Galicia)で両方のアルゴリズムを実行し、その結果をIBMのオープンアクセス量子コンピュータの1つと理想的なシミュレーションと比較する。 この並列実行は、2つのアルゴリズムの低レベル比較を可能にし、それぞれの量子実装がハードウェアノイズ、限られた回路深さ、有限サンプリングとどのように相互作用するかを強調している。 本分析では,1次元および高次元のフーリエサンプリングにより,Shor と Regev のアルゴリズムが量子状態に演算構造をエンコードする方法と,これらの差が実験結果にどのように現れるかを強調した。 どちらのアルゴリズムも小さなN状態において実用上の優位性を示していないが、現代の量子デバイスにおける相対的堅牢性と障害モードについての洞察を提供する。 本研究は,NISQ時代のアルゴリズム設計選択の実践的意味を理解する手段として,代替量子ファクタリングアルゴリズムの実験的なベンチマーク値について述べる。

関連論文リスト

• Implementation and Analysis of Regev's Quantum Factorization Algorithm [0.2874893537471256]
  本稿では,合成数を分解するRegevのアルゴリズムの実装について述べる。 Regevの理論的優位性にもかかわらず、我々の実装は小さな整数因数分解のためのShorのアルゴリズムよりも長い実行時間を示した。
  論文  参考訳（メタデータ） (2025-02-13T21:02:15Z)
• 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)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice [0.0]
  変分量子アルゴリズム、特に変分量子固有解器の変種は最適化(CO)問題に対処するために提案されている。 ベンチマークとしてMax-Cutを用いてCO問題を解く上で,このスケーリング結果がどのような意味を持つのかを数値的に検討する。
  論文  参考訳（メタデータ） (2024-08-06T09:57:34Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。 どの場の量子スピードアップが達成できるかという新たな課題が生じる。 量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
  論文  参考訳（メタデータ） (2024-02-26T09:32:07Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  テンソルネットワーク(TN)アルゴリズムは、パラメタライズド量子回路(PQC)にマッピングできる 本稿では,現実的な量子回路を用いてTN状態を近似する新しいプロトコルを提案する。 その結果、量子回路の逐次的な成長と最適化を含む1つの特定のプロトコルが、他の全ての手法より優れていることが明らかとなった。
  論文  参考訳（メタデータ） (2022-09-01T17:08:41Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。 本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
  論文  参考訳（メタデータ） (2021-11-19T12:35:26Z)
• Resource-efficient encoding algorithm for variational bosonic quantum simulations [0.0]
  量子コンピューティングのノイズ中間スケール量子(NISQ)時代には、量子資源は限られている。 ボゾン基底と励起状態計算のための資源効率のよい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-23T19:00:05Z)
• An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
  小型地震インバージョン問題を解決するために,D波量子アニールに量子アルゴリズムを適用した。 量子コンピュータによって達成される精度は、少なくとも古典的コンピュータと同程度である。
  論文  参考訳（メタデータ） (2020-05-06T14:18:44Z)

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

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