An efficient Pauli decomposition algorithm for structured matrices

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

Read An efficient Pauli decomposition algorithm for structured matrices by Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-31952.txt.

Introduction

Spencer and two colleagues speed up a bottleneck in near-term quantum computing: writing a classical matrix as a combination of Pauli strings. Quantum algorithms for chemistry, optimization and linear algebra usually assume the input already arrives in that form. For a general matrix, recovering the decomposition takes time exponential in the number of qubits, which can erase any quantum speedup before the device even runs.

Their randomized classical algorithm targets matrices promised to use only polynomially many Pauli strings, accessed through sparse queries. It recovers the exact decomposition with success probability at least one minus a chosen error level. Query and runtime costs stay polynomial in the qubit count, the number of Pauli terms and the logarithm of the inverse error.

Catalog record

CREATORDaniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.31952

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An efficient Pauli decomposition algorithm for structured matrices Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov Abstract 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=\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 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 − δ 1-\delta , for any δ \delta . Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in n n , k k , and log ⁡ ( 1 / δ ) \log(1/\delta) . 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. I Introduction Quantum algorithms for applications in chemistry [ 20 , 10 , 2 , 24 , 26 ] , machine learning [ 22 , 37 , 7 , 11 , 34 , 42 , 39 ] , and finance [ 28 , 8 , 14 ] often require classically-specified data to be loaded into a representation accessible to a quantum device, leading to the so-called data-loading problem [ 40 , 41 , 27 , 23 ] . In many near-term intermediate-scale quantum (NISQ) [ 33 , 4 ] settings, this representation takes the form of a linear combination of unitaries (LCUs), where the unitaries are often taken to be Pauli strings due to their natural compatibility with current quantum hardware. Obtaining this Pauli decomposition can be computationally costly, though this problem is frequently overlooked, with many NISQ algorithms simply assuming that the input data are already written in the Pauli basis. When considered in an end-to-end context, finding this decomposition may ruin the supposed speedup before even running the quantum algorithm. This problem arises in several prominent algorithmic settings. Variational methods such as the variational quantum eigensolver (VQE) [ 32 , 17 , 38 ] often assume that the input to the problem is a Hamiltonian decomposed into a linear combination of Pauli strings. Other near-term algorithms for optimization [ 30 ] and linear algebra [ 15 , 9 , 31 ] make similar assumptions, where the input matrices (e.g., the matrix A to solve the linear system Ax=b ) are assumed to be provided as an LCU. For problems in physics and chemistry, such decompositions are readily available from the underlying structure of the problem. However, for more general classically-specified matrices, the Pauli decomposition may not be known in advance and must be explicitly computed. While VQE is seen as one of the leading candidates for a useful near-term algorithm, alternative algorithms [ 6 , 5 ] have been proposed that avoid some of the problems of VQE (e.g., the barren plateau problem [ 21 ] ), but these too require the input to be given as a linear combination of Pauli strings. As such, there is a strong necessity for efficient Pauli decomposition algorithms. All algorithms [ 3 , 13 , 35 , 16 , 18 , 12 ] for decomposing a 2^{n}\times 2^{n} matrix into the Pauli basis scale exponentially in n in the worst case, where the matrix has support on all 4^{n} Pauli basis elements. In this case, there is an immediate worst-case lower bound of \bigOmega{4^{n}} since all 4^{n} Pauli terms must be recovered. The most straightforward way to obtain the Pauli decomposition of a 2^{n}\times 2^{n} matrix M is to calculate the overlap of each Pauli string with M to obtain the coefficient. Assuming standard matrix multiplication runtime of \bigOh{N^{3}} for an N\times N matrix, this requires 4^{n} multiplications of two 2^{n}\times 2^{n} matrices, for a total time complexity of \bigOh{32^{n}} . Although several existing algorithms [ 13 , 35 , 16 , 18 , 12 ] make significant improvements over the naïve trace-overlap approach, they are designed for the generic dense decomposition problem, where they either compute all 4^{n} Pauli coefficients or require access to the full matrix representation; see Table 1 . The best-known algorithm runs in time \bigOh{n4^{n}} and is implemented in the Python package PennyLane [ 3 ] . Algorithm Runtime complexity Direct algorithm \bigOh{32^{n}} PennyLane [ 3 ] \bigOh{n4^{n}} Gunlycke \etal [ 13 ] \bigOh{n4^{n}} PauliComposer [ 35 ] \bigOh{8^{n}} Jones [ 16 ] \bigOh{8^{n}} Koska \etal [ 18 ] \bigOh{8^{n}} Georges \etal [ 12 ] \bigOh{n4^{n}} Table 1: Comparison of runtime complexity of various Pauli decomposition algorithms. \captionsize \captionsize input \captionsize M= \captionsize v \captionsize u \captionsize sparse query access \captionsize \captionsize determine \mathcal{X} \captionsize x=u\oplus v \captionsize x_{1} \captionsize x_{2} \captionsize x_{3} \captionsize \mathcal{X}=\{x:\exists z\} \captionsize \captionsize shifts on fixed- x \captionsize \frac{b_{x}(e_{j})}{b_{x}(0^{n})}\overset{?}{=}\pm 1 for j\in[n] \captionsize \captionsize unique x \captionsize x \captionsize z \captionsize decode (z,\alpha) \captionsize \captionsize degenerate x \captionsize z_{1} \captionsize z_{2} \captionsize z_{3} \captionsize z_{4} \captionsize fixed x , several z ’s \captionsize \captionsize random fold \captionsize hash (S,R,w) \captionsize \captionsize \captionsize \captionsize 1 \captionsize 2 \captionsize 3 \captionsize 4 \captionsize keep verified singletons \captionsize \captionsize repeat, collect \captionsize z_{3} \captionsize z_{4} \captionsize all singletons \captionsize \captionsize output \captionsize Pauli decomposition: \mathcal{D}=\{P(x,z),\alpha_{x,z}\} \captionsize p_{x}=1 \captionsize p_{x}>1 \captionsize fresh independent folds \captionsize \captionsize degenerate x decoder \pgfsys@end@save \pgfscope@linewidth Figure 1: Schematic of the Pauli decomposition algorithm ( Algorithm 1 ). Assuming query access to the matrix M as described in Section III , the algorithm makes a series of queries that determine the set of active x bit strings and stores them in \mathcal{X} (see the beginning the Section III ). Then, for each x\in\mathcal{X} , the algorithm determines if x is unique and, if so, decodes it by finding its associated z bit string and coefficient \alpha to construct the full term in the Pauli decomposition ( Sections III.1 and 2 ). If x is degenerate, the algorithm passes x to the degenerate x decoder ( Algorithm 3 ), which uses the random folding procedure described in Section III.2 to determine the z bit strings and coefficients associated with each degenerate x . At the end, everything is put together to build the full Pauli decomposition of M . In this paper, we study a promise version of the Pauli decomposition problem. In particular, we assume that the input is a 2^{n}\times 2^{n} matrix that has support on k=\poly(n) elements of the Pauli basis and that the matrix is specified via a classical sparse query model. Under this model, we present a randomized classical algorithm that determines the Pauli decomposition with success probability at least 1-\delta for a user-chosen \delta\in(0,1) , with both query and runtime complexity scaling polynomially in n , k , and \log(1/\delta)

Read the complete text