論文の概要: The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups

• arxiv url: http://arxiv.org/abs/2608.05321v1
• Date: Wed, 05 Aug 2026 18:25:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-07 15:25:20.774579
• Title: The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups
• Title（参考訳）: 半直積と準ハミルトニアン群における隠れ部分群問題
• Abstract要約: いくつかの初期の量子アルゴリズムは有限アーベル群上の隠れ問題(HSP)の例である。 自由時間量子モジュラリティは、任意の非アーベル有限群上の HSP で知られている。 入力構造に対する軽度の仮定の下で、有限準ハミルトニアン群に対するニル時間量子アルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively. In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form $G=A\rtimes_{\varphi} \mathbb{Z}_{p^k}$, with $A$ finite Abelian, $p$ prime, $k\in \mathbb{N}$ and the action of $\mathbb Z_{p^k}$ is generated by the scalar automorphism $a\mapstoμa$, for some $μ\in\mathbb Z_{\operatorname{Exp}(A)}^\times$, where $\mathrm{Exp}(A)$ is the exponent of $A$. Our algorithm is efficient when $A$ has bounded generator rank and $\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)$. This includes the case $A=\mathbb{Z}_N$ for $N\in\mathbb{N}$ and $k=1$, studied by Bacon, Childs and van Dam (FOCS 2005), and $A=\mathbb{Z}_{q^r}$ with $q$ prime and $r\in \mathbb{N}$ studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).
• Abstract（参考訳）: シモンのアルゴリズムやショアの周期フィニングを含む初期の量子アルゴリズムは、有限アーベル群上の隠れ部分群問題(HSP)の例である。 任意の非アーベル有限群上の HSP に対して多項式時間量子アルゴリズムは知られていない。 非アベリアの場合、二面体群 HSP や対称群 HSP などは格子問題とグラフ同型にそれぞれ関係しているため、特に興味深い。 本研究では、非アベリア群を含む2つの族に対して多項式時間量子アルゴリズムを与える。 まず、$G=A\rtimes_{\varphi} \mathbb{Z}_{p^k}$, with $A$ finite Abelian, $p$ prime, $k\in \mathbb{N}$, and the action of $\mathbb Z_{p^k}$ is generated by the scalar automorphism $a\mapstoμa$, for some $μ\in\mathbb Z_{\operatorname{Exp}(A)}^\times$, where $\mathrm{Exp}(A)$ is the exponent of $A$. 我々のアルゴリズムは、$A$が有界ジェネレータランクと$\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)$を持つとき、効率的である。 例えば、$A=\mathbb{Z}_N$ for $N\in\mathbb{N}$と$k=1$、Bacon, Childs and van Dam (FOCS 2005)、$A=\mathbb{Z}_{q^r}$ with $q$ Primeと$r\in \mathbb{N}$はvan Dam and Dey (TQC 2014)である。 第二に、入力構造に対する軽度の仮定の下で、有限準ハミルトニアン群に対する多項式時間量子アルゴリズムを与える。 準ハミルトニアン群はモジュラー部分群格子を持つ有限零群、または同値に、すべての部分群が不変である有限群である。 私たちが知る限り、これはHSPを解くために部分群格子のモジュラリティを利用する最初の量子アルゴリズムである。 これは、前述の構造化された入力仮定の下で、ホールグレン、ラッセル、タ=シュマ(SIAM J. Comput. 32, 2003)によって与えられるデデキント群の量子アルゴリズムを拡張する。

関連論文リスト

• Extremal Chowla sets and their linear analogues: A human-AI mathematical investigation using Co-Scientist [0.9505505917924889]
  正確な式 $C(L/K)=[L:K]-d_max(L/K)$ を証明する。 有限体に対しては、正規基底構成を用いてすべての次数の直接証明を与える。
  論文  参考訳（メタデータ） (2026-07-25T01:46:56Z)
• Non-Invertible Symmetries Mixing with Witt Non-Trivial Quantum Cellular Automata [0.0]
  自己双対性と対称性保護位相の積み重ねは、量子多体系の基本的な操作である。 我々は、この構造全体を、ある局所作用素代数に作用する量子セルオートマトンとして顕微鏡的に実現した。
  論文  参考訳（メタデータ） (2026-07-23T18:00:00Z)
• The structure of gauge invariant Gaussian quantum operations on finite Fermion systems [0.0]
  量子演算の半群を$mathscr G_mathcal H_GIG$上で研究する。 それぞれの$etmathscr L$ は 1 対 1 であり、最初の主要な結果は $mathscr G_mathcal H_GIG$ 上のそのような量子演算の構造定理である。
  論文  参考訳（メタデータ） (2026-05-01T17:00:29Z)
• Discrete symmetries in classical and quantum oscillators [51.56484100374058]
  複素バーグマン・フォック・セガル表現において、量子ハミルトニアンの固有函数 $_n=zn$ を示す。 重ね合わせ $=sum_n c_n_n$ は、シュルディンガー方程式を解くための初期データの不完全な知識によってのみ生じる。
  論文  参考訳（メタデータ） (2026-01-05T10:04:39Z)
• Probabilistic Bounds on the Number of Elements to Generate Finite Nilpotent Groups and Their Applications [4.250782756734906]
  varphi_k(G) ge 1 - $ if $k ge operatornamerank(G) + lceil log(2/) rceil$ (グループランクに基づく境界) あるいは $k ge operatornamelen(G) + lceil log (1/) rceil$ (グループチェーンの長さに基づく境界) が証明される。
  論文  参考訳（メタデータ） (2025-11-23T12:30:46Z)
• The hidden subgroup problem for infinite groups [0.0]
  HSP は有理数の加法群と非アーベル自由群の正規部分群に対して NP-ハードであることを示す。 HSPのShorKitevアルゴリズムを標準クエリコストで$mathbbZk$で一般化する。 したがって、任意の有限生成アーベル群の HSP もまた指数時間アルゴリズムを拡張している。
  論文  参考訳（メタデータ） (2025-07-24T15:16:20Z)
• Antiparticles in non-relativistic quantum mechanics [55.2480439325792]
  非相対論的量子力学は、もともと粒子を記述するために定式化された。 量子場理論に訴えることなく、非相対論的ケースで反粒子の概念をいかに導入できるかを示す。
  論文  参考訳（メタデータ） (2024-04-02T09:16:18Z)
• 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)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。 境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。 治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2022-08-12T15:05:07Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem [1.189332466445755]
  我々は、$mathbbD_2n$上の隠れ部分群問題に対する時空量子アルゴリズムを提案する。 問題のコドメインにエンコードされた構造に着目して、隠れた部分群で$mathbbD_2n$終了する部分群格子を「ウォーク」するアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2022-02-19T23:51:15Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。 密度行列 $rho$ は可観測物の期待値から決定できると仮定される。 アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
  論文  参考訳（メタデータ） (2021-12-14T16:29:53Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)

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

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