⚛️ quantum physics

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

This paper introduces a memory-bounded algorithm, implemented in the `paulikit` library, that leverages character theory and the Fast Fourier Transform (specifically Walsh-Hadamard for qubits) to efficiently compute Pauli decompositions for arbitrary operators without requiring the materialization of dense $2^n \times 2^n$ matrices.

Original authors: Mohammadreza Khellat, Mohammad Masoumi, Saman Nasoori, Soroush Nasoori

Published 2026-10-07

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammadreza Khellat, Mohammad Masoumi, Saman Nasoori, Soroush Nasoori

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Quantum computers promise to solve problems that would take today's supercomputers thousands of years to crack, from designing new medicines to modeling complex materials. To do this, they must simulate the behavior of quantum systems, which are governed by mathematical objects called Hamiltonians. These objects describe how energy moves and changes within a system. However, quantum hardware cannot natively understand these complex, continuous descriptions. Instead, engineers must translate them into a specific language the machine speaks: a collection of simple, discrete building blocks known as Pauli strings. This translation process, called Pauli decomposition, is the essential first step for almost every quantum algorithm. Without it, the computer cannot begin its work. The problem is that for systems with many parts, the number of these building blocks explodes exponentially, making the translation so slow and memory-hungry that it often becomes a major practical bottleneck.

A team of researchers at Beavernets Technologies has developed a new way to perform this translation that breaks the memory barrier that has long held the field back. Their work, centered on a software tool they named paulikit, allows scientists to decompose massive quantum operators without ever needing to store the entire, unwieldy mathematical object in the computer's memory at once. In traditional approaches, the computer had to load the full, dense matrix of the system into memory before it could begin breaking it down. For larger systems, this matrix becomes so large that it exceeds the capacity of a typical laptop and requires large-memory workstations. The new method avoids this bottleneck by treating the problem as a series of small, independent tasks that can be processed one by one, streaming the results out as they are generated. For sparse matrix inputs, paulikit avoids building the full dense operator entirely. For inputs that are already dense, the current release still keeps that dense matrix in memory while streaming the decomposition. This allows the researchers to handle systems with over a billion distinct terms, a scale that was previously difficult to manage on modest hardware.

The core of their discovery lies in a fresh perspective on the mathematics behind the translation. The researchers realized that the problem could be understood through the lens of character theory, a branch of mathematics that studies how groups of symmetries interact. By viewing the quantum system as a grid of shifts and signs, they showed that the complex task of finding the coefficients for every building block is mathematically identical to a specific type of fast Fourier transform, a well-known algorithm for analyzing signals. This insight allowed them to replace a slow, brute-force calculation with a much faster, structured approach. They demonstrated that this method works not only for standard quantum bits but also extends cleanly to higher-dimensional systems, known as qudits, suggesting a universal path forward for more advanced quantum hardware.

A critical part of their work involves clarifying a long-standing ambiguity in how these building blocks are defined. In the quantum community, there are two ways to write down the same mathematical object: one version uses only real numbers, while the other inserts imaginary numbers at specific overlaps to ensure the pieces behave like physical observables. The researchers proved that the initial, simpler version is already a complete and valid decomposition. The step that adds the imaginary numbers is not a requirement of the math itself, but a choice made to ensure that individual pieces can be used as physical gates or measurements on a real device. By separating the mathematical decomposition from this physical convention, they showed that the heavy lifting of the calculation can be done in the simpler form, with the final adjustment applied only at the very end. This distinction removes unnecessary complexity from the core algorithm.

To prove their method works in the real world, the team tested it on a model of a fully coupled oscillator network, a system that mimics how vibrations travel through a network of masses and springs. They pushed the test to a system with 300 oscillators, which translates to a quantum operator with over 1.4 billion non-zero terms. In a traditional approach, the computer would need to hold a dense matrix or even just the surviving terms in memory, requiring tens of gigabytes of RAM. The new method, however, kept the decomposition memory footprint in the tens of megabytes, with the total process memory staying under about 100 megabytes, even as the number of terms grew over a thousand-fold. The researchers verified the results by comparing them against independent calculations, finding that the numbers matched to the limits of machine precision, confirming that the memory-saving tricks did not sacrifice accuracy.

The team also rigorously analyzed how their software performs on modern multi-core processors. They found that the algorithm scales efficiently, utilizing multiple processor cores to speed up the calculation without getting bogged down by the overhead of managing data between them. By measuring the actual time taken for each step and comparing it against theoretical limits, they showed that the software is limited by the speed at which data can be moved through the computer's memory, rather than by the raw speed of the processor. They also demonstrated that the software's API can handle non-Hermitian operators, which are mathematical objects that do not necessarily represent physical observables but are crucial for certain advanced simulations.

While the software is currently optimized for standard quantum bits, the mathematical framework they developed is general enough to apply to qudits, which are higher-dimensional quantum units that could offer more efficient computing in the future. The researchers note that while the coefficient extraction works for these systems, the specific properties of quantum error correction and randomization techniques used in current quantum experiments do not automatically transfer to these higher dimensions. This is a careful distinction, ensuring that users do not assume the software solves every problem in the qudit domain without further work. The team has released their code and all the data from their performance tests to the public, allowing other scientists to verify the results and build upon the foundation they have laid.

The significance of this work is not that it changes the fundamental speed of the calculation in a theoretical sense, but that it removes the practical wall that has prevented the calculation from being done at all for large systems. By decoupling the memory requirement from the size of the problem, the researchers have opened the door to simulating quantum systems that were previously too large to decompose. This allows physicists and chemists to tackle more realistic models of materials and molecules, moving closer to the day when quantum computers can provide genuine insights into the physical world. The paper stands as a demonstration that sometimes the most powerful advances come not from inventing a new law of physics, but from finding a smarter way to organize the data that already exists.

Technical Summary: Pauli Decomposition by Character Theory

Problem Statement
Pauli decomposition is a fundamental prerequisite for quantum algorithms including Trotterization, phase estimation, sparse-Hamiltonian simulation, and variational observables. The task involves expressing an arbitrary $n$ -qubit operator $H$ as a linear combination of Pauli strings:
$H = \sum_{x,z} c_{x,z} P(x, z)$
where $P(x, z)$ are tensor products of $\{I, X, Y, Z\}$ . The direct approach to computing these coefficients via trace projection ( $c_{x,z} = \text{Tr}(H \cdot P(x,z))/2^n$ ) incurs an exponential cost of $O(2^{5n})$ or $O(2^{3n})$ depending on implementation, making it infeasible for large systems. While prior work (e.g., Georges et al., Hamaguchi et al.) has reduced the asymptotic time complexity to $O(n \cdot 4^n)$ using the Fast Walsh-Hadamard Transform (FWHT), these methods typically require materializing the full $2^n \times 2^n$ operator matrix in memory. This creates a "memory wall" where the peak memory usage scales as $O(4^n)$ , limiting practical application to systems with roughly $n \le 15$ qubits, even when the resulting Pauli expansion is sparse.

Methodology
The paper reframes Pauli decomposition through the character theory of the abelian group $(\mathbb{Z}_2)^n$ .

Character-Theoretic Derivation:
- The authors identify the diagonal Pauli strings ( $Z^{\otimes z}$ ) as the characters $\chi_z(v) = (-1)^{\langle v, z \rangle}$ of the group $(\mathbb{Z}_2)^n$ .
- A general Pauli string $X^{\otimes x}Z^{\otimes z}$ is viewed as a shift operator $X^{\otimes x}$ coupled with a character $\chi_z$ .
- The decomposition is shown to be equivalent to performing $2^n$ independent Fast Walsh-Hadamard Transforms (FWHT). For a fixed shift $x$ , the coefficients are obtained by transforming the vector of matrix elements $\{T_{v, v+x}\}_v$ against the characters.
- The paper distinguishes between the "bare" basis ( $X^{\otimes x}Z^{\otimes z}$ ) and the "genuine" basis (where $Y = iXZ$ is inserted at overlapping qubits). The algorithm first computes the decomposition in the bare basis (Step 1) and then applies a phase correction $i^{|x \wedge z|}$ to convert to the genuine basis (Step 2). This separation clarifies that the computational cost is identical for both, and the choice of basis is a phase convention driven by the need for Hermitian terms in gate compilation, not an algebraic necessity.
Memory-Bounded Streaming Implementation (paulikit):
- To overcome the memory bottleneck, the authors implement a streaming algorithm that, for sparse matrix inputs, avoids materializing the full $2^n \times 2^n$ operator.
- Chunk Independence: Leveraging Lemma 2, the set of shifts $x$ is partitioned into disjoint chunks. Each chunk is processed independently: rows $T_{v, v+x}$ are gathered, transformed via FWHT, phase-corrected, and thresholded.
- Streaming Accumulation: Instead of storing a dense intermediate array, the algorithm yields raw $(x, z, \text{coefficient})$ triples for each chunk. This ensures that for sparse inputs, peak memory usage is bounded by $O(\text{chunk\_size} \times 2^n + N_{\text{terms}})$ , where $N_{\text{terms}}$ is the number of surviving coefficients, rather than the full operator size. (Note: For already-dense inputs, the per-chunk working set remains small, but the whole-process memory still holds the dense input matrix itself).
- Optimization: The implementation replaces Python-level loops with compiled C kernels for the FWHT and coefficient extraction to minimize overhead. It supports both process-pool and thread-pool parallelism, with an automatic selection mechanism based on the presence of compiled kernels to avoid GIL contention.

Key Contributions

Character-Theoretic Formulation: The paper provides a derivation of the $O(n \cdot 4^n)$ Pauli decomposition algorithm explicitly rooted in the character theory of $(\mathbb{Z}_2)^n$ , generalizing naturally to qudits via the Discrete Fourier Transform over $(\mathbb{Z}_p)^n$ (Corollary 1).
Basis Clarification: It explicitly demonstrates that the decomposition in the "bare" basis is complete and computationally equivalent to the "genuine" basis, with the latter being a simple phase adjustment. This clarifies that the use of $Y$ is a convention for Hermiticity, not a requirement for the transform itself.
Memory-Bounded Algorithm: The primary engineering contribution is paulikit, a library that achieves the $O(n \cdot 4^n)$ time complexity while maintaining low peak memory usage for sparse inputs. This allows the decomposition of operators with Hilbert-space dimensions far exceeding available RAM (e.g., $2^{14}$ dimensions with sparse outputs).
Rigorous Verification and Bounds: The authors provide exhaustive per-term correctness checks (up to $1.47 \times 10^9$ terms) and derive theoretical Work-Span and memory-bandwidth ceilings. These bounds are validated against direct measurements on a specific low-end Linux platform.

Results

Scalability: The algorithm was tested on a fully coupled harmonic oscillator family. At $N=150$ oscillators (requiring 14 qubits, Hilbert space dimension $2^{14} = 16,384$ ), the operator had $91,652,096$ nonzero Pauli terms. At this scale, a naive dense approach requires only a few GiB and is within reach of a laptop.
Memory Efficiency: For larger scales, such as $N=300$ ( $n=16$ , $1,470,038,016$ terms), the surviving triples alone would require approximately 44 GiB, while a full dense matrix would require 64 GiB. In measured streaming tests, as the number of terms grew $1165\times$ (from $N=50$ to $N=300$ ), the paulikit decomposition memory only grew from 13.2 to 46.0 MiB, and the whole-process peak RSS grew from 64.7 to 99.6 MiB, confirming that the memory is effectively decoupled from the result size for sparse inputs.
Performance: On a 4-core platform, the threaded implementation achieved speedups of $1.81\times$ (2 workers) and $3.36\times$ (4 workers), closely matching Amdahl's law predictions derived from the measured serial fraction. The compiled kernels achieved a throughput of $1.34$ GFLOPs/s, confirming the kernel is memory-bound (operating at $\sim 34\%$ of the platform's sustained bandwidth ceiling).
Correctness: All coefficients were verified against an independent projection method with a maximum absolute error of $8.7 \times 10^{-19}$ , consistent with machine precision.

Significance and Claims
The paper modestly claims that its primary contribution is memory scalability, not a reduction in asymptotic time complexity (which remains $O(n \cdot 4^n)$ , matching prior state-of-the-art). The significance lies in making Pauli decomposition feasible for large, sparse operators that were previously inaccessible due to memory constraints.

Theoretical Scope: The work establishes that the "genuine" Pauli basis is a phase-convention choice within a central extension of $(\mathbb{Z}_2)^n \times (\mathbb{Z}_2)^n$ , and that the character-theoretic approach naturally extends to qudits.
Practical Scope: The paulikit library enables the decomposition of non-Hermitian operators (treated as first-class inputs) and large sparse Hamiltonians without requiring supercomputing resources.
Limitations: The authors explicitly note that while the coefficient extraction lifts to qudits, the design properties of Clifford twirling (e.g., 2-designs) do not automatically lift to composite dimensions. The paper does not claim to solve the Clifford twirling problem for qudits, nor does it ship a qudit module. The performance bounds are specific to the tested hardware and do not claim universal superiority over all other implementations in all regimes.

In summary, the paper presents a theoretically grounded, memory-efficient realization of Pauli decomposition that bridges the gap between the theoretical $O(n \cdot 4^n)$ complexity and the practical constraints of large-scale quantum simulation.

Technical Summary: Pauli Decomposition by Character Theory

More like this