Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness

• URL: http://arxiv.org/abs/2609.10596v1
• Date: Mon, 07 Sep 2026 09:50:40 GMT
• Title: Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness
• Abstract summary: Several public-key schemes base their security on the belief that inverting a unit of a group ring is hard.<n>This paper shows that unit inversion is a different problem and does not require an HSP solver.<n>It can be solved by a change of basis that splits the group ring into small matrix blocks.
• Score: 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.

Related papers

• Efficient Learning and Symmetry Discovery under Exact Invariances [62.27019402162741]
  Learning with group invariances is central to many scientific and geometric learning problems.<n>It has been unclear whether one can efficiently compute a regression function that is exactly in subgroup to a given group action.<n>We present the first-time algorithm for learning with exact group invariants that applies uniformly to finite and infinite groups.
  arXiv  Detail & Related papers  (2026-09-07T04:35:19Z)
• Maximal Classicalization of Finite-Group Quantum Reference-Frame Noise [0.0]
  A finite quantum reference token with group-valued misalignment induces a random-unitary channel.<n>We prove that the following conditions are equivalent for a unitary representation U of a finite group G.
  arXiv  Detail & Related papers  (2026-07-14T17:07:57Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Highly-efficient quantum Fourier transformations for some nonabelian groups [0.0]
  We present fast quantum Fourier transformations for a number of nonabelian groups of interest for high energy physics. For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations.
  arXiv  Detail & Related papers  (2024-07-31T18:00:04Z)
• The wave function of stabilizer states and the Wehrl conjecture [0.0]
  We focus on quantum systems represented by a Hilbert space $L(A)$, where $A$ is a locally compact Abelian group that contains a compact open subgroup. We provide a complete and elegant solution to the problem of describing the stabilizer states in terms of their wave functions, an issue that arises in quantum information theory. We demonstrate that the stabilizer states are precisely the minimizers of the Wehrl entropy functional, thereby resolving the analog of the Wehrl conjecture for any such group.
  arXiv  Detail & Related papers  (2024-06-10T11:13:42Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms.<n>Intrepid permutations have so far remained a fundamental open problem.<n>We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• Learning with Errors over Group Rings Constructed by Semi-direct Product [26.148950348885972]
  Group ring LWE (GR-LWE) is an extension of the Learning with Errors (LWE) problem. As an extension of Ring-LWE, GR-LWE maintains computational hardness and can be potentially applied in many scenarios. GR-LWE samples can be leveraged to construct semantically secure public-keysystems.
  arXiv  Detail & Related papers  (2023-11-27T14:38:36Z)
• Unified Fourier-based Kernel and Nonlinearity Design for Equivariant Networks on Homogeneous Spaces [52.424621227687894]
  We introduce a unified framework for group equivariant networks on homogeneous spaces. We take advantage of the sparsity of Fourier coefficients of the lifted feature fields. We show that other methods treating features as the Fourier coefficients in the stabilizer subgroup are special cases of our activation.
  arXiv  Detail & Related papers  (2022-06-16T17:59:01Z)
• An exact quantum hidden subgroup algorithm and applications to solvable groups [2.5204420653245245]
  We present a time exact quantum algorithm for the hidden subgroup problem in $Z_mkn$. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors solvable as m.
  arXiv  Detail & Related papers  (2022-02-08T18:22:35Z)
• The dihedral hidden subgroup problem [0.0]
  We give an exposition of the hidden problem for dihedral groups from the point of view of the standard subgroup quantum algorithm for finite groups. We explain a new connection between the dihedral coset problem and cloning of quantum states.
  arXiv  Detail & Related papers  (2021-06-18T04:19:10Z)
• A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups [115.58550697886987]
  We provide a completely general algorithm for solving for the equivariant layers of matrix groups. In addition to recovering solutions from other works as special cases, we construct multilayer perceptrons equivariant to multiple groups that have never been tackled before. Our approach outperforms non-equivariant baselines, with applications to particle physics and dynamical systems.
  arXiv  Detail & Related papers  (2021-04-19T17:21:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.