論文の概要: Deterministic Algorithms for the Hidden Subgroup Problem
- arxiv url: http://arxiv.org/abs/2104.14436v3
- Date: Fri, 10 Jun 2022 20:49:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-02 02:00:39.915815
- Title: Deterministic Algorithms for the Hidden Subgroup Problem
- Title（参考訳）: 隠れ部分群問題の決定論的アルゴリズム
- Authors: Ashwin Nayak
- Abstract要約: 隠れ部分群問題に対する決定論的アルゴリズムを提案する。
アーベル群の場合、第1のアルゴリズムは最適なランダム化アルゴリズムと同じ最悪のクエリ複雑性を達成する。
非アーベル群に対する類似アルゴリズムは、最適ランダム化クエリの複雑さの$sqrt log n$ factorの範囲内にある。
- 参考スコア（独自算出の注目度）: 3.2590610391507444
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present deterministic algorithms for the Hidden Subgroup Problem. The
first algorithm, for abelian groups, achieves the same asymptotic worst-case
query complexity as the optimal randomized algorithm, namely O($\sqrt{ n}\,$),
where $n$ is the order of the group. The analogous algorithm for non-abelian
groups comes within a $\sqrt{ \log n}$ factor of the optimal randomized query
complexity. The best known randomized algorithm for the Hidden Subgroup Problem
has expected query complexity that is sensitive to the input, namely O($\sqrt{
n/m}\,$), where $m$ is the order of the hidden subgroup. In the first version
of this article (arXiv:2104.14436v1 [cs.DS]), we asked if there is a
deterministic algorithm whose query complexity has a similar dependence on the
order of the hidden subgroup. Prompted by this question, Ye and Li
(arXiv:2110.00827v1 [cs.DS]) present deterministic algorithms for abelian
groups which solve the problem with O($\sqrt{ n/m }\,$ ) queries, and find the
hidden subgroup with O($\sqrt{ n (\log m) / m} + \log m$) queries. Moreover,
they exhibit instances which show that in general, the deterministic query
complexity of the problem may be o($\sqrt{ n/m } \,$), and that of finding the
entire subgroup may also be o($\sqrt{ n/m } \,$) or even $\omega(\sqrt{ n/m }
\,)$. We present a different deterministic algorithm for the Hidden Subgroup
Problem that also has query complexity O($\sqrt{ n/m }\,$) for abelian groups.
The algorithm is arguably simpler. Moreover, it works for non-abelian groups,
and has query complexity O($\sqrt{ (n/m) \log (n/m) }\,$) for a large class of
instances, such as those over supersolvable groups. We build on this to design
deterministic algorithms to find the hidden subgroup for all abelian and some
non-abelian instances, at the cost of a $\log m$ multiplicative factor increase
in the query complexity.
- Abstract（参考訳）: 隠れ部分群問題に対する決定論的アルゴリズムを提案する。
最初のアルゴリズムは、アーベル群に対して、最適なランダム化アルゴリズムである o($\sqrt{ n}\,$) と同じ漸近的最悪ケースクエリ複雑性を達成する。
非可換群に対する類似のアルゴリズムは、最適なランダム化クエリ複雑性の $\sqrt{ \log n}$ factor に含まれる。
隠れ部分群問題の最もよく知られたランダム化アルゴリズムは、入力に敏感なクエリ複雑性、すなわち o($\sqrt{ n/m}\,$) であり、ここで$m$ は隠れ部分群の順序である。
この記事の最初のバージョン(arXiv:2104.14436v1 [cs.DS])では、クエリの複雑さが隠されたサブグループの順序に類似した依存性を持つ決定論的アルゴリズムが存在するかどうかを問う。
この質問によって、Ye と Li (arXiv:2110.00827v1 [cs.DS]) は、O($\sqrt{ n/m }\,$ ) クエリで問題を解くアーベル群に対する決定論的アルゴリズムを示し、O($\sqrt{ n (\log m) / m} + \log m$) クエリで隠れた部分群を見つける。
さらに、それらは一般に、問題の決定論的クエリ複雑性が o($\sqrt{ n/m } \,$) であることを示し、部分群全体の検索は o($\sqrt{ n/m } \,$) あるいは $\omega(\sqrt{ n/m } \,)$ であることも示している。
我々は、アベル群に対するクエリ複雑性 O($\sqrt{ n/m }\,$) を持つ隠れ部分群問題に対して異なる決定論的アルゴリズムを提案する。
アルゴリズムは間違いなくシンプルです。
さらに、非可換群に対しても機能し、スーパーソルバブル群上のインスタンスのような大きなインスタンスクラスに対するクエリ複雑性o($\sqrt{ (n/m) \log (n/m) }\,$)を持つ。
これに基づいて決定論的アルゴリズムを設計し、全てのアーベルおよびいくつかの非アーベルインスタンスの隠れ部分群を見つける。
関連論文リスト
- Clustering with Non-adaptive Subset Queries [16.662507957069813]
クエリ $S の部分集合 U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。
ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$Theta(nk)$であることが知られている。
非適応スキームは$Omega(n2)$クエリを必要とするが、これは全ての点を問合せすることで得られる自明な$O(n2)$上限と一致する。
論文 参考訳（メタデータ） (2024-09-17T05:56:07Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - 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) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Fast Classical and Quantum Algorithms for Online $k$-server Problem on
Trees [0.19573380763700712]
木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。
Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。
本稿では,前処理に要するO(nlog n)$時間複雑性を持つ新しい時間効率アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-08-01T14:21:45Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Quantum Algorithms for the Most Frequently String Search, Intersection
of Two String Sequences and Sorting of Strings Problems [0.0]
弦の3つの問題を解くアルゴリズムについて研究する。
1つ目は、最も頻度の高い文字列検索問題である。
2つ目は、2つの弦列の交叉である。
第三の問題は長さ$k$の$n$文字列をソートすることだ。
論文 参考訳（メタデータ） (2020-01-07T07:22:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。