Exact quantum splitting and the structure of finite algebras

Abstract

For squarefree $f\in\F_q[x]$, Berlekamp's fixed-point algebra is $B\cong\F_q^r$, where $r$ is the number of irreducible factors. We give an exact quantum splitting procedure in a circuit model permitting efficiently computable, input-dependent single-qubit rotations. For a block with $s\ge 2$ factors, a quadratic-character test (odd $q$) or absolute-trace test (characteristic $2$) is nonconstant with an exactly known probability $p_{q,s}\ge 1/2$. Its value depends only on $q,s$, not on the hidden factors. An auxiliary-qubit reduction to success probability $1/4$ makes one Grover iteration exact. Thus factorization takes exactly $r-1$ splitting rounds and $O(n^3\log q)$ quantum $\F_q$-operations, with deterministic polynomial classical preprocessing and bookkeeping. The method also extracts primitive idempotents of arbitrary finite-dimensional commutative unital algebras given by structure constants in $O(n^4\log q)$ quantum $\F_q$-operations, staying over $\F_q$ throughout. Computing the radical and passing to the center extends it to the decomposition of $A/\Rad(A)$ into simple two-sided ideals, for an arbitrary finite-dimensional associative $\F_q$-algebra $A$.