Pauli Decomposition by Character Theory: A Memory-Bounded Algorithm for Qubits and Qudits

Abstract:Pauli decomposition underpins Trotterization, phase estimation, sparse-Hamiltonian simulation, and variational observables, at exponential naive cost. From the character theory of $(\mathbb{Z}_2)^n$, characters $\chi_z(v)=(-1)^{\langle v,z\rangle}$ are the diagonal Pauli strings, so any diagonal operator is already Pauli-decomposed. A general operator still needs the shifts: each $X^{\otimes x}$ couples to a character $\chi_z=Z^{\otimes z}$, and the products $X^{\otimes x}Z^{\otimes z}$ -- up to phases in $\{\pm 1,\pm i\}$ -- form the Pauli group, the central extension of $(\mathbb{Z}_2)^n\times(\mathbb{Z}_2)^n$ by that phase group fixed by the symplectic pairing. A section of that extension remains a choice: the bare products $X^{\otimes x}Z^{\otimes z}$, or the genuine operators that insert $Y=iXZ$ at every qubit where $x$ and $z$ overlap. As Fourier analysis on an abelian shift-character lattice (a natural DFT), this formulation is not qubit-bound: $(\mathbb{Z}_p)^n$ recovers Heisenberg-Weyl qudits. The fast algorithm is the FFT for the group at hand; on $(\mathbb{Z}_2)^n$ that FFT is Walsh-Hadamard, at cost $O(n\cdot 4^n)$. paulikit is a memory-bounded realization of that qubit transform: peak usage need not materialize the dense $2^n\times 2^n$ operator, unlike prior codes whose $O(1)$ extra sits on that buffer, checked beyond a billion oscillator terms against Work-Span and bandwidth ceilings.

29 pages, 4 figures. Open-source companion: paulikit (GPL-3.0-or-later), Zenodo https://doi.org/10.5281/zenodo.22992251%3B measurements https://doi.org/10.5281/zenodo.22992460

arXiv:2610.08299 [quant-ph]

(or arXiv:2610.08299v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.08299 arXiv-issued DOI via DataCite (pending registration)