論文の概要: An integer factorization algorithm which uses diffusion as a
computational engine
- arxiv url: http://arxiv.org/abs/2104.11616v2
- Date: Mon, 23 Jan 2023 18:07:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-02 14:59:08.449636
- Title: An integer factorization algorithm which uses diffusion as a
computational engine
- Title（参考訳）: 拡散を計算エンジンとして用いる整数分解アルゴリズム
- Authors: Carlos A. Cadavid, Paulina Hoyos, Jay Jorgenson, Lejla Smajlovi\'c,
Juan D. V\'elez
- Abstract要約: 我々は、素数でも素数でもないと仮定される整数$N$の因子を計算するアルゴリズムを開発する。
比較すると、ショアのアルゴリズムは量子コンピュータ上での最大$O(log N)2log (log N) log (log log N)$quantum stepsで使用されることが知られている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In this article we develop an algorithm which computes a divisor of an
integer $N$, which is assumed to be neither prime nor the power of a prime. The
algorithm uses discrete time heat diffusion on a finite graph. If $N$ has $m$
distinct prime factors, then the probability that our algorithm runs
successfully is at least $p(m) = 1-(m+1)/2^{m}$. We compute the computational
complexity of the algorithm in terms of classical, or digital, steps and in
terms of diffusion steps, which is a concept that we define here. As we will
discuss below, we assert that a diffusion step can and should be considered as
being comparable to a quantum step for an algorithm which runs on a quantum
computer. With this, we prove that our factorization algorithm uses at most
$O((\log N)^{2})$ deterministic steps and at most $O((\log N)^{2})$ diffusion
steps with an implied constant which is effective. By comparison, Shor's
algorithm is known to use at most $O((\log N)^{2}\log (\log N) \log (\log \log
N))$ quantum steps on a quantum computer.
As an example of our algorithm, we simulate the diffusion computer algorithm
on a desktop computer and obtain factorizations of $N=33$ and $N=1363$.
- Abstract（参考訳）: 本稿では、素数でも素数でもないと仮定される整数$n$の因子を計算するアルゴリズムを開発する。
このアルゴリズムは有限グラフ上の離散時間熱拡散を用いる。
もし$N$が$m$異なる素因子を持つなら、我々のアルゴリズムが成功する確率は少なくとも$p(m) = 1-(m+1)/2^{m}$である。
我々は、アルゴリズムの計算複雑性を古典的、あるいはデジタル的なステップと拡散ステップの観点で計算し、これはここで定義する概念である。
以下に議論するとおり、拡散ステップは量子コンピュータ上で実行されるアルゴリズムの量子ステップと同等であり、かつ同等であると考えるべきであると断言する。
これを用いて、我々の分解アルゴリズムは、少なくとも$O((\log N)^{2})$決定ステップ、そして少なくとも$O((\log N)^{2})$拡散ステップを有効であるインプリッド定数で使用することを証明した。
比較すると、ショアのアルゴリズムは量子コンピュータ上での最大$O((\log N)^{2}\log (\log N) \log (\log \log N))$量子ステップを使用することが知られている。
提案アルゴリズムの例として,デスクトップコンピュータ上の拡散計算機アルゴリズムをシミュレートし,N=33$およびN=1363$の分解係数を求める。
関連論文リスト
- Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - An Efficient Quantum Factoring Algorithm [0.27195102129094995]
我々は、$tildeO(n3/2)$の量子回路を独立に実行することで、$n$bit整数を分解できることを示した。
アルゴリズムの正しさは、指数的古典的因数分解アルゴリズムで使われるものに似た数論的な仮定に依存する。
論文 参考訳（メタデータ） (2023-08-12T13:57:38Z) - Distributed Quantum-classical Hybrid Shor's Algorithm [1.7396274240172125]
ショアのアルゴリズムは、ノイズ中間量子時代の最も重要な量子アルゴリズムの1つであると考えられている。
Shorのアルゴリズムに必要なリソースを削減するために、我々は新しい分散量子古典ハイブリッド順序決定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-24T13:52:05Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Distributed Shor's algorithm [1.7396274240172125]
ショアのアルゴリズムはピーター・ショアが提唱した最も重要な量子アルゴリズムの1つである。
2つの量子コンピュータを別々に使い、$dfracsr$を$sin0, 1, cdots, r-1$と見積もる。
複数の制御量子ビットを使用する従来のショアのアルゴリズムと比較して、我々のアルゴリズムは、約$dfracL2$ qubitsを減らし、各コンピュータの回路深さを減らしている。
論文 参考訳（メタデータ） (2022-07-13T06:00:03Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - A quantum algorithm for computing the Carmichael function [0.0]
量子コンピュータは、多くの数理論問題を効率的に解くことができる。
本稿では,任意の整数$N$に対して,所望の 1 に近い確率でカーマイケル関数を計算するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-03T19:30:27Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。