Hidden parabolic subgroups of GL n over finite chain rings
quant-ph, cs.CC
Submitted: 2026-10-20
Updated: 2026-10-20
License: http://creativecommons.org/licenses/by/4.0/
The gist: We give a bounded-error quantum polynomial-time algorithm for finding hidden parabolic subgroups of GL n(R) over any effectively presented finite chain ring R.
Abstract
We give a bounded-error quantum polynomial-time algorithm for finding hidden parabolic subgroups of 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 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 3, 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 poly(n, R, (1/ε)). Consequences include GL n(Z/N Z) for every N 2 and, with an explicit maximal-order presentation, GL n(O K/N O K) for number fields K.
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Incoherent Imaging with Spatially Structured Quantum Probes
- A quasiparticle-protected superconducting qubit
- Theory of quantum-enhanced interferometry with general Markovian light sources