論文の概要: Asymptotic Vanishing of the Success Probability in Shor's Algorithm

• arxiv url: http://arxiv.org/abs/2510.06271v1
• Date: Mon, 06 Oct 2025 11:00:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.083169
• Title: Asymptotic Vanishing of the Success Probability in Shor's Algorithm
• Title（参考訳）: Shorアルゴリズムにおける成功確率の漸近的消滅
• Authors: João P. da Cruz,
• Abstract要約: N > 無限大として、乗法群 Omega_N = (Z/NZ)x は確率空間の非八次族を形成し、成功した基底に関連する確率重みは 1/phi(N) として崩壊する。 モンテカルロは、N = 106までシミュレーションし、この崩壊と定常的な成功確率がないことを確認する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shor's factoring algorithm guarantees a success probability of at least one half for any fixed modulus N = pq with distinct primes p and q. We show that this guarantee does not extend to the asymptotic regime. As N -> infinity, the multiplicative groups Omega_N = (Z/NZ)^x form a non-tight family of probability spaces, and the probability weight associated with successful bases, proportional to p(success | a', N) p(a' | N), decays as 1/phi(N). The ensemble of uniform measures {mu_N} therefore admits no weak limit, implying an asymptotic loss of ergodicity. Monte Carlo simulations up to N <= 10^6 confirm this decay and the absence of a stationary success probability. These results demonstrate that the "expected polynomial time" in order finding is only locally defined: no global expectation exists once the arithmetic domain expands. The asymptotic vanishing of success probability explains the empirical absence of large-N implementations of Shor's algorithm and sets a fundamental limit on the scalability of quantum factoring.
• Abstract（参考訳）: ショアの分解アルゴリズムは、異なる素数 p と q を持つ任意の固定係数 N = pq に対して、少なくとも半分の成功確率を保証する。 この保証が漸近的な体制に及ばないことを示す。 N > 無限大として、乗法群 Omega_N = (Z/NZ)^x は確率空間の非高次族を形成し、成功する基底に関連する確率重みは p(success | a', N) p(a' | N) に比例して 1/phi(N) として崩壊する。 したがって、一様測度 {mu_N} のアンサンブルは弱極限を認めず、漸近的にエルゴード性を失うことを意味する。 モンテカルロは N <= 10^6 までシミュレーションし、この崩壊と定常的な成功確率がないことを確認する。 これらの結果は、次数探索の「予想多項式時間」が局所的にのみ定義されることを示しており、算術領域が拡大すると大域的な期待は存在しない。 成功確率の漸近的消滅は、ショアのアルゴリズムの大規模N実装の実証的欠如を説明し、量子ファクタリングのスケーラビリティの基本的な限界を設定する。

関連論文リスト

• On the Algorithmic Information Between Probabilities [6.5268245109828005]
  我々はアルゴリズムの保存不等式を確率測度まで拡張する。 確率測度の自己情報の量は、ランダム化された処理に送信しても増加しない。 純状態の圧倒的多数に対して量子測度が与えられた場合、意味のある情報は得られないことが示される。
  論文  参考訳（メタデータ） (2023-03-13T17:20:27Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• A lower confidence sequence for the changing mean of non-negative right heavy-tailed observations with bounded mean [9.289846887298854]
  信頼シーケンスは、時間パラメトリックカバレッジ保証付き予測可能なパラメータシーケンスに対する適応されたセット列を生成する。 この研究は、スラックが0に収束するランニング平均条件付き期待値に対して、漸近的でない低CSを構成する。
  論文  参考訳（メタデータ） (2022-10-20T09:50:05Z)
• On the success probability of quantum order finding [0.0]
  我々はShorのオーダーフィニングアルゴリズムが単一ランで$r$のオーダーを回復する確率の低い境界を証明した。 漸近的に、$r$が無限大の傾向にあるように、単一のランで$r$を回復する確率は1つになる。
  論文  参考訳（メタデータ） (2022-01-19T18:58:18Z)
• Time-uniform central limit theory and asymptotic confidence sequences [34.00292366598841]
  信頼シーケンス(CS)は任意の停止時間に有効な推論を提供し、データに対する「覗き見」に対する罰則を生じさせない。 CSは漸近的ではなく、有限サンプルの保証を楽しむが、上記の信頼区間の広範な適用性はない。 CLTのような汎用性と(漸近的な)時間一様保証に対する漸近的CSは非漸近的妥当性を否定する。
  論文  参考訳（メタデータ） (2021-03-11T05:45:35Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)

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

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