Fugu-MT 論文翻訳(概要): On completely factoring any integer efficiently in a single run of an order finding algorithm

論文の概要: On completely factoring any integer efficiently in a single run of an order finding algorithm

arxiv url: http://arxiv.org/abs/2007.10044v2
Date: Wed, 9 Dec 2020 18:47:50 GMT
ステータス: 処理完了
システム内更新日: 2023-05-08 23:16:39.419081
Title: On completely factoring any integer efficiently in a single run of an order finding algorithm
Title（参考訳）: 順序探索アルゴリズムの単一実行における整数の完全因数化について
Authors: Martin Eker{\aa}
Abstract要約: 我々は、$mathbb Z_N*$からランダムに一意に選択された1つの要素の順序を考えると、時間内に$N$の完全分解を効率的に見つけることができることを示した。すると、$N$のすべての素因子は、古典的な後処理ステップで無視可能な計算コストで回収できる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We show that given the order of a single element selected uniformly at random from $\mathbb Z_N^*$, we can with very high probability, and for any integer $N$, efficiently find the complete factorization of $N$ in polynomial time. This implies that a single run of the quantum part of Shor's factoring algorithm is usually sufficient. All prime factors of $N$ can then be recovered with negligible computational cost in a classical post-processing step. The classical algorithm required for this step is essentially due to Miller.
Abstract（参考訳）: 我々は、$\mathbb Z_N^*$ からランダムに一意に選択された1つの要素の順序を考えると、非常に高い確率で、任意の整数 $N$ に対して多項式時間における$N$ の完全分解を効率的に見つけることができることを示す。これは、ショアの因数分解アルゴリズムの量子部分の単一実行が通常十分であることを意味する。 N$のすべての素因子は、古典的な後処理ステップで無視可能な計算コストで回収できる。このステップに必要な古典的なアルゴリズムは、基本的にmillerによるものである。

関連論文リスト

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth [8.938538037322381]
本稿では、古典的硬さがRSAと同値であると期待されているものを含む、整数の大規模なクラスを分解する小型量子回路を提案する。我々の知る限り、古典的にハードなファクタリング問題に対して、サブ線形量子ビットカウントを達成した初めてのMod-time回路である。 We build on the quantum algorithm found by Li, Peng, Du and Suter (Nature Scientific Reports 2012) which instead on computing the Jacobi symbol in quantum superposition。
論文参考訳（メタデータ） (2024-12-17T05:34:54Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
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)
An Efficient Quantum Factoring Algorithm [0.27195102129094995]
我々は、$tildeO(n3/2)$の量子回路を独立に実行することで、$n$bit整数を分解できることを示した。アルゴリズムの正しさは、指数的古典的因数分解アルゴリズムで使われるものに似た数論的な仮定に依存する。
論文参考訳（メタデータ） (2023-08-12T13:57:38Z)
Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise [1.3198689566654105]
我々は、ショアの量子ファクタリングアルゴリズムをノイズの多い量子ゲートの設定とみなす。回転ゲートに対するランダムノイズの一般的なモデルの下では、このアルゴリズムが$pq$という形の整数を分解しないことが証明される。さらに、確率 1 - o(1)$ over random prime pairs $(p,q)$, Shor's factoring algorithm not factor number of the form $pq$, with the level of random noise present。
論文参考訳（メタデータ） (2023-06-15T21:55:44Z)
Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文参考訳（メタデータ） (2023-02-16T13:57:19Z)
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)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文参考訳（メタデータ） (2022-12-03T02:45:23Z)
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)
An integer factorization algorithm which uses diffusion as a computational engine [0.0]
我々は、素数でも素数でもないと仮定される整数$N$の因子を計算するアルゴリズムを開発する。比較すると、ショアのアルゴリズムは量子コンピュータ上での最大$O(log N)2log (log N) log (log log N)$quantum stepsで使用されることが知られている。
論文参考訳（メタデータ） (2021-04-23T14:11:33Z)

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