論文の概要: Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness
- arxiv url: http://arxiv.org/abs/2609.10596v1
- Date: Mon, 07 Sep 2026 09:50:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 23:53:35.073638
- Title: Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness
- Title（参考訳）: 群環における単位の量子反転:ブロック次元、可換性ではなく、強硬性
- Abstract要約: いくつかの公開鍵スキームは、群環の単位を反転させることは難しいという信念に基づいている。
本稿では、単位反転は異なる問題であり、HSPソルバを必要としないことを示す。
これは、群環を小さな行列ブロックに分割する基底の変化によって解決できる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Several public-key schemes base their security on the belief that inverting a unit of a group ring is hard. A recent result showed that this belief is false on a quantum computer when the group is abelian. To restore security, designers moved to non-abelian groups, especially dihedral groups, believing that the hardness of the dihedral hidden subgroup problem (HSP) would protect the scheme. This paper shows that unit inversion is a different problem and does not require an HSP solver. Instead, it can be solved by a change of basis that splits the group ring into small matrix blocks. We prove that unit inversion is polynomial-time, classically and quantumly, when an efficient generalized Fourier transform exists, the group ring is semisimple, and the largest matrix block has polynomial size. Dihedral group rings satisfy these conditions because their irreducible representations have dimension at most 2 and an efficient Fourier transform exists. We give an explicit reversible quantum circuit for the block-inversion step and validate it in a register-level simulator. We also identify the exact structural boundary where the method stops and propose a candidate construction in the surviving regime under a new, clearly stated security assumption. The constructive results are supported by reproducible software artifacts and experiments.
- Abstract（参考訳）: いくつかの公開鍵スキームは、群環の単位を反転させることは難しいという信念に基づいている。
最近の結果は、群がアーベルであるとき、この信念は量子コンピュータ上で偽であることを示した。
安全性を回復するために、設計者は非アーベル群、特に二面体群に移行し、二面体隠れ部分群問題(HSP)の硬さが計画を保護すると信じた。
本稿では、単位反転は異なる問題であり、HSPソルバを必要としないことを示す。
代わりに、群環を小さな行列ブロックに分割する基底の変更によって解ける。
我々は、単位反転が多項式時間、古典的かつ量子的に証明し、効率的な一般化フーリエ変換が存在するとき、群環は半単純であり、最大の行列ブロックは多項式サイズである。
双面群環は、それらの既約表現が少なくとも 2 次元を持ち、効率的なフーリエ変換が存在するため、これらの条件を満たす。
ブロック反転ステップに対して、明示的な可逆量子回路を提供し、レジスタレベルのシミュレータで検証する。
また, 本手法が停止する正確な構造境界を同定し, 新たなセキュリティ仮定の下で, 生存体制における候補構築を提案する。
建設結果は再現可能なソフトウェアアーティファクトと実験によって支えられている。
関連論文リスト
- Efficient Learning and Symmetry Discovery under Exact Invariances [62.27019402162741]
群不変性による学習は多くの科学的および幾何学的な学習問題の中心である。
与えられた群作用のちょうど部分群にある回帰関数を効率的に計算できるかどうかは不明である。
有限群と無限群に一様に適用する正確な群不変量を持つ学習アルゴリズムを初めて提案する。
論文 参考訳（メタデータ） (2026-09-07T04:35:19Z) - Maximal Classicalization of Finite-Group Quantum Reference-Frame Noise [0.0]
グループ値のミスアライメントを持つ有限量子参照トークンは、ランダムなユニタリチャネルを誘導する。
以下の条件が有限群 G のユニタリ表現 U に等しいことを証明している。
論文 参考訳（メタデータ） (2026-07-14T17:07:57Z) - Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。
本手法の様々な応用は, 微分問題を解く文脈で論じる。
論文 参考訳（メタデータ） (2026-02-11T07:24:33Z) - Average-case quantum complexity from glassiness [45.57609001239456]
グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。
レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、ギブスサンプリングのための安定な量子アルゴリズムを妨げていることを証明している。
論文 参考訳（メタデータ） (2025-10-09T17:37:33Z) - Highly-efficient quantum Fourier transformations for some nonabelian groups [0.0]
我々は、高エネルギー物理学に対する多くの非アーベル群に対する高速量子フーリエ変換を示す。
各グループに対して、明示的な量子回路とフォールトトレラント実装のリソーススケーリングを導出する。
論文 参考訳（メタデータ） (2024-07-31T18:00:04Z) - The wave function of stabilizer states and the Wehrl conjecture [0.0]
我々はヒルベルト空間$L(A)$で表される量子系に焦点を当て、$A$はコンパクトな開部分群を含む局所コンパクトなアベリア群である。
量子情報理論において生じる問題である波動関数の観点から安定化状態を記述する問題に対する完全かつエレガントな解を提供する。
安定化状態がWehrlエントロピー汎函数の極小値であることを示し、したがってそのような群に対するWehrl予想の類似を解消する。
論文 参考訳（メタデータ） (2024-06-10T11:13:42Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Learning with Errors over Group Rings Constructed by Semi-direct Product [26.148950348885972]
グループリング LWE (GR-LWE) はLearning with Errors (LWE) 問題の拡張である。
Ring-LWEの拡張として、GR-LWEは計算硬度を維持し、多くのシナリオに適用することができる。
GR-LWEサンプルはセマンティックにセキュアな公開鍵システムを構築するために利用することができる。
論文 参考訳（メタデータ） (2023-11-27T14:38:36Z) - Unified Fourier-based Kernel and Nonlinearity Design for Equivariant
Networks on Homogeneous Spaces [52.424621227687894]
等質空間上の群同変ネットワークに対する統一的枠組みを導入する。
昇降した特徴場のフーリエ係数の空間性を利用する。
安定化部分群におけるフーリエ係数としての特徴を取り扱う他の方法が、我々のアクティベーションの特別な場合であることを示す。
論文 参考訳（メタデータ） (2022-06-16T17:59:01Z) - An exact quantum hidden subgroup algorithm and applications to solvable
groups [2.5204420653245245]
隠れた部分群問題に対する時間正確な量子アルゴリズムを、Z_mkn$で示す。
また、位数が m と同じ(おそらく未知の)素因子を持つアーベル群と可解群の構造を計算するための応用も提示する。
論文 参考訳（メタデータ） (2022-02-08T18:22:35Z) - The dihedral hidden subgroup problem [0.0]
有限群に対する標準部分群量子アルゴリズムの観点から、二面体群に対する隠れた問題の例を示す。
二面体コセット問題と量子状態のクローンとの新たな接続について説明する。
論文 参考訳（メタデータ） (2021-06-18T04:19:10Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。
他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。
提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文 参考訳（メタデータ） (2021-04-19T17:21:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。