⚛️ quantum physics

Approximate simulation of complex quantum circuits using sparse tensors

This paper introduces a method for approximately simulating complex quantum circuits using a sparse tensor data structure and efficient contraction algorithms that enable scalable classical simulation without relying on underlying symmetries.

Original authors: Benjamin N. Miller, Peter K. Elgee, Jason R. Pruitt, Kevin C. Cox

Published 2026-02-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benjamin N. Miller, Peter K. Elgee, Jason R. Pruitt, Kevin C. Cox

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

Imagine you are trying to predict the outcome of a massive, chaotic game of "telephone" played by a billion people. In the world of quantum computing, this game is a quantum circuit, and the "message" being passed around is a quantum state.

Simulating this game on a regular computer is incredibly hard. If you try to write down every possible message that could exist at the end, the list becomes so long (2 to the power of N) that it would fill the entire universe with paper. This is why classical computers usually struggle to keep up with quantum ones.

This paper introduces a new tool called TruSTS (Truncated Sparse Tensor Simulation) to solve this problem. Here is how it works, explained through simple analogies:

1. The "Sparse" List vs. The "Full" Encyclopedia

Usually, to simulate a quantum system, you need a list containing every single possible outcome, even the ones that are impossible or have zero chance of happening. It's like trying to read a dictionary that includes every word in every language, even words that don't exist, just in case.

TruSTS is different. It only keeps a short, "sparse" list of the outcomes that actually matter.

The Analogy: Imagine you are tracking a crowd of people. Instead of writing down the name of every single person in the world (most of whom aren't there), you only write down the names of the 100 people you actually see. If a new person enters the crowd, you add them to your list. If someone leaves, you cross them off. You never write down the empty space.

2. The "Gate" and the "Sorting Hat"

In a quantum circuit, "gates" are like operations that change the state of the qubits (the players in our game). When a gate acts on two qubits, it can potentially split one outcome into four new possibilities.

If you didn't have TruSTS, your list of outcomes would explode in size every time a gate was applied, quickly becoming too big to handle.

The Analogy: Imagine a sorting machine at a post office. When a letter (a quantum state) arrives, the machine might split it into four different envelopes. If you let this happen without limits, you'd have a mountain of envelopes.
The TruSTS Trick: The paper describes a clever way to use bitwise operations (think of them as digital scissors and glue) to sort these envelopes. It groups similar letters together so the computer can process them all at once, rather than one by one. This makes the math much faster.

3. The "Top-K" Truncation (The Bouncer)

Here is the most critical part. Even with the sorting trick, the list of outcomes can still grow too big. TruSTS has a strict rule: You can only keep a fixed number of items on your list (let's say, $k$ items).

Every time the list gets too full, a "bouncer" kicks out the least important items.

The "Top-K" Method: The bouncer looks at the list and kicks out the items with the lowest "probability" (the least likely outcomes). It keeps the "Top-K" most important ones.
The "Random-K" Method: The paper also tested a bouncer that kicks out random items just to see what happens. As you might guess, the "Top-K" bouncer is much better at keeping the simulation accurate.

4. The Trade-off: Speed vs. Accuracy

The paper shows that this method creates a useful trade-off.

If you keep a small list (small $k$ ): The simulation is incredibly fast and uses very little memory, but the result might be a bit fuzzy (lower "fidelity").
If you keep a larger list (large $k$ ): The simulation takes longer but is much more accurate.

The authors found that for up to 64 qubits, the time it takes to run the simulation doesn't get much slower just because you add more qubits, as long as you keep the list size ( $k$ ) small. This is a big deal because most other methods get exponentially slower as you add more qubits.

5. What Did They Prove?

The researchers tested this on random, complex quantum circuits (the kind that are hardest to simulate). They found:

Efficiency: Their method is fast and scales well.
Accuracy: They developed a way to predict how accurate the result will be based on how much "probability" they kept in the list.
Comparison: They compared their method to another popular technique called "Matrix Product States" (MPS). They found that for certain types of random circuits, their method behaves differently, offering a different set of pros and cons.

Summary

Think of TruSTS as a smart, efficient editor for a chaotic story. Instead of trying to write down every single word that could be said in a quantum story (which is impossible), it keeps a running draft of only the most likely sentences. It constantly edits out the nonsense, sorts the remaining sentences to make them easier to read, and gives you a story that is short enough to fit on a page but still tells the truth about the most important parts of the plot.

This tool doesn't replace the need for quantum computers, but it gives scientists a powerful new way to test and understand quantum circuits using the computers we already have.

Technical Summary: Approximate Simulation of Complex Quantum Circuits Using Sparse Tensors

Problem Statement
The simulation of quantum circuits on classical computers is essential for defining the boundary of verifiable quantum advantage, solving quantum many-body problems, and guiding hardware development. While tensor network methods (e.g., Matrix Product States, Density Matrix Renormalization Group) have become state-of-the-art for simulating complex circuits, they often rely on underlying symmetries or low dimensionality to achieve efficiency. Furthermore, general classical simulation is bounded by complexity theory ( $P \neq NP$ ), preventing universal polynomial-time simulators. The authors identify a need for simulation tools that can approximate quantum states without requiring singular value decomposition (SVD), underlying symmetries, or low dimensionality, specifically targeting circuits where traditional tensor networks may struggle.

Methodology: Truncated Sparse Tensor Simulation (TruSTS)
The paper introduces TruSTS, a method for approximately simulating quantum circuits using sparsely-populated tensors. The core approach involves representing an $N$ -qubit quantum state $|\psi\rangle$ as a sparse state $|\phi\rangle$ , which is a linear combination of $k$ basis states ( $k \le 2^N$ ).

Data Structure: The sparse state is stored using two fixed-length arrays of size $k$ $k$ :
1. $x[x_i]$ : An array of integer coordinates representing the binary bitstrings of the basis states.
2. $\alpha[\alpha_i]$ : An array of complex probability amplitudes corresponding to those basis states.
3. An integer pointer nnz tracks the number of currently filled elements.
Bitwise Contraction Algorithm: To apply a quantum gate (represented as a tensor $\hat{U}$ $\hat{U}$ ), the algorithm employs a bitwise sorting strategy inspired by Compressed Sparse Row (CSR) matrix multiplication:
1. A bitmask is defined to select the qubits coupled by the gate.
2. The state array is sorted based on the "uncoupled" bits (the complement of the mask). This groups basis states into computationally independent sub-arrays where the gate acts identically.
3. The gate is applied via independent $4\times4$ matrix contractions to each sub-array.
4. This process can increase the number of non-zero terms (nnz) by a factor of up to four per gate application.
Truncation: To prevent exponential growth of nnz, the algorithm truncates the state back to size $k$ $k$ after each gate. The paper compares two truncation strategies:
- Top-k: Retains the $k$ terms with the largest probability amplitudes.
- Random-k: Retains $k$ terms chosen randomly.
- A renormalization factor $\gamma$ is applied to $|\phi\rangle$ to account for the probability mass lost during truncation.

Key Contributions and Theoretical Derivations
The authors derive relationships between the renormalization parameter $\gamma$ and the simulation fidelity $f = |\langle \psi | \phi \rangle|^2$ .

Fidelity Bounds: They establish that for random quantum circuits, the expected fidelity $\bar{f}$ is approximately $\gamma^2$ (the probability mass retained), with a slight positive deviation due to interference terms.
Upper and Lower Limits:
- A lower bound $\bar{f}_{min} \approx 1/2^N$ is derived for the case where the state is truncated to a single random basis state.
- An upper bound $f_{max}$ is derived assuming the output distribution follows a Porter-Thomas distribution. This bound represents the best possible fidelity if one could identify and keep the $k$ most probable bitstrings after the circuit execution, rather than truncating mid-circuit. The paper notes that $f_{max} \approx d(1 - \ln d)$ , where $d = k/2^N$ is the truncation fraction.

Results
The authors benchmarked TruSTS on random quantum circuits consisting of Haar-random two-qubit unitaries arranged in layers.

Fidelity vs. Truncation: Simulations on $N=24$ qubits show that the fidelity of the approximate state scales approximately with the squared renormalization factor $\gamma^2$ . Top-k truncation consistently outperforms random-k truncation by concentrating probability in the retained terms.
Runtime Scaling:
- Versus $k$ : The runtime per gate scales linearly with the number of kept terms $k$ .
- Versus $N$ : For $k \ll 2^N$ , the runtime per gate is roughly constant with respect to the number of qubits $N$ (tested up to $N=64$ ). This indicates the algorithm does not introduce overhead dependent on the full Hilbert space size, provided the state remains sparse.
- Memory: The method avoids allocating full $2^N$ memory, storing only $k$ terms.
Comparison with MPS: A preliminary comparison with Matrix Product States (MPS) using the quimb library on $N=24$ qubits (5 layers) shows that for the tested parameters, MPS offers a more favorable runtime-fidelity tradeoff over most of the data range, maintaining higher fidelity for comparable runtimes. However, TruSTS demonstrates a steady, predictable decay in fidelity as runtime increases, reaching a lower limit near $f \sim 10^{-8}$ .

Significance and Claims
The paper positions TruSTS as a tool to extend the capabilities of tensor network-based simulators, particularly for scenarios where:

Symmetry is absent: The method does not rely on underlying symmetries or low dimensionality.
SVD is avoided: It achieves truncation without the computational cost of Singular Value Decomposition.
Inherent sparsity exists: It is attractive for quantum states that are inherently sparse.

The authors claim that TruSTS provides a useful tradeoff between fidelity and runtime, potentially finding immediate application in circuits where high fidelity is not strictly required. They emphasize that this work serves as a foundation for future research into optimizing sparse tensor networks and combining TruSTS with tensor network contraction order optimization strategies to further push the boundary of classical simulation for complex quantum systems. The authors remain modest, noting that rigorous comparison to alternate methods and investigations using measurable quantities (like cross-entropy fidelity) are important areas for future work.