論文の概要: 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 を計算することも示している。
関連論文リスト
- Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。
我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
論文 参考訳(メタデータ) (2025-02-13T12:04:39Z) - Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
線形微分方程式に対する量子アルゴリズムを提案する。
アルゴリズムのゲートの複雑さは、次元に依存する$mathcalO(dlog(Nd))$を示す。
アルゴリズムはOrnstein-Uhlenbeck過程、ブラウン運動、L'evy飛行に対して数値的に検証される。
論文 参考訳(メタデータ) (2024-12-19T14:04:11Z) - Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。
理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
論文 参考訳(メタデータ) (2024-11-29T05:29:47Z) - Practical implementation of a single-qubit rotation algorithm [0.0]
Toffoliは重要な普遍量子ゲートであり、Cliffordゲートと共に将来のフォールトトレラント量子コンピューティングハードウェアで利用できるようになる。
我々はClifford+Toffoliゲートセットを用いて,最近提案された1量子回転アルゴリズムの性能を評価する。
論文 参考訳(メタデータ) (2024-10-24T13:53:21Z) - Evaluation of phase shifts for non-relativistic elastic scattering using quantum computers [39.58317527488534]
本研究は, 量子コンピュータ上での一般相対論的非弾性散乱過程の位相シフトを求めるアルゴリズムの開発を報告する。
論文 参考訳(メタデータ) (2024-07-04T21:11:05Z) - 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) - Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
安定猫量子ビットの既存システムに動機づけられたビットフリップ誤差のみに影響されるバイアスノイズ量子ビットを考察する。
現実的なノイズモデルでは、位相フリップは無視できないが、Pauli-Twirling近似では、ベンチマークが最大106ドルのゲートを含む回路の正しさを確認できる。
論文 参考訳(メタデータ) (2023-05-03T11:27:50Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - 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) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳(メタデータ) (2020-12-03T07:12:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。