論文の概要: Diffusion Computation versus Quantum Computation: A Comparative Model for Order Finding and Factoring

• arxiv url: http://arxiv.org/abs/2601.02518v1
• Date: Mon, 05 Jan 2026 19:45:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-07 17:02:12.711721
• Title: Diffusion Computation versus Quantum Computation: A Comparative Model for Order Finding and Factoring
• Title（参考訳）: 拡散計算と量子計算--次数探索と分解の比較モデル
• Authors: Carlos A. Cadavid, Paulina Hoyos, Jay Jorgenson, Lejla Smajlović, J. D. Vélez,
• Abstract要約: 本稿では,有限グラフ上の拡散過程にのみアクセス可能な,整数分解のハイブリッド計算モデルについて検討する。 Shor のアルゴリズムとの比較は,概念的およびモデルベースである。 デジタルステップと拡散ステップの2つのコスト尺度で複雑性を報告する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a hybrid computational model for integer factorization in which the only non-classical resource is access to an \emph{iterated diffusion process} on a finite graph. Concretely, a \emph{diffusion step} is defined to be one application of a symmetric stochastic matrix (the half-lazy walk operator) to an $\ell^{1}$--normalized state vector, followed by an optional readout of selected coordinates. Let $N\ge 3$ be an odd integer which is neither prime nor a prime power, and let $b\in(\mathbb{Z}/N\mathbb{Z})^\ast$ have odd multiplicative order $r={\rm ord}_N(b)$. We construct, without knowing $r$ in advance, a weighted Cayley graph whose vertex set is the cyclic subgroup $\langle b\rangle$ and whose edges correspond to the powers $b^{\pm 2^t}$ for $t\le \lfloor \log_2 N\rfloor+1$. Using an explicit spectral decomposition together with an elementary doubling lemma, we show that $r$ can be recovered from a single heat-kernel value after at most $O((\log_2 N)^2)$ diffusion steps, with an effective bound. We then combine this order-finding model with the standard reduction from factoring to order finding (in the spirit of Shor's framework) to obtain a randomized factorization procedure whose success probability depends only on the number $m$ of distinct prime factors of $N$. Our comparison with Shor's algorithm is \emph{conceptual and model-based}. We replace unitary $\ell^2$ evolution by Markovian $\ell^1$ evolution, and we report complexity in two cost measures: digital steps and diffusion steps. Finally, we include illustrative examples and discussion of practical implementations.
• Abstract（参考訳）: 有限グラフ上の \emph{iterated diffusion process} に、古典的でない唯一の資源がアクセスできるような、整数分解のためのハイブリッド計算モデルについて検討する。 具体的には、 \emph{diffusion step} は対称確率行列(半遅延ウォーク演算子)の$\ell^{1}$-正規化状態ベクトルへの1つの応用として定義され、次に選択された座標の任意の読み出しが行われる。 N\ge 3$ を素数でも素数でもない奇整数とし、b\in(\mathbb{Z}/N\mathbb{Z})^\ast$ を奇乗法的位数 $r={\rm ord}_N(b)$ とする。 我々は、事前に$r$を知ることなく、頂点集合が巡回部分群 $\langle b\rangle$ であり、その辺が $t\le \lfloor \log_2 N\rfloor+1$ に対応するような重み付きケイリーグラフを構築する。 初等倍数補題とともに明示的なスペクトル分解を用いて、少なくとも$O((\log_2 N)^2)$拡散ステップの後に1つの熱カーネル値から$r$を回収できることを示す。 次に、この次数フィンディングモデルと、(ショアのフレームワークの精神において)階数探索から階数発見への標準的削減とを組み合わせて、成功確率が$N$の異なる素数の数$m$にのみ依存するランダム化因数分解手順を得る。 Shor のアルゴリズムとの比較は \emph{conceptual and model-based} である。 我々は、一元的$\ell^2$進化をマルコフ的$\ell^1$進化に置き換え、デジタルステップと拡散ステップの2つのコスト尺度で複雑さを報告する。 最後に、実演例と実践実践の議論を紹介する。

関連論文リスト

• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。 このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
  論文  参考訳（メタデータ） (2025-10-09T09:47:40Z)
• Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
  有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。 我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。 数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity [6.812247730094931]
  任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。 また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
  論文  参考訳（メタデータ） (2023-09-25T09:50:15Z)
• Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms [0.4527270266697462]
  積として$Z$を表現する方法を示す: Z=Z(lambda)tilde Z(lambda)$ ここで乗法補正である$tilde Z(lambda)$はノードに依存しない確率分布に対する期待値である。 また,画像デノイズ化問題に対する本手法の適用性についても論じる。
  論文  参考訳（メタデータ） (2023-01-25T00:50:28Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)

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

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