PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact quantum splitting and the structure of finite algebras

Muhammad Imran

arXiv:2608.30340v1quant-phcs.CC

TL;DR

For large odd finite fields, efficient classical splitting is randomized, and known efficient derandomizations are conditional. The paper uses exactly known, factorization-independent test probabilities with exact amplitude amplification; the resulting algorithm factors with certainty and extends to finite-algebra structure problems.

  • Problem

    For large odd q, efficient classical polynomial splitting is randomized, while known efficient derandomizations are conditional on ERH.

    Source: §1 · p. 1

  • Method

    An unconditional counting argument supplies a test success probability known independently of the hidden factorization, allowing exact amplitude amplification to make the test certain.

    Source: Contribution · p. 2, §6 · p. 24

  • Results

    Squarefree degree-n polynomials with r irreducible factors are factored with certainty in exactly r − 1 splitting calls, using O(n^3 log q) quantum Fq-operations.

    Source: §6 · p. 24

  • Takeaways & Limitations

    The method also reaches separable commutative algebras and, through the centre, the Wedderburn decomposition of finite associative algebras.

    Source: §6 · p. 24

    The substantive gain over classical methods is confined to large odd characteristic, and exactness is stated in the EQPuC model.

    Source: §6 · p. 24

Abstract

from arXiv · show

Berlekamp's algorithm factors a squarefree polynomial $f\in\mathbb{F}_q[x]$ by deterministic linear algebra, reducing the problem to splitting an explicit commutative algebra $B\cong\mathbb{F}_q^r$ into its $r$ simple factors. For large odd $q$, the standard efficient splitting step is randomized, while known derandomizations are conditional on the Extended Riemann Hypothesis. We give an unconditional exact quantum implementation in a circuit model permitting single-qubit rotations through efficiently computable angles. The construction uses an unconditional counting argument. For a block containing $s\ge2$ irreducible factors, a quadratic-character test in odd characteristic and an absolute-trace test in characteristic $2$ yield a nonconstant test element with probability $p_{q,s}\ge\tfrac12$, known exactly in advance and depending only on $q$ and $s$, not on the unknown factorization. Exact amplitude amplification therefore converts each randomized test into a procedure succeeding with certainty after one amplification iteration. The resulting algorithm uses exactly $r-1$ quantum splitting rounds and $O(n^3\log q)$ quantum $\mathbb{F}_q$-operations and $O(n^3)$ classical operations, requiring no primitive root, quadratic non-residue, or distinct-degree preprocessing. The method also splits arbitrary finite-dimensional separable commutative $\\mathbb{F}_q$-algebras given by structure constants. Combined with R'onyai's classical structure theory, which computes the radical deterministically and reduces the remaining tasks deterministically to polynomial factorization, it yields the radical and the Wedderburn decomposition of $A/\mathrm{Rad}(A)$ into minimal two-sided ideals, with certainty, for any $n$-dimensional associative $\mathbb{F}_q$-algebra given by structure constants, using $O(n^4\log q)$ quantum $\mathbb{F}_q$-operations.

1 Introduction

For large odd finite fields, efficient classical polynomial splitting is randomized, while known derandomizations are conditional. The paper uses exactly known, factorization-independent test probabilities to make splitting exact, then extends the approach from polynomials to finite algebras.

1 Introduction

  • In large odd characteristic, every known efficient classical splitting method is randomized, and known derandomizations are conditional on ERH.The paper frames its contribution as exact derandomization, not an asymptotic speedup over randomized classical splitting.Source: §1 · p. 2

Contribution

  • An unconditional counting argument gives a test success probability known from q and the block size, so exact amplitude amplification makes each test certain.The tests use quadratic character in odd characteristic and absolute trace in characteristic 2; recursive splitting takes exactly r − 1 calls.Source: Contribution · p. 2
  • Squarefree degree-n polynomials with r irreducible factors are factored with certainty using O(n^3 log q) quantum Fq-operations, without primitive-root, quadratic-non-residue, or distinct-degree preprocessing.The construction does not rely on auxiliary exact subroutines to produce a primitive root or quadratic non-residue.Source: Contribution · p. 2
  • The test-map mechanism splits separable commutative Fq-algebras into primitive idempotents, using Lagrange interpolation rather than gcd extraction or auxiliary-extension factoring calls.The approach reaches primitive idempotents directly, unlike the classical cutting procedure through generators and minimal polynomials.Source: Contribution · p. 3
  • R’onyai’s structure theory extends the result to computing Rad(A) and decomposing A/Rad(A) into minimal two-sided ideals with certainty, using O(n^4 log q) quantum Fq-operations.The paper also treats zero divisors and explicit isomorphisms of simple components as reductions to polynomial factorization.Source: Contribution · p. 3

Relation to our earlier work

  • The explicit ring structure avoids a black-box group obstruction: group-operation tests depend only on element order, whereas this construction uses polynomial evaluation and gcd extraction.The paper notes that equal-order elements from distinct hidden factors cannot be distinguished by tests built purely from cyclic-group operations.Source: Relation to our earlier work · p. 4

2 Preliminary

The preliminaries establish the algebraic reduction behind Berlekamp factoring, the exact-amplification tool, and the circuit and cost models used for the paper’s claims.

2.1 Berlekamp’s algorithm and notation

  • Berlekamp’s subalgebra is the Frobenius-fixed part of Fq[x]/(f), computable by linear algebra and isomorphic to Fq^r, with one coordinate for each irreducible factor.The factorization problem then reduces to finding elements that distinguish those coordinates.Source: §2.1 · p. 5

2.2 Exact amplitude amplification

  • Exact amplitude amplification converts a success probability known exactly in advance into certainty, using Θ(1/√a) applications of the circuit and its inverse.The construction uses an auxiliary qubit and one efficiently computable rotation to make the probability reachable by an integer number of fixed-phase Grover iterations.Source: §2.2 · pp. 5–6

2.3 Computational model

  • The paper’s exactness claims use a circuit model permitting input-computed, efficiently computable rotation angles, with gate parameters computable in advance.Finite-field arithmetic is implemented reversibly; costs are primarily counted in Fq-operations.Source: §2.3 · p. 6
  • For classical f-algorithm reductions, the paper accounts for oracle-call counts and each polynomial’s degree and field, since extension-field calls cost more.A call over Fq^d costs d log q rather than log q in the Section 3 bounds.Source: §2.3 · p. 7

3 Main results

This section develops exact quantum splitting and factoring, from factorization-independent success probabilities and reversible implementation of the splitting test through the recursive factoring stages. It states that each split succeeds with certainty, the full algorithm uses exactly r−1 splits, and gives quantum and classical complexity bounds in the specified circuit model.

3.1 An exact, hidden-factorization-independent counting bound

  • For every block size s ≥ 2, characteristic-specific tests have an exactly known success probability from q and s alone, with p_q,s ≥ 1/2.Odd characteristic uses a quadratic-character test, while characteristic 2 uses an absolute-trace test; the trace partition is not a suitable universal choice for odd characteristic.Source: §3.1 · p. 9

3.2 The splitting oracle and the exact block-splitting lemma

  • Exact amplitude amplification produces a nonconstant test element with certainty using one application of the splitting oracle for every block with s ≥ 2.Because p_q,s lies in [1/2, 1), each invocation uses exactly one Grover iteration.Source: §3.2 · p. 10

3.3 Reversible arithmetic

  • Reversible reduction stores the discarded quotient in an ancilla, enabling reversible ring arithmetic; complexity is measured in Fq-operations, without translation to bit or gate counts.The raw product and quotient are computed into fresh registers and then uncomputed.Source: §3.3 · p. 10

3.4 The phase oracle

  • The phase oracle tests nonconstancy by checking nonconstant coefficients in O(nP) coefficient-level tests and computes its test element by repeated squaring or Frobenius-squaring.Within BP, agreement across all factor coordinates is equivalent to being a constant polynomial.Source: §3.4 · pp. 11–12
  • The phase oracle applies phase −1 exactly to nonconstant elements and uncomputes its test, with compute and uncompute costs contributing equal, not multiplicative, factors.The oracle cost is O(log q) calls to M.Source: §3.4 · p. 12

3.5 Composition across rounds

  • For every block with s ≥ 2, QuantumSplit produces a nontrivial proper partition with certainty using one splitting-oracle application and parameters determined by q and s.The success probability is known exactly and is at least 1/2; a nonconstant test element yields a proper divisor by classical gcd extraction. Reduced bases for child blocks can be recovered by Gaussian elimination.Source: §3.5 · pp. 12–13

3.7 Main theorem

  • In EQPuC circuits with efficiently computable single-qubit rotation angles, Factor(f) returns the complete factorization with certainty after exactly r−1 QuantumSplit calls.The amplitude-amplification parameters depend only on q and the current block size, not on the unknown factorization.Source: §3.7 · p. 14

3.6 Complexity

  • The total cost is O(n^3 log q) quantum F_q-operations and O(n^3) classical field operations for basis maintenance and gcd extraction.The quantum bound follows from O(r n^2 log q) operations and exactly r−1 internal splitting nodes.Source: §3.7 · p. 14, §3.6 · p. 14

4 Comparison with classical and quantum approaches

Classical splitting is already deterministic in small characteristic, but large odd characteristic remains the hard regime. The paper’s exact quantum splitting complements prior quantum work on a different factorization stage.

4.1 Comparison with classical splitting

  • For fixed small characteristic, splitting is classically deterministic; in characteristic 2, the quantum method adds uniformity and uses one amplification round instead of sweeping an F2-basis.The stated gain is practical rather than asymptotic.Source: §4.1 · pp. 14–15
  • In large odd characteristic, the procedure replaces randomized splitting exactly without ERH, auxiliary number-theoretic objects, or a √q factor, but is not asymptotically faster.The existence of deterministic polynomial-time factorization remains open even under ERH.Source: §4.1 · p. 15

4.2 Comparison with previous quantum approaches

  • The paper reports no prior quantum treatment of Berlekamp-type splitting; Draper [11] exactly constructs non-residues over prime fields, a different problem.A non-residue alone does not split a block, and Draper’s construction does not cover general Fq.Source: §4.2 · pp. 15, 17
  • Doliskani [10] uses quantum order finding for DDF but leaves EDF randomized, whereas this work makes splitting exact and performs no DDF.DDF separates factors by degree; EDF splits within equal-degree groups, while Berlekamp splitting handles arbitrary factors directly.Source: §4.2 · pp. 15–16, Figure 1 · p. 16
  • Other quantum work on quadratic characters addresses hidden-shift and reconstruction problems, not splitting the Berlekamp subalgebra.Grover-based root finding over Fp gives at most a quadratic speedup over brute force and is not comparable to this setting.Source: §4.2 · p. 17

5 Beyond polynomials: splitting finite algebras

The section extends exact quantum splitting beyond polynomial algebras, identifying the needed test-map properties and applying the method to separable commutative algebras. It also uses classical structure theory to address noncommutative finite algebras, computing the radical and decomposing the semisimple quotient, with exact procedures for finding zero divisors and constructing matrix-algebra isomorphisms.

5.1 Test maps

  • A test map must be efficiently evaluable, have a small image, and have balanced fibers; fiber balance ensures success probability above 1/2, while the other conditions bound evaluation and extraction costs.The identity map has ideal fiber balance but an image of size q, making extraction cost Θ(q).Source: §5.1 · p. 18
  • For odd q, power-residue tests offer a small image, while trace tests offer balanced fibers; characteristic two permits a trace test with both properties.For odd q, d = 2 gives the quadratic-character test; characteristic two uses the absolute-trace test. Coarsening a trace test for odd characteristic harms its fiber balance.Source: §5.1 · p. 19

5.2 The commutative case

  • In a separable commutative algebra, the Frobenius-fixed subalgebra is isomorphic to Fq^r, and the exact construction extracts primitive idempotents directly without a generating element or its minimal polynomial.Lagrange interpolation replaces polynomial gcd extraction: one successful test can split a block into as many as |T| parts by trying the values in the test map’s image.Source: §5.2 · pp. 20–21
  • With certainty, the algorithm decomposes a separable commutative algebra into its primitive idempotents in at most r - 1 splitting rounds, using O(n^4 log q) quantum Fq-operations.Its exact-amplification parameters depend only on q, the current block size, and the test map’s fiber profile, not on the unknown decomposition.Source: §5.2 · p. 21
  • The direct construction avoids extension fields and has an O(n^4 log q) bound, compared with a worst-case ˜O(n^6 log q) bound for the cutting-procedure route; neither bound is optimized.The direct method does not build a generating element and uses one splitting round per decomposition-tree node rather than one factoring call per basis vector.Source: §5.2 · p. 22

5.3 The noncommutative case

  • Removing commutativity costs only a linear system: classical structure theory reduces decomposition of an associative algebra into simple components to the corresponding problem for its centre.The passage identifies this reduction as deterministic and requiring no randomness.Source: §5.3 · p. 22
  • In positive characteristic, a trace characterization computes Rad(A) through O(log n) rounds of Gaussian elimination, deterministically and without quantum treatment.The method constructs a descending chain of ideals cut out by linear equations, replacing Dickson’s trace criterion, which can fail when the characteristic divides n.Source: §5.3 · p. 22
  • With certainty, the algorithm outputs Rad(A) and the minimal two-sided ideals of A/Rad(A) in O(n^4 log q) quantum operations and polynomial classical field operations.The input is an n-dimensional associative Fq-algebra given by structure constants.Source: §5.3 · p. 23
  • Exact procedures also find zero divisors in finite algebras and construct explicit isomorphisms from simple components to full matrix algebras over finite fields.The procedures use factoring-oracle calls and deeper noncommutative steps, including Wedderburn’s theorem, Noether–Skolem, and a norm equation; Theorem 3.14 makes them exact.Source: §5.3 · p. 23
  • No complexity bound is claimed for these procedures; a quantitative account would need to track oracle-call counts, extension fields, and factorizations used to solve norm equations.The accounting must also respect the procedure’s treatment of even degrees through descent to a degree-two subfield.Source: §5.3 · p. 23
  • Rónyai shows that finding zero divisors in finite algebras is as hard as factoring finite-field polynomials, so exact quantum structure algorithms are no easier in substance than exact polynomial factorization.A zero divisor in Fq[x]/(f) directly exhibits a proper factor of f.Source: §5.3 · p. 23

6 Conclusion

The paper’s central principle is that exact counting can make a randomized splitting test certain when its success probability is known independently of the hidden decomposition. It applies this to polynomial factorization and finite-algebra structure problems, with the substantive gain confined to exact derandomization in large odd characteristic.

6 Conclusion

  • Exact amplitude amplification turns a randomized test into a certain procedure when counting determines its success probability independently of the hidden decomposition.For a coordinate map that is a bijection, the failure probability depends on the test-map fiber sizes and block size; the paper identifies tests for which this is exact and cheap.Source: §6 · p. 24
  • A squarefree polynomial of degree n with r irreducible factors is factored with certainty using r−1 splitting calls and O(n^3 log q) quantum Fq-operations, beyond the one-off classical Berlekamp basis computation.The procedure uses no primitive root, quadratic non-residue, or distinct-degree preprocessing.Source: §6 · p. 24
  • The substantive gain over classical methods is exact derandomization for large odd characteristic, not an asymptotic speedup over classical factorization.The result is stated in the EQP_C circuit model.Source: §6 · p. 24
  • The method also splits separable commutative algebras and, through Rónyai’s reductions, yields exact structure results for finite algebras without randomized generating-element reductions or extension towers.The paper applies the method to primitive idempotents and to the decomposition of a semisimple algebra using the primitive idempotents of its centre.Source: §6 · p. 24
Loading 2608.30340v1…