Fugu-MT 論文翻訳(概要): Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms

論文の概要: Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms

arxiv url: http://arxiv.org/abs/2404.16450v1
Date: Thu, 25 Apr 2024 09:30:19 GMT
ステータス: 処理完了
システム内更新日: 2024-04-26 14:19:10.431097
Title: Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms
Title（参考訳）: 離散対数分解と計算のための最近の量子アルゴリズムの無条件正当性
Authors: Cédric Pilatte,
Abstract要約: 2023年、レジチェフはショアのアルゴリズムの多次元バージョンを提案し、より少ない量子ゲートを必要とした。解析的数論の道具を用いて、この予想のバージョンを証明する。その結果、この改良された量子アルゴリズムの正確性の無条件証明が得られる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multi-dimensional version of Shor's algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in $(\mathbb{Z}/N\mathbb{Z})^{\times}$ that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such as zero-density estimates. As a result, we obtain an unconditional proof of correctness of this improved quantum algorithm and of subsequent variants.
Abstract（参考訳）: 1994年、ショアは整数を分解し、多項式時間で離散対数を計算するために有名な量子アルゴリズムを導入した。 2023年、レジチェフはショアのアルゴリズムの多次元バージョンを提案し、より少ない量子ゲートを必要とした。彼のアルゴリズムは、非常に小さな素数の短い積として記述できる$(\mathbb{Z}/N\mathbb{Z})^{\times}$の要素に関する数論的な予想に依存する。ゼロ密度推定のような解析的数論のツールを用いて、この予想のバージョンを証明する。その結果、改良された量子アルゴリズムとその後の変種に対する無条件の正当性の証明が得られる。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文参考訳（メタデータ） (2023-11-19T00:06:11Z)
Integer Factorization by Quantum Measurements [0.0]
量子アルゴリズムは、古典的コンピュータでは解けない計算問題を解くために量子力学を使うことが進行中の努力の中心である。既知の量子アルゴリズムの中で、特別な役割はShorアルゴリズム、すなわち整数分解のための量子時間アルゴリズムによって演じられる。ここでは、別の真の量子特性(量子計測)に基づく整数分解の異なるアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-09-19T17:00:01Z)
Quantum Multiplication Algorithm Based on the Convolution Theorem [0.0]
時間複雑性を持つ整数乗算の量子アルゴリズムをO(sqrtnlog2 n)$で提案する。 Harveyアルゴリズムとは異なり、我々のアルゴリズムは極大数にのみ適用できるという制限はない。また、古典的乗法アルゴリズムの歴史と発展を概観し、量子資源がこの根本的な問題に対してどのように新たな視点と可能性を提供できるかを探求する動機付けとなる。
論文参考訳（メタデータ） (2023-06-14T12:40:54Z)
Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning [35.11103784048256]
有限水平MDPの学習を容易にするために,textitUpper Confidence Bound (UCB) ベースの量子アルゴリズムフレームワークを提案する。我々の量子アルゴリズムは、古典的なアルゴリズムと比較して、後悔の指数的な改善を実現している。
論文参考訳（メタデータ） (2023-02-16T23:01:27Z)
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)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文参考訳（メタデータ） (2022-05-26T20:32:36Z)
An efficient quantum algorithm for lattice problems achieving subexponential approximation factor [2.3351527694849574]
整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
論文参考訳（メタデータ） (2022-01-31T18:58:33Z)
Basic Quantum Algorithms [0.0]
量子コンピューティングは急速に進化しており、理論の基礎を再検討し、書き直し、更新せざるを得ない。基本量子アルゴリズムは、初期の量子アルゴリズムを再考する。
論文参考訳（メタデータ） (2022-01-25T19:00:10Z)
Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
我々は、ノイズの多い量子デバイス上で分解可能な数値の範囲を拡大するステップを推し進めるShorのアルゴリズムの縮小版を導入する。特に、ほとんどのケースで注目すべき結果が得られており、しばしば提案されたアルゴリズムの1つで与えられた数を分解できる。
論文参考訳（メタデータ） (2021-12-23T15:36:59Z)

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