Exact quantum splitting and the structure of finite algebras

For squarefree f in q[x], Berlekamp's fixed-point algebra is B 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 2 factors, a quadratic-character test (odd q) or absolute-trace test (characteristic 2) is nonconstant with an exactly known probability p q,s 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 cubed q) quantum 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 q) quantum q-operations, staying over q throughout. Computing the radical and passing to the center extends it to the decomposition of A/ (A) into simple two-sided ideals, for an arbitrary finite-dimensional associative q-algebra A.