論文の概要: Quantum Algorithms for Discrete Log Require Precise Rotations
- arxiv url: http://arxiv.org/abs/2412.17269v1
- Date: Mon, 23 Dec 2024 04:33:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-24 15:57:27.084942
- Title: Quantum Algorithms for Discrete Log Require Precise Rotations
- Title(参考訳): 離散ログ要求精密回転のための量子アルゴリズム
- Authors: Jin-Yi Cai, Ben Young,
- Abstract要約: Shorの量子因数分解アルゴリズムは、アルゴリズムの量子フーリエ変換がランダムノイズの消滅レベルによって破壊されるとき、大きな整数を分解できないことを示す。
また、同じノイズレベルがShorのアルゴリズムを確率 1-o(1) で失敗させ、ランダムに選択された素数 P に対して離散ログ P を計算することも示している。
- 参考スコア(独自算出の注目度): 2.0038377839038644
- License:
- Abstract: Recently, Cai showed that Shor's quantum factoring algorithm fails to factor large integers when the algorithm's quantum Fourier transform (QFT) is corrupted by a vanishing level of random noise on the QFT's precise controlled rotation gates. We show that under the same error model, Shor's quantum discrete log algorithm, and its various modifications, fail to compute discrete logs modulo P for a positive density of primes P and a similarly vanishing level of noise. We also show that the same noise level causes Shor's algorithm to fail with probability 1-o(1) to compute discrete logs modulo P for randomly selected primes P.
- Abstract(参考訳): 近年のカイは、量子フーリエ変換(QFT)がQFTの精密制御された回転ゲート上のランダムノイズの消失によって崩壊した場合、ショアの量子因数分解アルゴリズムは大きな整数を分解できないことを示した。
同じ誤差モデルの下では、ショアの量子離散ログアルゴリズムとその様々な修正により、素数 P の正の密度と同様のノイズのレベルについて離散ログ P を計算できないことが示される。
また、同じノイズレベルがShorのアルゴリズムを確率 1-o(1) で失敗させ、ランダムに選択された素数 P に対して離散ログ P を計算することも示している。
関連論文リスト
- Practical implementation of a single-qubit rotation algorithm [0.0]
Toffoliは重要な普遍量子ゲートであり、Cliffordゲートと共に将来のフォールトトレラント量子コンピューティングハードウェアで利用できるようになる。
我々はClifford+Toffoliゲートセットを用いて,最近提案された1量子回転アルゴリズムの性能を評価する。
論文 参考訳(メタデータ) (2024-10-24T13:53:21Z) - T-Count Optimizing Genetic Algorithm for Quantum State Preparation [0.05999777817331316]
本稿では,Clifford+Tゲートセットのゲートからなる状態準備回路に対して,遺伝的アルゴリズムを提案する。
我々のアルゴリズムは、最もエラーが多いコンポーネントの数が減少するフォールトトレラント実装可能なソリューションを自動的に生成する。
論文 参考訳(メタデータ) (2024-06-06T12:26:14Z) - Simulation and analysis of quantum phase estimation algorithm in the
presence of incoherent quantum noise channels [0.0]
本研究では, トラスト保存と完全正の量子チャネルをモデル化した量子アルゴリズムにおける非コヒーレントノイズの影響について検討する。
シミュレーションの結果,単位作用素の固有値の標準偏差は個々の量子ビットの誤差確率に強い指数的依存性を持つことが示された。
論文 参考訳(メタデータ) (2023-07-28T17:08:56Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳(メタデータ) (2023-04-12T18:10:47Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
ほとんどの人造システム、特にコンピュータは決定論的に機能する。
本稿では、量子物理学が確率法則に従うときの直観的なアプローチである量子情報理論による接続を提供する。
論文 参考訳(メタデータ) (2022-09-08T17:55:30Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳(メタデータ) (2021-11-29T19:26:28Z) - Nearly optimal quantum algorithm for generating the ground state of a
free quantum field theory [0.0]
量子場理論の基底状態に対する近似を生成するための準線形量子アルゴリズムを考案する。
我々のアルゴリズムは、基底状態生成のための最先端の量子アルゴリズムを超クアッドレートで高速化する。
論文 参考訳(メタデータ) (2021-10-12T02:48:46Z) - Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation [0.0]
雑音二元線形問題(NBLP)の量子可解性について完全解析する。
NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
論文 参考訳(メタデータ) (2021-09-23T07:46:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。