Exact quantum splitting and the structure of finite algebras

• URL: http://arxiv.org/abs/2608.30340v1
• Date: Mon, 31 Aug 2026 06:56:14 GMT
• Title: Exact quantum splitting and the structure of finite algebras
• Abstract summary: Berlekamp's algorithm factors a squarefree $finmathbbF_q[x]$ by deterministic linear algebra.<n>We give an unconditional exact quantum implementation in a circuit model permitting single-qubit rotations through efficiently computable angles.
• Score: 1.7277199466514768
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing [0.0]
  We achieve query-optimal quantum simulations of non-Hermitian Hamiltonians $H_mathrmeff = H_R + iH_I$, where $H_R$ is Hermitian and $H_I succeq 0$.
  arXiv  Detail & Related papers  (2026-05-12T17:40:56Z)
• Quantum Mechanics from Finite Graded Equality [0.40611352512781856]
  We propose that quantum mechanics follows from a single hypothesis: equality has finite resolution.<n>We formalize the first two axioms as axioms; a structural Leibniz condition within the saturation axiom forces permutation invariance of basis elements.<n>Local tomography follows from $mathbbF = mathbbC$ with tensor product composition.
  arXiv  Detail & Related papers  (2026-03-12T13:14:48Z)
• Diffusion Computation versus Quantum Computation: A Comparative Model for Order Finding and Factoring [0.0]
  We study a hybrid computational model for integer factorization in which the only non-classical resource is access to an emphiterated diffusion process on a finite graph.<n>Our comparison with Shor's algorithm is emphconceptual and model-based.<n>We report complexity in two cost measures: digital steps and diffusion steps.
  arXiv  Detail & Related papers  (2026-01-05T19:45:38Z)
• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices.<n>We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Infinite quantum signal processing [0.6808803980072229]
  Quantum signal processing (QSP) represents a real scalar of degree $d$.<n>We show that QSP can be used to represent a large class of non-polynomial functions.<n>Our analysis reveals a surprising connection between the regularity of the target function and the decay properties of the factors.
  arXiv  Detail & Related papers  (2022-09-21T07:50:26Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  We focus on the measurement defined by the decomposition based on Schur-Weyl duality on $n$ qubits. We derive various types of distribution including a kind of central limit when $n$ goes to infinity.
  arXiv  Detail & Related papers  (2021-04-26T15:03:08Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  We give a learning algorithm for an arithmetic circuit model from a lower bound for the same model, provided certain non-degeneracy conditions hold. Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from a lower bound for the same model.
  arXiv  Detail & Related papers  (2020-04-15T06:18:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.