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

Pauli decomposition underpins Trotterization, phase estimation, sparse-Hamiltonian simulation, and variational observables, at exponential naive cost. From the character theory of (Z 2) n, characters χ z(v)=(-1) v,z are the diagonal Pauli strings, so any diagonal operator is already Pauli-decomposed. A general operator still needs the shifts: each X x couples to a character χ z=Z z, and the products X xZ z -- up to phases in plus or minus 1, plus or minus i -- form the Pauli group, the central extension of (Z 2) n times(Z 2) n by that phase group fixed by the symplectic pairing. A section of that extension remains a choice: the bare products X xZ 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: (Z p) n recovers Heisenberg-Weyl qudits. The fast algorithm is the FFT for the group at hand; on (Z 2) n that FFT is Walsh-Hadamard, at cost O(n times 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.