Hidden parabolic subgroups of GL n over finite chain rings

arXiv:2610.28368 · quant-ph, cs.CC · Submitted 2026-10-20 · Read on arXiv

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