Fugu-MT 論文翻訳(概要): Quantum Algorithms for Minimum Generating Set

論文の概要: Quantum Algorithms for Minimum Generating Set

arxiv url: http://arxiv.org/abs/2609.40260v1
Date: Wed, 30 Sep 2026 17:41:31 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-01 18:57:28.206378
Title: Quantum Algorithms for Minimum Generating Set
Title（参考訳）: 最小生成集合の量子アルゴリズム
Abstract要約: ブラックボックス群の最小サイズの生成集合を計算するための可解時間量子アルゴリズムを提案する。一般的なブラックボックス群に対する最小生成集合問題は、$textrmcoAM$であることを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper, we present a polynomial-time quantum algorithm for computing a minimum-sized generating set of solvable black-box groups. Next, we consider the class $Γ_d$ of black-box groups, where every non-abelian composition factor is isomorphic to a subgroup of the symmetric group $S_d$ for a fixed $d$. We design polynomial-time quantum algorithms to compute the direct product decomposition of abelian factor groups and solve the constructive membership problem for factor groups of groups from $Γ_d$. With the help of these algorithms, we design a quantum algorithm for computing a chief series of black-box groups from $Γ_d$. Using the chief series, we construct a polynomial-time quantum algorithm for computing minimum generating sets of black-box groups from $Γ_d$. Finally, we show that the minimum generating set problem for general black-box groups is in $\textrm{NP} \cap \textrm{coAM}$.
Abstract（参考訳）: 本稿では,最小サイズのブラックボックス群の生成集合を計算するための多項式時間量子アルゴリズムを提案する。次に、ブラックボックス群(英語版)( black-box group) のクラス $a_d$ を考えると、すべての非アーベル合成因子は、固定の $d$ に対して対称群 $S_d$ の部分群に同型である。我々は多項式時間量子アルゴリズムを設計し、アーベル因子群の直積分解を計算し、群全体の因子群に対する構成的メンバシップ問題を$ _d$ から解く。これらのアルゴリズムの助けを借りて、量子アルゴリズムを設計する。主級数を用いた多項式時間量子アルゴリズムは, ブラックボックス群を最小に生成する。最後に、一般的なブラックボックス群に対する最小生成集合問題は$\textrm{NP} \cap \textrm{coAM}$であることを示す。

関連論文リスト

The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups [0.0]
いくつかの初期の量子アルゴリズムは有限アーベル群上の隠れ問題(HSP)の例である。自由時間量子モジュラリティは、任意の非アーベル有限群上の HSP で知られている。入力構造に対する軽度の仮定の下で、有限準ハミルトニアン群に対するニル時間量子アルゴリズムを与える。
論文参考訳（メタデータ） (2026-08-05T18:25:25Z)
The hidden subgroup problem for infinite groups [0.0]
HSP は有理数の加法群と非アーベル自由群の正規部分群に対して NP-ハードであることを示す。 HSPのShorKitevアルゴリズムを標準クエリコストで$mathbbZk$で一般化する。したがって、任意の有限生成アーベル群の HSP もまた指数時間アルゴリズムを拡張している。
論文参考訳（メタデータ） (2025-07-24T15:16:20Z)
Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文参考訳（メタデータ） (2023-06-15T15:37:31Z)
An Algorithm for Computing with Brauer's Group Equivariant Neural Network Layers [0.0]
本稿では,各群に対する重み行列によってベクトルを乗算するアルゴリズムを提案する。提案手法は対称群である$S_n$に拡張され,その過程でarXiv:2303.06208のアルゴリズムが復元されることを示す。
論文参考訳（メタデータ） (2023-04-27T13:06:07Z)
A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem [1.189332466445755]
我々は、$mathbbD_2n$上の隠れ部分群問題に対する時空量子アルゴリズムを提案する。問題のコドメインにエンコードされた構造に着目して、隠れた部分群で$mathbbD_2n$終了する部分群格子を「ウォーク」するアルゴリズムを開発する。
論文参考訳（メタデータ） (2022-02-19T23:51:15Z)
An exact quantum hidden subgroup algorithm and applications to solvable groups [2.5204420653245245]
隠れた部分群問題に対する時間正確な量子アルゴリズムを、Z_mkn$で示す。また、位数が m と同じ(おそらく未知の)素因子を持つアーベル群と可解群の構造を計算するための応用も提示する。
論文参考訳（メタデータ） (2022-02-08T18:22:35Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)
Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。クエリを少なくすることで、問題の解決が容易になる。
論文参考訳（メタデータ） (2021-06-04T02:32:26Z)
A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文参考訳（メタデータ） (2021-04-19T17:21:54Z)
Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文参考訳（メタデータ） (2020-11-12T16:29:45Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。