Fugu-MT 論文翻訳(概要): A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem

論文の概要: A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem

arxiv url: http://arxiv.org/abs/2202.09697v2
Date: Wed, 23 Feb 2022 14:39:27 GMT
ステータス: 処理完了
システム内更新日: 2023-02-24 11:57:19.168922
Title: A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem
Title（参考訳）: 二面隠れ部分群問題に対する量子多項式時間解
Authors: Matthew Moore and Grace Young
Abstract要約: 我々は、$mathbbD_2n$上の隠れ部分群問題に対する時空量子アルゴリズムを提案する。問題のコドメインにエンコードされた構造に着目して、隠れた部分群で$mathbbD_2n$終了する部分群格子を「ウォーク」するアルゴリズムを開発する。
参考スコア（独自算出の注目度）: 1.189332466445755
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present a polynomial-time quantum algorithm for the Hidden Subgroup Problem over $\mathbb{D}_{2^n}$. The usual approach to the Hidden Subgroup Problem relies on harmonic analysis in the domain of the problem, and the best known algorithm using this approach has time complexity in $2^{\mathcal{O}(\sqrt{n})}$. By focusing on structure encoded in the codomain of the problem, we develop a polynomial-time algorithm which uses this structure to direct a "walk" down the subgroup lattice of $\mathbb{D}_{2^n}$ terminating at the hidden subgroup.
Abstract（参考訳）: 我々は,$\mathbb{d}_{2^n}$ 上の隠れ部分群問題に対する多項式時間量子アルゴリズムを提案する。隠れた部分群問題に対する通常のアプローチは、問題の領域における調和解析に依存しており、このアプローチを用いた最もよく知られたアルゴリズムは、2.^{\mathcal{O}(\sqrt{n})}$で時間複雑性を持つ。問題のコドメインにエンコードされた構造に焦点をあてて、この構造を用いて隠れ部分群を終端する$\mathbb{d}_{2^n}$の部分群格子の「ウォーク」を指示する多項式時間アルゴリズムを開発した。

関連論文リスト

Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions [6.487242614495099]
RLWE(Ring Learning With Errors)問題とPLWE(Polynomial Learning With Errors)問題との等価性を実証する。また、最大実部分体の環内の2つの要素の積を計算するための高速整数についても述べる。
論文参考訳（メタデータ） (2024-10-01T15:32:02Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Zero sum subsequences and hidden subgroups [2.5204420653245245]
我々は、nilpotent group 内の隠れ部分群問題を、中心級数のメンバーによって商群内の部分群とそのイメージに変換することで解決する。この画像を知ることで、隠れた部分群が完全群でない限り、適切な部分群に降下することができる。フィールドのサイズが一定である場合、後者の問題に対する新しい決定論的時間アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-04-17T15:40:30Z)
Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文参考訳（メタデータ） (2023-01-04T04:15:40Z)
Computing a Group Action from the Class Field Theory of Imaginary Hyperelliptic Function Fields [0.0]
$mathbb F_q$ 上で定義される虚超楕円曲線のヤコビアンは、ドリンフェルト加群の同型類の部分集合に作用する。これは、Couveignes-Rostovtsev-Stolbunov群作用の関数場類似体である。群作用を反転する問題は、Drynfeld $mathbb F_q[X]$-加群の間の固定された$tau$-次数の同種関係を見つける問題を減少させる。
論文参考訳（メタデータ） (2022-03-14T10:11:35Z)
The dihedral hidden subgroup problem [0.0]
有限群に対する標準部分群量子アルゴリズムの観点から、二面体群に対する隠れた問題の例を示す。二面体コセット問題と量子状態のクローンとの新たな接続について説明する。
論文参考訳（メタデータ） (2021-06-18T04:19:10Z)
A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文参考訳（メタデータ） (2021-04-19T17:21:54Z)
Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文参考訳（メタデータ） (2021-03-03T22:42:15Z)
A new quantum algorithm for the hidden shift problem in $\mathbb{Z}_{2^t}^n$ [0.0]
k$が2のパワーであり、$nlog (k) で実行されている場合の解決策を提供します。一般的には、隠れたシフトや隠れた問題にも役立ちます。
論文参考訳（メタデータ） (2021-02-08T13:01:33Z)
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文参考訳（メタデータ） (2020-12-14T18:14:08Z)
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文参考訳（メタデータ） (2020-06-22T17:53:54Z)

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