論文の概要: Revisiting Shor's quantum algorithm for computing general discrete
logarithms
- arxiv url: http://arxiv.org/abs/1905.09084v3
- Date: Mon, 6 Mar 2023 13:23:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-25 04:31:00.156732
- Title: Revisiting Shor's quantum algorithm for computing general discrete
logarithms
- Title（参考訳）: 一般離散対数計算のためのshorの量子アルゴリズムの再検討
- Authors: Martin Eker{\aa}
- Abstract要約: 一般的な離散対数計算のためのShorのアルゴリズムは、1回のランで約60%から82%の成功確率を達成できることを示す。
量子的に評価されるグループ演算数をわずかに増加させることで、このアルゴリズムが1回の実行で99%を超える成功確率を達成するために、さらにどのように修正されるかを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We heuristically show that Shor's algorithm for computing general discrete
logarithms achieves an expected success probability of approximately 60% to 82%
in a single run when modified to enable efficient implementation with the
semi-classical Fourier transform. By slightly increasing the number of group
operations that are evaluated quantumly and performing a single limited search
in the classical post-processing, or by performing two limited searches in the
post-processing, we show how the algorithm can be further modified to achieve a
success probability that heuristically exceeds 99% in a single run. We provide
concrete heuristic estimates of the success probability of the modified
algorithm, as a function of the group order $r$, the size of the search space
in the classical post-processing, and the additional number of group operations
evaluated quantumly. In the limit as $r \rightarrow \infty$, we heuristically
show that the success probability tends to one. In analogy with our earlier
works, we show how the modified quantum algorithm may be heuristically
simulated classically when the logarithm $d$ and $r$ are both known.
Furthermore, we heuristically show how slightly better tradeoffs may be
achieved, compared to our earlier works, if $r$ is known when computing $d$. We
generalize our heuristic to cover some of our earlier works, and compare it to
the non-heuristic analyses in those works.
- Abstract（参考訳）: 一般離散対数を計算するためのshorのアルゴリズムは、半古典フーリエ変換による効率的な実装を可能にするように修正された場合、1回の実行で約60%から82%の期待成功確率を達成することをヒューリスティックに示す。
量子的に評価されたグループ操作の数をわずかに増加させ、古典的な後処理において1回の限定探索を行うか、あるいは後処理で2回の限定探索を行うことで、アルゴリズムをさらに改良して1回の実行で99%を超える成功確率を達成できることを示す。
我々は,修正アルゴリズムの成功確率の具体的なヒューリスティックな推定を,群順序 $r$ の関数,古典的後処理における探索空間の大きさ,量子的に評価される群演算の追加数として提供する。
r \rightarrow \infty$ の極限において、成功確率が 1 になる傾向があることをヒューリスティックに示す。
初期の研究と類似して、修正された量子アルゴリズムが、対数 $d$ と $r$ の両方が知られているとき、古典的にヒューリスティックにシミュレーションされることを示す。
さらに私たちは、もし$r$が$d$を計算した場合に知っていれば、以前の仕事と比べて少し良いトレードオフが達成できるかをヒューリスティックに示します。
我々は、初期の作品のいくつかをカバーするようにヒューリスティックを一般化し、それらの作品における非ヒューリスティック分析と比較する。
関連論文リスト
- Circuit Implementation and Analysis of a Quantum-Walk Based Search Complement Algorithm [0.3277163122167433]
我々は,Shenvi,Kempe,Whaleyによって作成された量子ウォークに基づく探索アルゴリズムの修正版を提案する。
修正された進化作用素は、元のアルゴリズムのように反対の挙動、すなわちターゲット状態を測定する確率を減少させる。
論文 参考訳（メタデータ） (2024-05-25T18:11:14Z) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Simulation of IBM's kicked Ising experiment with Projected Entangled
Pair Operator [71.10376783074766]
我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。
提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。
我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
論文 参考訳（メタデータ） (2023-08-06T10:24:23Z) - An adaptive Bayesian quantum algorithm for phase estimation [0.0]
平均絶対誤差と平均二乗誤差の最適2次スケーリングを実現するためのコヒーレンスに基づく位相推定アルゴリズムを提案する。
ノイズの存在下で、我々のアルゴリズムは理論的な下界に近づく誤差を生成する。
論文 参考訳（メタデータ） (2023-03-02T19:00:01Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Improvement of quantum walk-based search algorithms in single marked
vertex graphs [0.0]
増幅増幅は通常、成功確率を増幅するために使用されるが、サッフル問題は続く。
本研究では,探索アルゴリズムの成功確率の向上とソッフル問題回避を両立できる一般化補間量子ウォークを定義する。
論文 参考訳（メタデータ） (2022-09-09T07:43:46Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Benchmarks for quantum computers from Shor's algorithm [0.0]
Shorのアルゴリズムと関連する周期フィニングアルゴリズムの特性は、量子コンピュータの動作のベンチマークとして機能する。
入力量子レジスタが増加するにつれて、周期フィニングの成功確率に対して、識別的普遍的な振る舞いが期待される。
論文 参考訳（メタデータ） (2021-11-27T09:46:16Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。