⚛️ quantum physics

An efficient Pauli decomposition algorithm for structured matrices

This paper presents a randomized classical algorithm that efficiently recovers the exact Pauli decomposition of structured matrices with promised sparsity in polynomial time, overcoming the exponential complexity of existing methods designed for generic dense matrices.

Original authors: Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

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

The Big Problem: The "Pauli Puzzle"

Imagine you have a massive, complex instruction manual for a quantum computer. This manual is written in a special code called Pauli strings. To run a quantum algorithm, you need to break this manual down into its individual sentences (the Pauli strings) and know exactly what each one says.

However, for a general matrix (the instruction manual), this puzzle is incredibly hard. It's like trying to find a specific grain of sand on a beach that is the size of a planet. The number of possible grains grows so fast (exponentially) that even the fastest supercomputers would take longer than the age of the universe to solve it for large inputs.

Existing methods try to read the entire beach to find the sand. They are thorough, but they are too slow to be useful for the quantum computers we are building right now (called NISQ devices).

The Promise: A Sparse Beach

The authors of this paper say: "Wait a minute. What if we don't have a beach full of sand? What if we are promised that there are only a few grains of sand hidden in the whole manual?"

In technical terms, they assume the matrix is sparse. This means that out of the billions of possible Pauli strings, only a small, manageable number (let's call it $k$ ) are actually being used.

The paper asks: If we know the puzzle is simple (sparse), can we solve it quickly without reading the whole beach?

The Solution: A Smart Detective

The authors created a new, randomized algorithm that acts like a clever detective. Instead of reading every single page of the manual, the detective uses a few smart tricks to find the hidden grains of sand.

Here is how the detective works, broken down into three steps:

1. The "Flashlight" Scan (Finding the Locations)

Imagine the Pauli strings have two parts: a "location" part (where the action happens) and a "sign" part (whether it's positive or negative).

The Trick: The detective shines a flashlight on random rows of the manual. Because the manual is sparse, if a row has any writing at all, the detective can instantly tell which "location" is active.
The Analogy: It's like walking into a dark room with a few lit candles. You don't need to scan the whole room; just a quick glance at a few spots tells you exactly where the candles are. The algorithm finds the "active locations" (called unique $x$ bit strings) very quickly.

2. The "Unique" vs. "Crowded" Rooms

Once the detective finds a location, they check if it's a "unique" room or a "crowded" room.

Unique Rooms: Sometimes, a location has only one candle (one Pauli string). This is easy. The detective just reads the candle's label and moves on.
Crowded Rooms: Sometimes, multiple candles are stacked in the same spot, and their lights might cancel each other out or mix together. This is the hard part.

3. The "Folding" Trick (Solving the Crowded Rooms)

When the detective finds a crowded room, they can't just read the labels because they are mixed up.

The Trick: The detective uses a technique called random folding. Imagine taking a huge map of the room and folding it up into a small box.
The Magic: If you fold the map randomly, there's a good chance that the "crowded" candles will get separated into different corners of the box. Suddenly, a corner that looked crowded now has only one candle.
The Result: The detective can now read that single candle. They subtract it from the mix and repeat the folding process until all the candles in the crowded room are found.

Why This Matters

The paper proves that this detective method is fast.

Old Way: Takes time that grows exponentially (like $2^{100}$ ). Impossible for large problems.
New Way: Takes time that grows polynomially (like $n^3$ ). This is fast enough for real-world use.

The algorithm doesn't just guess; it has built-in "certification" steps. It checks its own work to make sure it hasn't made a mistake. If it finds a mistake, it says "Fail" and stops, rather than giving you a wrong answer.

The Bottom Line

The paper shows that while finding the Pauli decomposition is usually a nightmare, it becomes a breeze if you know the input is "sparse" (has few active parts). By using random sampling and clever folding tricks, the authors have built a tool that can efficiently decode these structured matrices, making it much more feasible to load data into near-term quantum computers.

In short: They found a way to solve a massive puzzle by realizing you don't need to look at every piece—you just need to look at the right ones, randomly, and fold the rest until they reveal themselves.

Technical Summary: An Efficient Pauli Decomposition Algorithm for Structured Matrices

Problem Statement
The decomposition of classical $2^n \times 2^n$ matrices into linear combinations of Pauli strings is a critical bottleneck for end-to-end implementations of near-term quantum algorithms, particularly in chemistry, machine learning, and finance. Many algorithms, such as the Variational Quantum Eigensolver (VQE) and linear algebra solvers, assume input data is provided as a Linear Combination of Unitaries (LCU) of Pauli strings. However, for general classically-specified matrices, this decomposition is not known a priori.

Existing algorithms for generic, dense matrices scale exponentially with the number of qubits $n$ . The most straightforward approach requires $O(32^n)$ time, while the best-known existing methods (e.g., in PennyLane) scale as $O(n4^n)$ . This exponential cost arises because, in the worst case, a matrix has support on all $4^n$ Pauli basis elements, requiring the recovery of all coefficients.

This paper addresses a promise version of the Pauli decomposition problem. It assumes the input matrix $M$ is guaranteed to have support on only $k = \text{poly}(n)$ Pauli strings. Furthermore, the matrix is accessed via a classical sparse query model, where an algorithm can retrieve the non-zero entries of a specific row or column without constructing the full $2^n \times 2^n$ matrix in memory. The goal is to recover the exact Pauli decomposition (the set of Pauli strings and their coefficients) with high probability using resources polynomial in $n$ , $k$ , and $\log(1/\delta)$ .

Methodology
The authors propose a randomized classical algorithm that exploits the promised sparsity ( $k$ ) and the structure of Pauli strings in binary symplectic form. The algorithm decomposes the problem into three main stages:

Discovery of Active Pauli-X Parts ( $x$ ):
Using Lemma 1, which relates the row index $v$ , column index $u$ , and the Pauli-X part $x$ via $x = u \oplus v$ , the algorithm queries random rows of the matrix. By collecting the column indices of non-zero entries and XORing them with the row indices, the algorithm identifies the set $X$ of distinct $x$ bit strings present in the decomposition. This step relies on the Boolean uncertainty principle (Fact 1) to ensure that random queries reveal active $x$ strings with high probability.
Decoding Unique $x$ Strings:
For each discovered $x$ , the algorithm checks if it is "unique" (i.e., associated with exactly one Pauli string, so $p_x = 1$ ). If unique, the query function $b_x(u) = M_{x \oplus u, u}$ reduces to a single Walsh character $\beta_x(z)(-1)^{z \cdot u}$ . The algorithm recovers the associated Pauli-Z part $z$ and coefficient $\beta$ by evaluating $b_x$ at the zero vector and standard basis vectors. A certification step using random inputs verifies that the candidate solution is not a degenerate case that coincidentally matches the queried points.
Decoding Degenerate $x$ Strings:
If an $x$ is "degenerate" (associated with $p_x \geq 2$ Pauli strings), the problem reduces to recovering a sparse Walsh-Hadamard spectrum. The algorithm employs a random folding technique:
- It maps the $n$ -bit spectral indices ( $z$ ) into $m$ -bit bins using a random binary matrix $R$ , where $m \ll n$ .
- This "folding" isolates individual $z$ strings into "singleton bins" with high probability.
- For a singleton bin, the algorithm uses shifted queries to determine the bits of the $z$ string and its coefficient.
- Recovered terms are subtracted from the residual function, and the process repeats until all terms for that $x$ are found.
- A final randomized verification ensures no terms were missed.

Key Contributions

Algorithm Design: The paper presents a randomized classical algorithm (Algorithm 1) that solves the Pauli decomposition problem under the promise of $k$ -sparsity and sparse query access.
Complexity Improvement: Unlike existing methods that scale exponentially in $n$ , the proposed algorithm achieves query and runtime complexity that is polynomial in $n$ , $k$ , and $\log(1/\delta)$ .
Theoretical Guarantees: The algorithm succeeds with probability at least $1-\delta$ for any user-chosen $\delta \in (0, 1)$ . The authors provide rigorous bounds on failure probabilities for each stage (discovery, unique decoding, and degenerate decoding).
Sparse Walsh-Hadamard Techniques: The work adapts sparse recovery techniques from the Boolean cube (specifically sparse Walsh-Hadamard decoding) to the context of Pauli decomposition, utilizing random folding and shift-based bit recovery.

Results

Numerical Benchmarks: The authors tested the algorithm on random instances for $n = 2$ $n = 2$ to $30$ with $k = 2^n$ $k = 2^{n}$ .
- For small $n$ ( $n < 10$ ), the overhead of the randomized algorithm makes it slower than the existing PennyLane PauliDecompose routine.
- A crossover occurs around $n=10$ . For $n > 10$ , the proposed algorithm significantly outperforms the exponential-time baseline.
- The observed runtime and query counts scale polynomially with $n$ , consistent with the theoretical bounds.
- In all tested runs, the algorithm successfully recovered the full decomposition without failure.
Scalability: The algorithm successfully handled instances up to $n=30$ , a regime where constructing the full matrix or running dense decomposition algorithms becomes computationally intractable.

Significance and Claims
The paper claims that while finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices known to be sparse in the Pauli basis. This regime is highly relevant for near-term quantum algorithms operating on structured classical input data.

The authors emphasize that their algorithm is specifically designed for the promise problem where $k = \text{poly}(n)$ . They do not claim to solve the general dense case. The significance lies in enabling efficient classical preprocessing for quantum algorithms that require Pauli decompositions, potentially removing a major bottleneck in end-to-end quantum workflows. The work also highlights specific application contexts, such as matrices defined by succinct classical rules or data held by untrusted servers where only query access is available.

The paper concludes modestly, noting that the derived upper bounds may be loose and that future work could explore tighter bounds, lower bounds, and extensions to approximately sparse matrices.