Fugu-MT 論文翻訳(概要): Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise

論文の概要: Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise

arxiv url: http://arxiv.org/abs/2306.10072v1
Date: Thu, 15 Jun 2023 21:55:44 GMT
ステータス: 処理完了
システム内更新日: 2023-06-26 01:18:31.320381
Title: Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise
Title（参考訳）: shorのアルゴリズムはノイズの存在下で大きな整数を分解しない
Authors: Jin-Yi Cai
Abstract要約: 我々は、ショアの量子ファクタリングアルゴリズムをノイズの多い量子ゲートの設定とみなす。回転ゲートに対するランダムノイズの一般的なモデルの下では、このアルゴリズムが$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。
参考スコア（独自算出の注目度）: 1.3198689566654105
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form $pq$ when the noise exceeds a vanishingly small level in terms of $n$ -- the number of bits of the integer to be factored, where $p$ and $q$ are from a well-defined set of primes of positive density. We further prove that with probability $1 - o(1)$ over random prime pairs $(p,q)$, Shor's factoring algorithm does not factor numbers of the form $pq$, with the same level of random noise present.
Abstract（参考訳）: 我々は、ショアの量子ファクタリングアルゴリズムをノイズの多い量子ゲートの設定とみなす。回転ゲート(制御)に対するランダムノイズの一般的なモデルの下で、このアルゴリズムは、正の密度の正の素数の集合から$p$と$q$が明確に定義された整数のビット数である$n$ --という点で、ノイズが消滅的に小さいレベルを超えるとき、$pq$という形の整数を分解しないことを証明している。さらに、確率 1 - o(1)$ over random prime pairs $(p,q)$ では、ショアの因子付けアルゴリズムは、同じレベルのランダムノイズを持つ $pq$ 形式の数を分解しない。

関連論文リスト

Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文参考訳（メタデータ） (2023-06-28T16:33:39Z)
Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
論文参考訳（メタデータ） (2023-05-08T08:49:01Z)
Distributed Quantum-classical Hybrid Shor's Algorithm [1.7396274240172125]
ショアのアルゴリズムは、ノイズ中間量子時代の最も重要な量子アルゴリズムの1つであると考えられている。 Shorのアルゴリズムに必要なリソースを削減するために、我々は新しい分散量子古典ハイブリッド順序決定アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-04-24T13:52:05Z)
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)
Higher degree sum-of-squares relaxations robust against oblivious outliers [14.58610686291355]
我々は、$Y=X*+N$という形の推定モデルを考える。本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
論文参考訳（メタデータ） (2022-11-14T13:09:12Z)
Distributed Shor's algorithm [1.7396274240172125]
ショアのアルゴリズムはピーター・ショアが提唱した最も重要な量子アルゴリズムの1つである。 2つの量子コンピュータを別々に使い、$dfracsr$を$sin0, 1, cdots, r-1$と見積もる。複数の制御量子ビットを使用する従来のショアのアルゴリズムと比較して、我々のアルゴリズムは、約$dfracL2$ qubitsを減らし、各コンピュータの回路深さを減らしている。
論文参考訳（メタデータ） (2022-07-13T06:00:03Z)
Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文参考訳（メタデータ） (2021-11-29T19:26:28Z)
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)
On completely factoring any integer efficiently in a single run of an order finding algorithm [0.0]
我々は、$mathbb Z_N*$からランダムに一意に選択された1つの要素の順序を考えると、時間内に$N$の完全分解を効率的に見つけることができることを示した。すると、$N$のすべての素因子は、古典的な後処理ステップで無視可能な計算コストで回収できる。
論文参考訳（メタデータ） (2020-07-20T12:32:34Z)

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