概要 - 無限群の隠れた部分群問題
タイトル
無限群の隠れた部分群問題
時間
2025-07-24 15:16:20
著者
{"Greg Kuperberg"}
カテゴリ
{quant-ph,cs.CC,math.GR}
リンク
http://arxiv.org/abs/2507.18499v1
PDF リンク
http://arxiv.org/pdf/2507.18499v1
概要
この論文は、有限群に焦点を当てた以前の研究を大幅に拡張し、離散無限群における隠れた群問題（HSP）を探求し、整数におけるShorの周期検出アルゴリズムとの類似性を引き出しています。 **難度結果**： * 論文は、有理数の加法群および非アーベル自由群の通常準群に対してHSPがNP難であることを示しています。 * また、擬ポリノミアルクエリコストを持つZkにおける短ベクトル問題のバージョンをHSPに間接的に還元しています。 **アルゴリズム結果**： * 論文は、隠れた群が欠損ランクまたは無限指数を持つ場合のZkにおけるHSPに対するShor-Kitaevアルゴリズムを一般化しています。 * さらに、著者自身およびRegevとPeikertの以前の研究を拡張し、アーベル隠れたシフト問題（AHShP）に対する拡張指数時間アルゴリズムを示しています。 **主要な貢献**： * **無限群**：論文は無限群におけるHSPを調査し、有限群に焦点を当てた以前の研究を大きな進展としています。 * **難度とアルゴリズム**：難度とアルゴリズムの両方の結果を提供し、問題の包括的な理解を提供しています。 * **AHShP**：論文はAHShPに対する新しいアルゴリズムを提案し、実際のアーベル群におけるHSPの解決に役立ちます。 **影響**： * 無限群におけるHSPの計算的複雑さが強調され、クラスicalアルゴリズムにとって挑戦的な問題として認識されます。 * 提案されたアルゴリズムは特定のHSPのケースに対する量子アルゴリズムを提供し、特定の問題に対する潜在的な解決策を示しています。 * この研究は群理論のより広範な理解に寄与し、量子計算および暗号学におけるその適用に貢献しています。
推奨論文
進化性を学習アルゴリズムとしてシミュレートすること：分布敏感性、耐性、制約のトレードオフに関する経験的研究
検出されていない光子を使用した中間赤外線ハイパースペクトル画像撮影
柔軟なN-タプル弱い監督のための統一した経験的リスク最小化枠組
シロフの境界におけるリース評価と積分拡張
物理学情報に基づくニューラルオペレータ（PINO）を使用して連結されたAllen-CahnとCahn-Hilliard相場方程式を学習する
2025年インタースピーチ音声アクセスプロジェクトチャレンジ
「型IIIのアスペクトの仮説検定における強い逆の対数率」
神経形态計算：時間、空間、エネルギースケーリングのための理論的枠組み
非屏蔽環境で動作するMRIスキャナーに対する電磁干渉を減少させるための主題の接地
UI-AGILE：効果的な強化学習と正確な推論時の根拠化によるGUIエージェントの進化