論文の概要: Efficient quantum processing of ideals in finite rings
- arxiv url: http://arxiv.org/abs/0908.0022v2
- Date: Wed, 5 Jul 2023 17:22:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-09 14:18:03.686820
- Title: Efficient quantum processing of ideals in finite rings
- Title(参考訳): 有限環におけるイデアルの効率的な量子処理
- Authors: Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi, and Joseph P.
Brennan
- Abstract要約: ポリ(log |R|)時間において、I に対して加法基底表現を求める方法を示す。
このアルゴリズムは、量子コンピュータが有限環に関する様々な問題を迅速に解くことができる有用なプリミティブであることを示す。
- 参考スコア(独自算出の注目度): 1.1724565818034947
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Suppose we are given black-box access to a finite ring R, and a list of
generators for an ideal I in R. We show how to find an additive basis
representation for I in poly(log |R|) time. This generalizes a quantum
algorithm of Arvind et al. which finds a basis representation for R itself. We
then show that our algorithm is a useful primitive allowing quantum computers
to rapidly solve a wide variety of problems regarding finite rings. In
particular we show how to test whether two ideals are identical, find their
intersection, find their quotient, prove whether a given ring element belongs
to a given ideal, prove whether a given element is a unit, and if so find its
inverse, find the additive and multiplicative identities, compute the order of
an ideal, solve linear equations over rings, decide whether an ideal is
maximal, find annihilators, and test the injectivity and surjectivity of ring
homomorphisms. These problems appear to be hard classically.
- Abstract(参考訳): 有限環 R へのブラックボックスアクセスと R のイデアル I に対する生成元のリストが与えられると仮定する。
これは、arvind et al. の量子アルゴリズムを一般化し、r 自体の基底表現を求める。
そして,本アルゴリズムは,有限環に関する様々な問題を量子コンピュータが迅速に解くための有用なプリミティブであることを示す。
特に、2つのイデアルが同一であるかどうかを検証し、それらの交叉を見つけ、与えられた環要素が与えられたイデアルに属するかどうかを証明し、ある元が単位であるかどうかを証明し、その逆元を見つけると、加法的および乗法的アイデンティティを見つけ、イデアルの順序を計算し、環上の線型方程式を解き、イデアルが極大であるかどうかを判定し、アニヒレータを見つけ、環準同型の射影と全射性をテストする方法を示す。
これらの問題は古典的には難しい。
関連論文リスト
- Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings [0.0]
我々は、標数 p の超特異楕円曲線の自己準同型環を計算する決定論的時間アルゴリズムを与える。
我々は、局所自己同型環に向かうために高次元同相の技法を用いる。
論文 参考訳(メタデータ) (2024-02-07T18:10:54Z) - The supersingular endomorphism ring problem given one endomorphism [5.01069065110753]
我々は、E の自己準同型環が古典的時間で計算できることを証明した。
また、楕円曲線上の滑らかなイデアルの作用が時間内に計算できることも証明する。
論文 参考訳(メタデータ) (2023-09-21T09:22:43Z) - Embedding Integer Lattices as Ideals into Polynomial Rings [29.240943119083678]
さらに、イデアル格子の付加構造を研究し、その係数を埋め込むことで、与えられたイデアル格子をイデアルとして無限に多くの異なる環に埋め込むことができる。
Ding と Lindner のアルゴリズムには、ある理想的な格子をそれらのアルゴリズムで特定できない欠陥がある。
論文 参考訳(メタデータ) (2023-07-24T03:06:49Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳(メタデータ) (2023-06-21T17:03:22Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳(メタデータ) (2023-05-22T17:43:34Z) - Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
種々の非重み付きグラフの集合上でガウス過程の先行を定義するための原理的手法を提案する。
さらに、未重み付きグラフの同値類の集合を検討し、それに対する事前の適切なバージョンを定義する。
化学の応用に触発されて、我々は、小データ構造における実際の分子特性予測タスクについて、提案手法を解説した。
論文 参考訳(メタデータ) (2022-11-03T10:18:17Z) - An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor [2.3351527694849574]
整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。
量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。
この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
論文 参考訳(メタデータ) (2022-01-31T18:58:33Z) - Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
従来の計算手法は、半定値の標準的なプログラミング技術に基づいていた。
確率分布が均一な量子ビットアンサンブルの量子推定処理を計算すれば、よりクワッドラティックなスピードアップがもたらされることを示す。
例として、正則および準正則なクォービット状態集合の推理を計算する。
論文 参考訳(メタデータ) (2021-12-03T01:24:57Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳(メタデータ) (2021-06-04T02:32:26Z) - Subgroup-based Rank-1 Lattice Quasi-Monte Carlo [51.877197074344586]
グループ理論に基づく単純な閉形式ランク1格子構築法を提案する。
本手法は,ベンチマーク統合テスト問題とカーネル近似問題において,優れた近似性能を実現する。
論文 参考訳(メタデータ) (2020-10-29T03:42:30Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。