論文の概要: The hidden subgroup problem for infinite groups

• arxiv url: http://arxiv.org/abs/2507.18499v1
• Date: Thu, 24 Jul 2025 15:16:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-25 15:10:43.917333
• Title: The hidden subgroup problem for infinite groups
• Title（参考訳）: 無限群に対する隠れ部分群問題
• Authors: Greg Kuperberg,
• Abstract要約: HSP は有理数の加法群と非アーベル自由群の正規部分群に対して NP-ハードであることを示す。 HSPのShorKitevアルゴリズムを標準クエリコストで$mathbbZk$で一般化する。 したがって、任意の有限生成アーベル群の HSP もまた指数時間アルゴリズムを拡張している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Following the example of Shor's algorithm for period-finding in the integers, we explore the hidden subgroup problem (HSP) for discrete infinite groups. On the hardness side, we show that HSP is NP-hard for the additive group of rational numbers, and for normal subgroups of non-abelian free groups. We also indirectly reduce a version of the short vector problem to HSP in $\mathbb{Z}^k$ with pseudo-polynomial query cost. On the algorithm side, we generalize the Shor-Kitaev algorithm for HSP in $\mathbb{Z}^k$ (with standard polynomial query cost) to the case where the hidden subgroup has deficient rank or equivalently infinite index. Finally, we outline a stretched exponential time algorithm for the abelian hidden shift problem (AHShP), extending prior work of the author as well as Regev and Peikert. It follows that HSP in any finitely generated, virtually abelian group also has a stretched exponential time algorithm.
• Abstract（参考訳）: 整数における周期有限化のShorのアルゴリズムの例に続いて、離散無限群に対する隠れ部分群問題 (HSP) を探索する。 硬度側では、HSP は有理数の加法群と非アーベル自由群の正規部分群に対して NP-ハードであることを示す。 また、短ベクトル問題のバージョンを擬ポリノミカルクエリコストで$\mathbb{Z}^k$でHSPに間接的に還元する。 アルゴリズム側では、HSP に対する Shor-Kitaev アルゴリズムを $\mathbb{Z}^k$ (標準多項式クエリコスト) で一般化する。 最後に、アーベル隠れシフト問題 (AHShP) に対する指数時間拡張アルゴリズムの概要を述べる。 したがって、任意の有限生成アーベル群の HSP もまた指数時間アルゴリズムを拡張している。

関連論文リスト

• An Initialization-free Quantum Algorithm for General Abelian Hidden Subgroup Problem [0.0]
  我々のアルゴリズムは、任意の未知混合状態を補助レジスタとして適用することができる。 また,計算終了後に補助レジスタの状態を元の形式に復元する。
  論文  参考訳（メタデータ） (2025-07-24T04:50:28Z)
• The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
  この研究において、ラベルは(ガウス)$d$-次元入力にのみ依存し、低次元$r = O_d(1)$部分空間への射影を通して得られる。 生成的跳躍指数 $kstar$, [Damian et al.'24] から生成的指数の自然拡張をマルチインデックス設定に導入する。
  論文  参考訳（メタデータ） (2025-06-05T18:34:56Z)
• 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)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14: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)
• Polynomial-time quantum algorithm for solving the hidden subgroup problem [0.0]
  隠れ部分群問題(HSP)は量子計算における最も重要な問題の一つである。 我々は,HSPを,マルチステップ量子アルゴリズムによる量子アルゴリズムを用いて効率よく解けるネスト型構造化探索問題に還元できることを見出した。
  論文  参考訳（メタデータ） (2022-04-07T08:50:50Z)
• A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem [1.189332466445755]
  我々は、$mathbbD_2n$上の隠れ部分群問題に対する時空量子アルゴリズムを提案する。 問題のコドメインにエンコードされた構造に着目して、隠れた部分群で$mathbbD_2n$終了する部分群格子を「ウォーク」するアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2022-02-19T23:51:15Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• 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)
• The Hidden Subgroup Problem for Universal Algebras [0.7832189413179361]
  隠れ部分群問題(英: Hidden Subgroup Problem、HSP)は、特殊の場合の整数分解、離散離散問題、グラフ同型、最短ベクトル問題を含む計算問題である。
  論文  参考訳（メタデータ） (2020-01-30T13:09:35Z)

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

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