CS Paper Radar

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

Mohammadreza Khellat, Mohammad Masoumi, Saman Nasoori, Soroush Nasoori

cs.MS quant-ph ·submitted 2026-10-06 13:03 UTC · v3

Abstract

Pauli decomposition of an $n$-qubit operator is expensive if each of the $4^n$ Pauli strings is treated as an unstructured object. Labeling those strings by the configuration space $(\mathbb{Z}_2)^n$ makes them displacement operators $X^{\otimes x}Z^{\otimes z}$ on the computational space: shifts by~$x$ and multiplications by characters $Z^{\otimes z}$ in the computational basis. That labeling organizes the operator into $2^n$ fibers of length $2^n$, one per shift~$x$, each collecting the computational-basis amplitudes that hop by~$x$. Expanding each fiber function in the character basis of $(\mathbb{Z}_2)^n$ --- a length-$2^n$ Walsh--Hadamard transform --- recovers the Pauli coefficients at total cost $O(n\cdot4^n)$. The same fiber / shift--character picture extends to $(\mathbb{Z}_p)^n$ (Heisenberg--Weyl qudits). \texttt{paulikit} is a memory-bounded realization for qubits: for matrix-sparse inputs, peak memory need not densify to a full $2^n\times2^n$ operator. Performance is checked on a stated low-end GNU/Linux platform for a coupled-oscillator sweep beyond a billion Pauli terms.

Comment
23 pages, 4 figures. Corrected oscillator Hamiltonian (paulikit 0.1.4); remesured tables. Zenodo 10.5281/zenodo.23972284 (software), 10.5281/zenodo.24030142 (measurements)

Closest papers

Nearest neighbours by meaning across the whole index.

Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation

cs.ET quant-ph ·2026-09-08 ·Cesar Augusto do Amaral, Nicolás Legnazzi, Marcos Vinicius Reballo, Marcus Ritt, Alexsandro Santos da Rosa Júnior +1 more
similarity 0.59
Abstract

We introduce a sparse Walsh-Pauli correlation encoding for MaxCut, in which graph variables are represented by diagonal Pauli-string expectation values computed classically as normalized XOR autocorrelations of Walsh coefficients. The complete Walsh basis can reproduce the diagonal correlators of arbitrary quantum states, while a structured sparse support reduces the number of trainable coefficients to $m+1$ for $m$ graph variables. We evaluate the method on $1{,}400$ held-out random graphs with up to $7{,}000$ vertices, obtaining empirical approximation ratios near $0.98$ relative to MQLib heuristic references. On Gset instances G14, G23, G60, and G64, the sparse model achieves mean refined approximation ratios of $0.9828$, $0.9926$, $0.9781$, and $0.9369$, respectively, with $80.4\%$-$89.3\%$ fewer parameters than the complete Walsh representation. The trained coefficients are transferred without retraining to quantum circuits. Statevector simulations of the four Gset instances achieve fidelities above $0.99994$ and preserve all correlator signs. Separately, a seven-qubit experiment on a $15$-vertex graph executed on IBM quantum hardware achieves a correlator-sign agreement of $0.927\pm0.049$ relative to the corresponding noiseless circuit. These results demonstrate the potential of sparse Walsh-PCE for large-instance quantum-inspired MaxCut optimization while validating the transfer of classically trained parameters to quantum hardware.

0.25

Quantum codes in the Lee metric

cs.IT quant-phmath.COmath.MG ·2026-10-04 ·Jinkang Guo, Yiqiu Han, Aranya Chakraborty, Shubham P. Jain, Tianhao Liu +2 more
theory similarity 0.56
Abstract

We introduce a quantum coding framework for discrete small-shift noise, in which errors on qudits are modeled as low-weight $X$- and $Z$-type Pauli shifts, analogous to small phase-space displacements in continuous-variable systems. This structure is approximately respected by nuclear-spin noise and captured by the Lee metric, motivating a quantum extension of classical Lee-metric coding theory. We develop such a formalism for stabilizer codes over $\mathbb{Z}_q$ for arbitrary $q$, using joint and separate Lee metrics for the $X$- and $Z$-components of errors. For qubits, the joint metric counts $Y$ errors twice and can yield codes that detect and correct $X$ and $Z$ errors with fewer physical qubits than codes designed for the conventional Hamming metric. We discuss Lee-weight spreading under Clifford gates and qubitize codes over $\mathbb{Z}_4$ via the Gray map, finding codes with two-fold transversal non-qubit-Clifford gates. For quantum CSS Lee-LDPC codes on $n$ qudits, we prove that the Lee distance cannot exceed $O(n)$, uniformly in $q$, demonstrating an unexpected obstruction to using the large internal Hilbert space of a large-$q$ qudit to make high-Lee-distance codes. Under local Metropolis dynamics, certain classical $q$-ary ``helical repetition codes'' have exponentially long memory times at fixed temperature for sufficiently large $q$ (that grows with system length), which can be understood as spontaneous symmetry breaking at finite temperature, even in local one-dimensional models. Hypergraph products of these helical repetition codes provide local two-dimensional quantum codes that inherit self-correction for $Z$ errors, but self-correction for $X$ errors remains an open question.

0.49

PADO-Pauli: A GPU-Accelerated Implementation of Pauli Propagation

cs.ET quant-phcs.MS ·2026-10-13 ·Hyunwoo Kim, Youngseok Lee
code/data similarity 0.56
Abstract · 42 pages, 13 figures, 10 tables. Code available at https://github.com/Norma-Q/PADO-Pauli

Variational quantum algorithms utilize parameterized circuits many times during training, at new parameter values, over batches of data, and with gradients. Pauli propagation approximates the expectation values of such circuits classically by evolving the observable in the Heisenberg picture as a truncated sum of Pauli strings. We present PADO-Pauli, a GPU engine for Pauli propagation that compiles a circuit and its observables once into sparse matrices in which each rotation angle contributes only a cosine and a sine factor, so every later evaluation reuses the compiled program. It evaluates batches of parameters and data inputs embedded as rotation angles. By default its gradients come from a vector-Jacobian product registered with PyTorch's automatic differentiation, so they flow through the angles to any classical layer that produces them. PADO-Pauli also provides truncation by Pauli weight and coefficient size, and noise channels. Zero-filtering removes terms that do not contribute to an expectation value in the all-zero reference state and makes the batched forward pass about 1.5 times faster. Compared to cuPauliProp on an NVIDIA A100, PADO-Pauli evaluates up to 10 times faster on 4 to 12 qubits and uses up to 3.1 times less memory on 16 qubits. We check its accuracy against exact statevector simulation up to 28 qubits. These features make PADO-Pauli a practical toolkit for training variational quantum algorithms, including quantum machine learning models.

0.39

Fractal dimension predicts quantum kernel collapse in angle-encoded data

cs.LG quant-ph ·2026-08-31 ·Ana Paula Appel
similarity 0.55
Abstract · 28 pages, 12 figures. Submitted to Quantum Machine Intelligence

Angle-encoded quantum kernels on tabular data collapse when the feature map is wider than the intrinsic dimension of the data. We propose the correlation fractal dimension D2 as an a priori qubit budget: encode D2 coordinates chosen by FD-ASE instead of the PCA-95% width or all E attributes. On nine data sets and a statevector simulator (n= 32), a one-layer ZZ fidelity kernel at q=D2 stays geometrically alive while the same kernel at the PCA-95% width has already collapsed. The budget is map-dependent: product-state and IQP maps overshoot it; a second ZZ layer undershoots it. Packed dense-angle and re-uploading encodings still live at the fractal q, but not when PCA-95% features are stacked onto those qubits. Shrinking the angle bandwidth moves the ZZ knee later; stretching it kills the kernel earlier. On IBM Quantum (ibm_fez, 256 shots, n=8) the one-layer ZZ kernel at the fractal width matches the exact kernel (MAE 0.021); past that width both hardware and simulator have collapsed. The ceiling is a property of the map-data pair at a stated bandwidth, not of the classical table alone.

0.49

The kernel-block rank profiles of the $\mathbb{Z}_2\mathbb{Z}_4$-linear and the $\mathbb{Z}_{2^s}$-linear Hadamard codes, and a complete classification of the $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard codes

cs.IT ·2026-09-10 ·Dipak K. Bhunia
theory similarity 0.55
Abstract · 34 pages

The kernel of a binary code containing the zero word partitions the binary coordinates into blocks, two coordinates lying in the same block when every kernel word takes the same value in both, and the \emph{kernel-block rank profile} is the multiset of the dimensions of its linear span punctured on those blocks. For the family $H^{t_1,t_2,t_3}$ of $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard codes, this invariant is known explicitly and gives a complete classification of the family. In this paper, we compute it for the $\mathbb{Z}_2\mathbb{Z}_4$-linear and $\mathbb{Z}_{2^s}$-linear Hadamard families with which those codes are compared, and we prove that it is constant for every nonlinear $\mathbb{Z}_2\mathbb{Z}_4$-linear Hadamard code and for every nonlinear $\mathbb{Z}_{2^s}$-linear Hadamard code $\bar H^{a_1,\dots,a_s}$ with $s\geq2$. The second statement is obtained without any rank formula, by exhibiting coordinate permutations that preserve the code and act transitively on its kernel blocks, which makes the argument uniform in $s$. We also prove a descent theorem: if $\bar H^{a_1,\dots,a_s}$ is nonlinear and $a_1\geq2$, then the code punctured on one kernel block is the $\mathbb{Z}_{2^{s-1}}$-linear Hadamard code $\bar H^{a_1,\dots,a_{s-1}}$. Consequently, the constant local rank equals $rank(\bar H^{a_1,\dots,a_{s-1}})$ and is at least $t-κ+2$, where $2^t$ is the length and $κ$ the kernel dimension. These results separate every nonlinear $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard code from every $\mathbb{Z}_4$-linear, $\mathbb{Z}_2\mathbb{Z}_4$-linear and $\mathbb{Z}_{2^s}$-linear Hadamard code of the same length, except for the single infinite family $H^{1,1,t-4}$ and $\bar H^{2,0,t-5}$ with $t\geq5$. The members of this infinite family agree in the rank, kernel dimension and the kernel-block rank profile, but a two-block refinement separates them.

0.19

Efficient Lempel-Ziv Prediction with the Run-Length BWT

cs.DS cs.LG ·2026-11-01 ·Ohad Avnery
similarity 0.54
Abstract · 21 pages, 1 table

Lempel-Ziv Plurality (LZP) is an algorithm of Kosoy that predicts the next symbol of a string by using its Lempel-Ziv factorization, and makes at most $O(z\log n)$ mistakes on every string of length $n$ with $z$ LZ77 phrases. We give efficient online implementations of LZP and of a new variant of it. Our first implementation maintains a run-length encoded Burrows-Wheeler transform (RLBWT) of the reversed history. It implements LZP, uses $O(z\log z\log^2 n)$ bits, and has worst-case update and prediction times $O(\log z+\log\log n)$ and $O(σ(\log z+\log\log n))$, respectively, where $σ$ is the size of the alphabet. This is an exponential improvement over Kosoy's implementation, whose update time is $O(z\log^7 n)$. We then introduce the Lempel-Ziv Majority (LZM) predictor, which has the same mistake bound and update time, and predicts in $O(1)$ time independently of $σ$. These two predictors accept new symbols at any time, without knowing the alphabet in advance. For an alphabet known in advance, a different data structure gives $O(σ(1+\log z/\log\log n))$ time per symbol, which is constant when $σ=O(1)$ and $z=\mathrm{polylog}(n)$.

0.25

Resonance Breaking in Noisy Shor's Algorithm

cs.CC quant-phcs.ITmath-ph+1 ·2026-09-29 ·Zhengwei Liu
positionhot direction similarity 0.54
Abstract · 8 pages

We argue that the exponential quantum advantage in Shor's algorithm is broken under one-layer depolarizing noise of arbitrary small error rate, by analyzing a resonance breaking phenomenon in noisy quantum circuits. First, we express the distribution of measurements on $n$-qubit strings as the superposition of the $4^n$ wave functions in the Pauli path integral. In the noiseless case, the bit-strings achieving resonant peaks guaranteed a constant rate of successful measurements to factor a large number. Secondly, when the middle layer of the quantum circuit has independent depolarizing noise of rate $λ$, for any Hamming weight $d$, we obtain corresponding measurement rate bounded by $2(1-λ)^d$ for higher frequency terms and by $O(n^d)/2^{n/2}$ for low frequency terms. The rate approaches to zero as $n$ and $d$ approaches to infinity. Resonance breaking destroys the exponential quantum advantage. Furthermore, we design a classical factoring algorithm in polynomial time $O(n^d)$ to substitute the low frequency contribution.

0.40

The rank of $\mathbb{Z}_{2^s}$-linear Hadamard codes

cs.IT ·2026-10-26 ·Xuan Wang, Minjia Shi
similarity 0.54
Abstract

The canonical $\mathbb{Z}_{2^s}$-linear Hadamard codes are the Gray images of the $\mathbb{Z}_{2^s}$-additive codes. Their rank, the dimension of the binary linear span, was known in closed form only for $s\le 3$, and for $s \ge 4$ only through computer computations for small lengths. We give a method that computes the rank for every $s$. We show that the rank is a binomial polynomial in the type parameters, with coefficients $ρ_s(\boldsymbol{k})$ independent of the length. We compute all the coefficients for $s\le 5$, which yields explicit rank formulas over $\mathbb{Z}_4$ and $\mathbb{Z}_8$ (recovering the known ones), and over $\mathbb{Z}_{16}$ and $\mathbb{Z}_{32}$.

0.05