Quantum algorithm finds hidden matrix group structures over finite rings
Hidden parabolic subgroups of $\mathrm{GL}_n$ over finite chain rings
Computational Complexity
Summary
The paper presents a quantum algorithm that efficiently finds special hidden subgroups inside certain matrix groups defined over finite ring structures. These hidden subgroups relate to nested sequences of subspaces, called flags, and the algorithm uncovers them by cleverly combining classical and quantum steps. The method works for a broad class of finite rings including modular integers and ring extensions relevant in number theory. This advances understanding of how quantum computing can solve complex hidden subgroup problems beyond basic abelian cases.
What this means in practice
- •For quantum algorithm developers: Develop quantum algorithms targeting matrix group problems over finite rings important for cryptography and coding theory.
- •For cryptographic engineers: Analyze security assumptions involving linear algebraic structures mod N using advanced quantum hidden subgroup algorithms.
Authors
Muhammad Imran
Abstract
We give a bounded-error quantum polynomial-time algorithm for finding hidden parabolic subgroups of $\mathrm{GL}_n(R)$ over any effectively presented finite chain ring $R$. We call auxiliary group elements or subgroups used to extract information through oracle queries \emph{probes}. For chain length at least two, elementary abelian socle probes first recover the complete flag modulo the maximal ideal. When the residue field has size $q\ge3$, we reconstruct the flag recursively, lifting rank-one terminal members one digit at a time. The intermediate digits reduce to abelian hidden subgroup problems, while the final digit is a finite-field multiple-shift problem solved using learning from subset and Fourier sampling. For $q=2$, where distinct flags can have the same stabilizer, we instead lift the conjugate parabolic subgroup through the congruence filtration. A final linear system determines it modulo normalizer directions. The algorithm outputs generators with probability at least $1-ε$ in time $\mathrm{poly}(n,\log|R|,\log(1/ε))$. Consequences include $\mathrm{GL}_n(\mathbb{Z}/N\mathbb{Z})$ for every $N\ge2$ and, with an explicit maximal-order presentation, $\mathrm{GL}_n(\mathcal{O_K}/N\mathcal{O_K})$ for number fields $K$.