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
v1 · Oct 6, 2026v2 · Oct 20, 2026
arXivHTMLPDF

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 $χ_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 $χ_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.

Comments
29 pages, 4 figures. Open-source companion: paulikit (GPL-3.0-or-later), Zenodo 10.5281/zenodo.22992251; measurements 10.5281/zenodo.22992460

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 underpins Trotterization, phase estimation, sparse-Hamiltonian simulation, and variational observables, at exponential naive cost. From the character theory of (Z2)n(\mathbb{Z}_2)^n(Z2​)n, characters χz(v)=(−1)⟨v,z⟩χ_z(v)=(-1)^{\langle v,z\rangle}χ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⊗xX^{\otimes x}X⊗x couples to a character χz=Z⊗zχ_z=Z^{\otimes z}χz​=Z⊗z, and the products X⊗xZ⊗zX^{\otimes x}Z^{\otimes z}X⊗xZ⊗z -- up to phases in {±1,±i}\{\pm 1,\pm i\}{±1,±i} -- form the Pauli group, the central extension of (Z2)n×(Z2)n(\mathbb{Z}_2)^n\times(\mathbb{Z}_2)^n(Z2​)n×(Z2​)n by that phase group fixed by the symplectic pairing. A section of that extension remains a choice: the bare products X⊗xZ⊗zX^{\otimes x}Z^{\otimes z}X⊗xZ⊗z, or the genuine operators that insert Y=iXZY=iXZY=iXZ at every qubit where xxx and zzz overlap. As Fourier analysis on an abelian shift-character lattice (a natural DFT), this formulation is not qubit-bound: (Zp)n(\mathbb{Z}_p)^n(Zp​)n recovers Heisenberg-Weyl qudits. The fast algorithm is the FFT for the group at hand; on (Z2)n(\mathbb{Z}_2)^n(Z2​)n that FFT is Walsh-Hadamard, at cost O(n⋅4n)O(n\cdot 4^n)O(n⋅4n). paulikit is a memory-bounded realization of that qubit transform: peak usage need not materialize the dense 2n×2n2^n\times 2^n2n×2n operator, unlike prior codes whose O(1)O(1)O(1) extra sits on that buffer, checked beyond a billion oscillator terms against Work-Span and bandwidth ceilings.
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.