論文の概要: On the success probability of quantum order finding
- arxiv url: http://arxiv.org/abs/2201.07791v2
- Date: Mon, 28 Nov 2022 12:31:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-28 10:13:00.932385
- Title: On the success probability of quantum order finding
- Title（参考訳）: 量子次数探索の成功確率について
- Authors: Martin Eker{\aa}
- Abstract要約: 我々はShorのオーダーフィニングアルゴリズムが単一ランで$r$のオーダーを回復する確率の低い境界を証明した。
漸近的に、$r$が無限大の傾向にあるように、単一のランで$r$を回復する確率は1つになる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove a lower bound on the probability of Shor's order-finding algorithm
successfully recovering the order $r$ in a single run. The bound implies that
by performing two limited searches in the classical post-processing part of the
algorithm, a high success probability can be guaranteed, for any $r$, without
re-running the quantum part or increasing the exponent length compared to Shor.
Asymptotically, in the limit as $r$ tends to infinity, the probability of
successfully recovering $r$ in a single run tends to one. Already for moderate
$r$, a high success probability exceeding e.g. $1 - 10^{-4}$ can be guaranteed.
As corollaries, we prove analogous results for the probability of completely
factoring any integer $N$ in a single run of the order-finding algorithm.
- Abstract（参考訳）: shor の順序探索アルゴリズムが 1 回のランで $r$ を回収することに成功すれば,その確率は低い値であることが証明される。
このバウンドは、アルゴリズムの古典的な後処理部分で2つの制限された検索を行うことで、量子部分を再実行したり、shorと比較して指数長を増加させることなく、r$で高い成功確率を保証できることを意味する。
漸近的に、$r$が無限大の傾向にあるように、単一のランで$r$を回復する確率は1つになる。
適度な$r$の場合、例えば1 - 10^{-4}$を超える高い成功確率が保証される。
行程として、オーダーフィンディングアルゴリズムの単一実行において任意の整数$N$を完全に分解する確率について類似した結果を示す。
関連論文リスト
- Even-Cycle Detection in the Randomized and Quantum CONGEST Model [1.5566524830295314]
すべての$kgeq 2$に対して、$C_2k$-freenessは、CONGESTモデルで$O(n1-1/k)$ラウンドで決定できることを示す。
また、量子設定において、円複雑度$tilde O(nfrac12-frac12k)$を達成するためのアルゴリズムの量子化方法を示す。
論文 参考訳（メタデータ） (2024-02-19T10:23:37Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - On the Fine-Grained Query Complexity of Symmetric Functions [4.956977275061968]
本稿では、Watrous予想のきめ細かいバージョンについて考察する。
確率が任意に1/2ドルに近いランダム化および量子化アルゴリズムを含む。
論文 参考訳（メタデータ） (2023-09-20T13:04:45Z) - On the success probability of the quantum algorithm for the short DLP [0.0]
我々は,Ekeraa-Haastadのアルゴリズムが単一ランで短い$d$を回復する確率の低い境界を証明した。
私たちの限界によって、成功確率は、任意の短い$d$に対して1から1010$まで容易に押し付けられる。
論文 参考訳（メタデータ） (2023-09-04T18:26:45Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - 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) - Improvement of quantum walk-based search algorithms in single marked
vertex graphs [0.0]
増幅増幅は通常、成功確率を増幅するために使用されるが、サッフル問題は続く。
本研究では,探索アルゴリズムの成功確率の向上とソッフル問題回避を両立できる一般化補間量子ウォークを定義する。
論文 参考訳（メタデータ） (2022-09-09T07:43:46Z) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳（メタデータ） (2022-04-06T13:50:33Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Revisiting Shor's quantum algorithm for computing general discrete logarithms [0.0]
一般的な離散対数計算のためのShorのアルゴリズムは、1回のランで約60%から82%の成功確率を達成できることを示す。
量子的に評価されるグループ演算数をわずかに増加させることで、このアルゴリズムが1回の実行で99%を超える成功確率を達成するために、さらにどのように修正されるかを示す。
論文 参考訳（メタデータ） (2019-05-22T11:47:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。