Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.08299

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

Mohammadreza Khellat, Mohammad Masoumi, Saman Nasoori, Soroush Nasoori

quant-phcs.MSSubmitted Oct 6, 2026• Announced Oct 7, 2026• 0 citations• Revised Oct 20, 2026 (v2)
v1 · Oct 6, 2026v2 · Oct 20, 2026
arXivHTMLPDF

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.

Comments
23 pages, 4 figures. Major presentation revision; algorithms and tables unchanged. Zenodo 10.5281/zenodo.22992251 (software), 10.5281/zenodo.22992460 (measurements)

Related papers

An efficient Pauli decomposition algorithm for structured matrices

Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only $k = \mathsf{poly}(n)$ Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in $n$. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least $1 - δ$, for any $δ$. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in $n$, $k$, and $\log(1/δ)$. These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.

quant-pharXiv:2606.31952•Jul 1, 2026•0 citations

Pauli decomposition via the fast Walsh-Hadamard transform

Timothy N. Georges, Bjorn K. Berntson, Christoph Sünderhauf +1 more

Abstract The decomposition of a square matrix into a sum of Pauli strings is a classical pre-processing step required to realize many quantum algorithms. Such a decomposition requires significant computational resources for large matrices. We present an exact and explicit formula for the Pauli string coefficients which inspires an efficient algorithm to compute them. More specifically, we show that up to a permutation of the matrix elements, the decomposition coefficients are related to the original matrix by a multiplication of a generalised Hadamard matrix. This allows one to use the Fast Walsh-Hadamard transform and calculate all Pauli decomposition coefficients in O ( N 2 log ⁡ N ) time and using O ( 1 ) additional memory, for an N × N matrix. A numerical implementation of our equation outperforms currently available solutions.

arXiv:2408.06206•New Journal of Physics•Feb 10, 2025•11 citations

Structurally Sparse Qubit Hamiltonians from Spectral Graph Theory

Josh Loutey

We show that qubit Hamiltonians derived from spectral graph theory lattices exhibit structurally favorable Pauli decompositions for quantum simulation. After Jordan–Wigner transformation, the GeoVac lattice Hamiltonian yields $O(Q^{3.15})$ Pauli string terms in the number of qubits $Q$, compared to $O(Q^{4+})$ for conventional Gaussian-basis Hamiltonians (our own log-log fit of the published Pauli counts of Trenev et al. [ref] gives $Q^{4.25}$ for LiH and $Q^{3.92}$ for H$_2$O, spanning $Q^{3.9}$–$Q^{4.3}$). The advantage originates in angular momentum selection rules—enforced by Gaunt integrals at the two-electron integral level—which cause the electron repulsion integral (ERI) tensor density to decay as $\sim 1/M$ (empirically $\approx M^{-0.85}$–$M^{-1}$) with the number of spatial orbitals $M$, while Gaussian ERI tensors remain near-dense at $O(1)$. Beyond term counts, we quantify two operationally relevant cost metrics: the number of qubitwise-commuting (QWC) measurement groups scales as $O(Q^{3.36})$, and the Pauli 1-norm $\lambda = \sum_i |c_i|$—which controls both Trotter step counts and qubitization query complexity—scales as $O(Q^{1.69})$ with $R^2 = 0.997$. The sub-quadratic 1-norm scaling is the key result for fault-tolerant simulation: it implies that Trotter circuit depth grows far more slowly with system size than term counts alone would suggest. All Gaussian baselines are validated against published integral values (Szabo and Ostlund for H$_2$; analytical STO for He). For composed multi-center systems, the pseudopotential approximation of the composed natural geometry framework [ref] yields block-diagonal electron repulsion integrals with a universal Pauli scaling of $O(Q^{2.5})$, independent of molecular topology (exponent spread $0.02$ across three molecules). At equal qubit counts, this represents two or more orders of magnitude fewer Pauli terms than Gaussian baselines (published counts of Trenev et al. [ref], $Q^{3.9}$–$Q^{4.3}$ span fitted by us)—an advantage that grows with system size due to the $\sim 1.5$ exponent gap. These comparisons are at matched qubit counts, not matched accuracy; the composed basis carries classical equilibrium-geometry errors of 5–26% (LiH/BeH$_2$/H$_2$O; Sec. (ref)), making the framework optimal for fixed-geometry quantum simulation rather than geometry optimisation. Across the composed molecular library (35 molecules spanning $Z = 1$–56, H through Ba, including the first transition series ScH–ZnH), the composed Pauli count is exactly linear in the qubit count: $N_{\mathrm{Pauli}} = 11.10 × Q$ (exact, non-identity terms; $d$-orbital blocks give 9.23). These counts are realized under a pair-diagonal angular approximation ($m_a=m_c$, $m_b=m_d$) adopted deliberately for sparsity; the exact global-$M_L$ Coulomb rule (used in the framework's precision-physics paths, and considered but left on the table here) gives $\approx 2.5×$ more terms with the same scaling, under which the $d$-block coefficient is in fact higher, not lower (Sec. (ref)). GeoVac Paper 14. Part of the GeoVac research corpus (quantum computing group). Code, tests, and the full paper series: https://github.com/jloutey-hash/geovac. Corpus archive DOI: 10.5281/zenodo.20482394. Corpus version at deposit: v4.75.0.

•Jul 9, 2026•0 citations

Efficiently manipulating Pauli strings with PauliArray

Maxime Dion, Tania Belabbas, Nolan Bastien

Pauli matrices and Pauli strings are widely used in quantum computing. These mathematical objects are useful to describe or manipulate the quantum state of qubits. They offer a convenient basis to express operators and observables used in different problem instances such as molecular simulation and combinatorial optimization. Therefore, it is important to have a well-rounded, versatile and efficient tool to handle a large number of Pauli strings and operators expressed in this basis. This is the objective behind the development of the PauliArray library presented in this work. This library introduces data structures to represent arrays of Pauli strings and operators as well as various methods to modify and combine them. Built using NumPy, PauliArray offers fast operations and the ability to use broadcasting to easily carry out otherwise cumbersome manipulations. Applications to the fermion-to-qubit mapping, to the estimation of expectation values and to the computation of commutators are considered to illustrate how PauliArray can simplify some relevant tasks and accomplish them faster than current libraries.

arXiv:2405.19287•May 29, 2024•0 citations

PHASE: Pauli Hierarchical Assembly on Subdivided Elements for Quantum-Compatible Operator Synthesis

Tillman Philo, Caglar Oskay

Efficiently decomposing finite element stiffness matrices into the Pauli basis is challenging due to the exponential growth of Pauli strings with problem size. A naive Pauli expansion requires $Θ(8^{\lceil \log_2 N \rceil})$ operations, where $N$ denotes the number of degrees of freedom, rendering direct decomposition infeasible for large systems. Existing approaches exploit algebraic sparsity or operator structure but do not incorporate the geometric organization intrinsic to finite element discretizations, and consequently exhibit poor scaling for stiffness matrices. To address this problem, we introduce PHASE, a hierarchical, geometry-aware Pauli decomposition algorithm that leverages recursive mesh partitioning to organize element contributions across multiple spatial scales. PHASE employs a hybrid strategy that combines full- and reduced-space Tensorized Pauli Decomposition with Fast Walsh-Hadamard Transform-based aggregation to assemble global Pauli coefficients efficiently. We show that this approach yields a dimension-dependent reduction in the exponential scaling exponent of Pauli assembly asymptotic complexity relative to existing methods, reducing the cost from $2^{2{\lceil \log_2 N \rceil}}$ to $2^{γ_d{\lceil \log_2 N \rceil}}$ with $γ_d < 2$ under standard mesh regularity and balanced partition assumptions. These results substantially improve the feasibility of quantum-compatible operator synthesis for large-scale finite element models.

quant-pharXiv:2606.11478•Computer Methods in Applied Mechanics and Engineering•Jun 11, 2026•0 citations

A Tree-Approach Pauli Decomposition Algorithm with Application to Quantum Computing

Océane Koska, Marc Baboulin, Arnaud Gazda

The Pauli matrices are 2-by-2 matrices that are very useful in quantum computing. They can be used as elementary gates in quantum circuits but also to decompose any matrix of$\mathbb{C}^{2^{n}\times 2^{n}}$as a linear combination of tensor products of the Pauli matrices. However, the computational cost of this decomposition is potentially very expensive since it can be exponential in$n$. In this paper, we propose an algorithm with a parallel implementation that optimizes this decomposition using a tree approach to avoid redundancy in the computation while using a limited memory footprint. We also explain how some particular matrix structures can be exploited to reduce the number of operations. We provide numerical experiments to evaluate the sequential and parallel performance of our decomposition algorithm and we illustrate how this algorithm can be applied to encode matrices in a quantum memory.

arXiv:2403.11644•ISC High Performance (ISC)•May 1, 2024•8 citations
Pauli decomposition of an nnn-qubit operator is expensive if each of the 4n4^n4n Pauli strings is treated as an unstructured object. Labeling those strings by the configuration space (Z2)n(\mathbb{Z}_2)^n(Z2​)n makes them displacement operators X⊗xZ⊗zX^{\otimes x}Z^{\otimes z}X⊗xZ⊗z on the computational space: shifts by~xxx and multiplications by characters Z⊗zZ^{\otimes z}Z⊗z in the computational basis. That labeling organizes the operator into 2n2^n2n fibers of length 2n2^n2n, one per shift~xxx, each collecting the computational-basis amplitudes that hop by~xxx. Expanding each fiber function in the character basis of (Z2)n(\mathbb{Z}_2)^n(Z2​)n --- a length-2n2^n2n Walsh--Hadamard transform --- recovers the Pauli coefficients at total cost O(n⋅4n)O(n\cdot4^n)O(n⋅4n). The same fiber / shift--character picture extends to (Zp)n(\mathbb{Z}_p)^n(Zp​)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 2n×2n2^n\times2^n2n×2n operator. Performance is checked on a stated low-end GNU/Linux platform for a coupled-oscillator sweep beyond a billion Pauli terms.
Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only k=poly(n)k = \mathsf{poly}(n)k=poly(n) Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in nnn. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least 1−δ1 - δ1−δ, for any δδδ. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in nnn, kkk, and log⁡(1/δ)\log(1/δ)log(1/δ). These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.
Abstract The decomposition of a square matrix into a sum of Pauli strings is a classical pre-processing step required to realize many quantum algorithms. Such a decomposition requires significant computational resources for large matrices. We present an exact and explicit formula for the Pauli string coefficients which inspires an efficient algorithm to compute them. More specifically, we show that up to a permutation of the matrix elements, the decomposition coefficients are related to the original matrix by a multiplication of a generalised Hadamard matrix. This allows one to use the Fast Walsh-Hadamard transform and calculate all Pauli decomposition coefficients in O ( N 2 log ⁡ N ) time and using O ( 1 ) additional memory, for an N × N matrix. A numerical implementation of our equation outperforms currently available solutions.
We show that qubit Hamiltonians derived from spectral graph theory lattices exhibit structurally favorable Pauli decompositions for quantum simulation. After Jordan–Wigner transformation, the GeoVac lattice Hamiltonian yields O(Q3.15)O(Q^{3.15})O(Q3.15) Pauli string terms in the number of qubits QQQ, compared to O(Q4+)O(Q^{4+})O(Q4+) for conventional Gaussian-basis Hamiltonians (our own log-log fit of the published Pauli counts of Trenev et al. [ref] gives Q4.25Q^{4.25}Q4.25 for LiH and Q3.92Q^{3.92}Q3.92 for H2_22​O, spanning Q3.9Q^{3.9}Q3.9–Q4.3Q^{4.3}Q4.3). The advantage originates in angular momentum selection rules—enforced by Gaunt integrals at the two-electron integral level—which cause the electron repulsion integral (ERI) tensor density to decay as ∼1/M\sim 1/M∼1/M (empirically ≈M−0.85\approx M^{-0.85}≈M−0.85–M−1M^{-1}M−1) with the number of spatial orbitals MMM, while Gaussian ERI tensors remain near-dense at O(1)O(1)O(1). Beyond term counts, we quantify two operationally relevant cost metrics: the number of qubitwise-commuting (QWC) measurement groups scales as O(Q3.36)O(Q^{3.36})O(Q3.36), and the Pauli 1-norm λ=∑i∣ci∣\lambda = \sum_i |c_i|λ=∑i​∣ci​∣—which controls both Trotter step counts and qubitization query complexity—scales as O(Q1.69)O(Q^{1.69})O(Q1.69) with R2=0.997R^2 = 0.997R2=0.997. The sub-quadratic 1-norm scaling is the key result for fault-tolerant simulation: it implies that Trotter circuit depth grows far more slowly with system size than term counts alone would suggest. All Gaussian baselines are validated against published integral values (Szabo and Ostlund for H2_22​; analytical STO for He). For composed multi-center systems, the pseudopotential approximation of the composed natural geometry framework [ref] yields block-diagonal electron repulsion integrals with a universal Pauli scaling of O(Q2.5)O(Q^{2.5})O(Q2.5), independent of molecular topology (exponent spread 0.020.020.02 across three molecules). At equal qubit counts, this represents two or more orders of magnitude fewer Pauli terms than Gaussian baselines (published counts of Trenev et al. [ref], Q3.9Q^{3.9}Q3.9–Q4.3Q^{4.3}Q4.3 span fitted by us)—an advantage that grows with system size due to the ∼1.5\sim 1.5∼1.5 exponent gap. These comparisons are at matched qubit counts, not matched accuracy; the composed basis carries classical equilibrium-geometry errors of 5–26% (LiH/BeH2_22​/H2_22​O; Sec. (ref)), making the framework optimal for fixed-geometry quantum simulation rather than geometry optimisation. Across the composed molecular library (35 molecules spanning Z=1Z = 1Z=1–56, H through Ba, including the first transition series ScH–ZnH), the composed Pauli count is exactly linear in the qubit count: NPauli=11.10×QN_{\mathrm{Pauli}} = 11.10 × QNPauli​=11.10×Q (exact, non-identity terms; ddd-orbital blocks give 9.23). These counts are realized under a pair-diagonal angular approximation (ma=mcm_a=m_cma​=mc​, mb=mdm_b=m_dmb​=md​) adopted deliberately for sparsity; the exact global-MLM_LML​ Coulomb rule (used in the framework's precision-physics paths, and considered but left on the table here) gives ≈2.5×\approx 2.5×≈2.5× more terms with the same scaling, under which the ddd-block coefficient is in fact higher, not lower (Sec. (ref)). GeoVac Paper 14. Part of the GeoVac research corpus (quantum computing group). Code, tests, and the full paper series: https://github.com/jloutey-hash/geovac. Corpus archive DOI: 10.5281/zenodo.20482394. Corpus version at deposit: v4.75.0.
Pauli matrices and Pauli strings are widely used in quantum computing. These mathematical objects are useful to describe or manipulate the quantum state of qubits. They offer a convenient basis to express operators and observables used in different problem instances such as molecular simulation and combinatorial optimization. Therefore, it is important to have a well-rounded, versatile and efficient tool to handle a large number of Pauli strings and operators expressed in this basis. This is the objective behind the development of the PauliArray library presented in this work. This library introduces data structures to represent arrays of Pauli strings and operators as well as various methods to modify and combine them. Built using NumPy, PauliArray offers fast operations and the ability to use broadcasting to easily carry out otherwise cumbersome manipulations. Applications to the fermion-to-qubit mapping, to the estimation of expectation values and to the computation of commutators are considered to illustrate how PauliArray can simplify some relevant tasks and accomplish them faster than current libraries.
Efficiently decomposing finite element stiffness matrices into the Pauli basis is challenging due to the exponential growth of Pauli strings with problem size. A naive Pauli expansion requires Θ(8⌈log⁡2N⌉)Θ(8^{\lceil \log_2 N \rceil})Θ(8⌈log2​N⌉) operations, where NNN denotes the number of degrees of freedom, rendering direct decomposition infeasible for large systems. Existing approaches exploit algebraic sparsity or operator structure but do not incorporate the geometric organization intrinsic to finite element discretizations, and consequently exhibit poor scaling for stiffness matrices. To address this problem, we introduce PHASE, a hierarchical, geometry-aware Pauli decomposition algorithm that leverages recursive mesh partitioning to organize element contributions across multiple spatial scales. PHASE employs a hybrid strategy that combines full- and reduced-space Tensorized Pauli Decomposition with Fast Walsh-Hadamard Transform-based aggregation to assemble global Pauli coefficients efficiently. We show that this approach yields a dimension-dependent reduction in the exponential scaling exponent of Pauli assembly asymptotic complexity relative to existing methods, reducing the cost from 22⌈log⁡2N⌉2^{2{\lceil \log_2 N \rceil}}22⌈log2​N⌉ to 2γd⌈log⁡2N⌉2^{γ_d{\lceil \log_2 N \rceil}}2γd​⌈log2​N⌉ with γd<2γ_d < 2γd​<2 under standard mesh regularity and balanced partition assumptions. These results substantially improve the feasibility of quantum-compatible operator synthesis for large-scale finite element models.
The Pauli matrices are 2-by-2 matrices that are very useful in quantum computing. They can be used as elementary gates in quantum circuits but also to decompose any matrix ofC2n×2n\mathbb{C}^{2^{n}\times 2^{n}}C2n×2nas a linear combination of tensor products of the Pauli matrices. However, the computational cost of this decomposition is potentially very expensive since it can be exponential innnn. In this paper, we propose an algorithm with a parallel implementation that optimizes this decomposition using a tree approach to avoid redundancy in the computation while using a limited memory footprint. We also explain how some particular matrix structures can be exploited to reduce the number of operations. We provide numerical experiments to evaluate the sequential and parallel performance of our decomposition algorithm and we illustrate how this algorithm can be applied to encode matrices in a quantum memory.