© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2401.16378

Decomposing dense matrices into dense Pauli tensors

Tyson Jones

Published Jan 29, 2024• 3 citations

Abstract

Decomposing a matrix into a weighted sum of Pauli strings is a common chore of the quantum computer scientist, whom is not easily discouraged by exponential scaling. But beware, a naive decomposition can be cubically more expensive than necessary! In this manuscript, we derive a fixed-memory, branchless algorithm to compute the inner product between a 2^N-by-2^N complex matrix and an N-term Pauli tensor in O(2^N) time, by leveraging the Gray code. Our scheme permits the embarrassingly parallel decomposition of a matrix into a weighted sum of Pauli strings in O(8^N) time. We implement our algorithm in Python, hosted open-source on Github, and benchmark against a recent state-of-the-art method called the "PauliComposer" which has an exponentially growing memory overhead, achieving speedups in the range of 1.5x to 5x for N < 8. Note that our scheme does not leverage sparsity, diagonality, Hermitivity or other properties of the input matrix which might otherwise enable optimised treatment in other methods. As such, our algorithm is well-suited to decomposition of dense, arbitrary, complex matrices which are expected dense in the Pauli basis, or for which the decomposed Pauli tensors are a priori unknown.

DOI: 10.48550/arxiv.2401.16378

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

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

PauliComposer: compute tensor products of Pauli matrices efficiently

Sebastián V. Romero, Juan Santos-Suárez

Abstract We introduce a simple algorithm that efficiently computes tensor products of Pauli matrices. This is done by tailoring the calculations to this specific case, which allows to avoid unnecessary calculations. The strength of this strategy is benchmarked against state-of-the-art techniques, showing a remarkable acceleration. As a side product, we provide an optimized method for one key calculus in quantum simulations: the Pauli basis decomposition of Hamiltonians.

arXiv:2301.00560•Quantum Information Processing•Dec 15, 2023•13 citations

H2ZIXY: Pauli spin matrix decomposition of real symmetric matrices

Rocco Monteiro Nunes Pesce, P. D. Stevenson

We present a code in Python3 which takes a square real symmetric matrix, of arbitrary size, and decomposes it as a tensor product of Pauli spin matrices. The application to the decomposition of a Hamiltonian of relevance to nuclear physics for implementation on quantum computer is given.

arXiv:2111.00627•Oct 31, 2021•5 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

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

Decomposing a matrix into a weighted sum of Pauli strings is a common chore of the quantum computer scientist, whom is not easily discouraged by exponential scaling. But beware, a naive decomposition can be cubically more expensive than necessary! In this manuscript, we derive a fixed-memory, branchless algorithm to compute the inner product between a 2^N-by-2^N complex matrix and an N-term Pauli tensor in O(2^N) time, by leveraging the Gray code. Our scheme permits the embarrassingly parallel decomposition of a matrix into a weighted sum of Pauli strings in O(8^N) time. We implement our algorithm in Python, hosted open-source on Github, and benchmark against a recent state-of-the-art method called the "PauliComposer" which has an exponentially growing memory overhead, achieving speedups in the range of 1.5x to 5x for N < 8. Note that our scheme does not leverage sparsity, diagonality, Hermitivity or other properties of the input matrix which might otherwise enable optimised treatment in other methods. As such, our algorithm is well-suited to decomposition of dense, arbitrary, complex matrices which are expected dense in the Pauli basis, or for which the decomposed Pauli tensors are a priori unknown.

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.

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.

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.

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.