⚛️ quantum physics

Randomized truncation of quantum states

This paper presents efficient algorithms for constructing optimal random mixtures of sparse or low-entanglement quantum states that significantly improve approximation accuracy in trace distance and robustness compared to deterministic methods, offering practical benefits for matrix product state truncation without increasing computational or memory costs.

Original authors: Aram W. Harrow, Angus Lowe, Freek Witteveen

Published 2026-10-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Aram W. Harrow, Angus Lowe, Freek Witteveen

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

In the quantum world, information is stored in states that can be incredibly complex, existing in many places at once. To make sense of these states, scientists often try to simplify them, keeping only the most important parts while discarding the rest. This process is called truncation. Imagine trying to describe a vast, intricate landscape by listing only the tallest mountains; you keep the biggest features and ignore the smaller hills. In quantum computing, this is usually done by looking at a list of numbers that describe the state, sorting them from largest to smallest, and keeping only the top few. This deterministic method is reliable and straightforward, but it treats the discarded information as simply gone. However, there is a growing realization that sometimes, throwing away information completely is not the most efficient way to handle it.

A team of researchers has discovered that by introducing a specific kind of randomness into this simplification process, they can achieve a much better approximation of the original quantum state than the traditional method allows. Instead of just picking the biggest numbers and keeping them, their new approach creates a mixture of different simplified versions of the state. By randomly selecting which parts of the state to keep in each version and then averaging them together, they can reduce the error significantly. This finding challenges the standard practice of simply keeping the largest values and suggests that a little bit of controlled chaos can lead to a clearer picture of the quantum reality.

The core of this work lies in solving a difficult mathematical puzzle: how to best approximate a complex quantum state using a simpler one that has limited complexity. In the language of quantum physics, a "pure" state is a single, precise configuration, while a "mixed" state is a collection of different possibilities. The researchers focused on states that are "sparse," meaning they have very few non-zero components. The traditional way to find the best sparse approximation is to look at the list of numbers describing the state, sort them, and keep the largest ones. This is the best possible answer if you are forced to pick just one specific simplified state. However, the researchers proved that if you are allowed to use a mixture of several different sparse states, you can do much better. They developed efficient computer algorithms to find the perfect recipe for this mixture.

The key insight is that the optimal solution is not a single state, but a probability distribution over many states. Think of it like this: if you are trying to guess the average height of a group of people, you could pick the tallest person and say that is your answer, but you would be wrong. A better approach might be to randomly pick a few different people, measure them, and take the average. In the quantum case, the researchers found that by randomly sampling different subsets of the state's components and combining them in a specific way, they could minimize the difference between their approximation and the true state. This difference is measured by a standard metric called trace distance, which tells you how distinguishable two states are. Their method showed that the error in this distance could be reduced quadratically, meaning if the old method had an error of a certain size, the new method could reduce it to the square of that size, which is a massive improvement for small errors.

To make this work, the team had to solve a complex sampling problem. They needed a way to randomly select groups of numbers from a larger list, ensuring that each number had a specific chance of being included, while also ensuring that the selection of one number influenced the likelihood of selecting others in a precise, negative way. This is known as conditional Poisson sampling. The researchers not only proved that such a sampling method exists but also created new, faster computer algorithms to perform it. These algorithms allow a computer to generate the random mixtures needed for the approximation without getting bogged down in calculation time. The result is a method that is just as fast as the old way but produces a much more accurate result.

The practical application of this discovery is most immediate in the simulation of quantum many-body systems, which are used to model materials and chemical reactions. These simulations often rely on a technique called matrix product states, which breaks a large quantum system into smaller, manageable chunks. A critical step in these simulations is truncating the connections between these chunks to keep the computer memory usage low. Traditionally, this is done by keeping the largest values, which introduces errors. By replacing this step with the new randomized method, scientists can run these simulations with higher accuracy without needing more memory or significantly more time. The researchers tested this numerically on simulated quantum systems and found that for certain types of states, the new method reduced the error by an order of magnitude compared to the standard approach.

The paper also addresses the limits of this improvement. The researchers showed that the benefit of this randomized approach depends heavily on how the numbers in the quantum state are distributed. If the numbers drop off very quickly, the improvement is dramatic. If they drop off slowly, the benefit is smaller, though still present. They also clarified that this advantage applies specifically to pure quantum states. If the state being approximated is already a messy mixture of many possibilities, the problem becomes much harder, and the simple rules they found for pure states do not apply. In fact, they proved that finding the best approximation for a general mixed state is computationally impossible to solve efficiently for large systems, highlighting that their success relies on the specific structure of pure states.

Ultimately, this work demonstrates that in the realm of quantum information, randomness is not just a source of noise to be eliminated, but a powerful resource that can be harnessed. By carefully designing how randomness is applied, the researchers found a way to squeeze more accuracy out of limited resources. Their algorithms provide a concrete tool for improving the fidelity of quantum simulations, potentially allowing scientists to model complex physical phenomena with greater precision. The findings suggest that the future of quantum simulation may lie not just in building bigger computers, but in smarter ways of using the ones we have, turning the act of simplification into a more sophisticated and effective process.

Technical Summary: Randomized Truncation of Quantum States

1. Problem Statement

The paper addresses the fundamental task of approximating a pure quantum state $v$ (represented as a unit vector in $\mathbb{C}^d$ ) using states with limited complexity. Specifically, the goal is to approximate $v$ using a mixture of $k$ -sparse states (states with at most $k$ non-zero entries in the standard basis) or, for bipartite systems, a mixture of states with Schmidt rank at most $k$ .

Traditionally, this "truncation" problem is solved deterministically by keeping the $k$ largest entries (or singular values) of the vector and discarding the rest. While this deterministic approach is optimal for maximizing fidelity (or minimizing trace distance among pure approximations), the authors investigate whether randomized mixtures of sparse states can achieve better accuracy under standard distance measures.

The paper focuses on two primary error metrics:

Trace Distance ( $T$ ): A measure of additive error, defined as $T(\rho, \sigma) = \frac{1}{2}\|\rho - \sigma\|_1$ .
Robustness ( $R$ ): A measure of multiplicative error, defined as the minimum $s \ge 0$ such that $\frac{\rho + s\sigma}{1+s}$ belongs to the set of free states (mixtures of $k$ -sparse states).

2. Methodology and Theoretical Framework

2.1 The Advantage of Randomization

The central insight is that while the optimal pure approximation is deterministic (keeping the top $k$ entries), the optimal mixed approximation is generally a probabilistic ensemble. The authors frame the trace distance minimization as a zero-sum game between a player choosing a mixed state $\sigma$ (to minimize distinguishability) and a player choosing a measurement $M$ (to maximize it). Game-theoretic principles suggest that mixed strategies often outperform pure strategies in such equilibrium settings.

Geometrically, the paper argues that a convex combination of pure states can lie closer to the target state in trace distance than any single pure state in the convex hull, achieving a quadratic improvement in error (i.e., $O(\epsilon)$ vs $O(\sqrt{\epsilon})$ ) in specific regimes.

2.2 Mathematical Tools

The construction of optimal approximations relies on several advanced mathematical tools:

Convex Optimization and Duality: The problem is formulated using the $k$ -support norm (dual to the top- $k$ norm). The robustness of a pure state is shown to be exactly $\|v\|_{(k,*)}^2 - 1$ .
Minimax Theorems: Used to establish the existence of saddle points for the trace distance optimization, proving that the optimal measurement operator is rank-1.
Conditional Poisson Sampling: The core algorithmic challenge involves sampling subsets of indices $S$ of a fixed size $r+1$ such that the marginal inclusion probabilities $q_i = \Pr(i \in S)$ match specific values derived from the target vector. This is a known problem in survey sampling.
Maximum Entropy Distributions: The authors utilize the maximum-entropy distribution subject to marginal constraints to generate the optimal ensemble. This distribution takes the form $p_\mu(S) \propto e^{-\sum_{j \in S} \mu_j}$ .

3. Key Contributions and Algorithms

3.1 Efficient Algorithms for Optimal Approximation

The paper provides efficient algorithms to compute and sample from the optimal randomized approximations for both trace distance and robustness.

Trace Distance (Section 4):
- Computation: An algorithm (Algorithm 1) computes the optimal trace distance $T_k(v)$ and the optimal distinguishing measurement $M_\star$ in time $O(dk + d \log d)$ . The solution involves solving a cubic equation to find a Lagrange multiplier $\lambda$ .
- Structure: The optimal mixed state $\sigma_\star$ is an ensemble of states $w(S)$ . These states deterministically keep the top $k-r-1$ entries, truncate entries beyond a certain index $\ell$ , and randomly sample $r+1$ entries from the intermediate range $\{k-r, \dots, \ell-1\}$ with specific marginal probabilities.
- Sampling: The paper provides algorithms to sample from this ensemble in $O(d)$ time after an initial $poly(d, \log(1/\eta))$ preprocessing step to find the distribution parameters.
Robustness (Section 5):
- The authors show that the optimal robustness approximation is also a mixture of $k$ -sparse states derived from a maximum-entropy distribution.
- They provide an algorithm to compute the optimal density matrix and sample from the corresponding ensemble with similar efficiency guarantees.

3.2 Improved Algorithms for Conditional Poisson Sampling (Section 8)

A significant portion of the work is dedicated to the sub-routine of conditional Poisson sampling (sampling fixed-size subsets with prescribed marginals). The authors improve upon existing literature (e.g., [CDL94, Til06]) by providing:

Fast Partition Function Computation: Computing the normalization constant $Z_\mu$ in $O(n \log^2 \ell \log \log \ell)$ time.
Efficient Marginal Calculation: Computing single and two-element marginals in $O(n\ell)$ and $O(n^2)$ time, respectively.
Fast Sampling: An algorithm to sample from the distribution in expected $O(n \log n)$ time using a rejection-sampling-like procedure based on Glauber dynamics.
Inference (Finding Parameters): Several algorithms (Accelerated Projected Gradient Descent, Box-Constrained Newton, Iterative Proportional Fitting with Fixed weights) are presented to find the distribution parameters $\mu$ given target marginals $q$ . The Box-Constrained Newton method is highlighted for its favorable runtime scaling, potentially matching or beating the cost of Singular Value Decomposition (SVD) in certain regimes.

4. Results and Analysis

4.1 Quadratic Improvement Conditions

The paper analyzes when the randomized truncation offers a significant advantage over the deterministic one.

Uniform States: For the uniform state (maximally entangled in bipartite cases), the randomized method achieves a trace distance of $O(\epsilon)$ , whereas the deterministic method yields $O(\sqrt{\epsilon})$ .
Power Law States: For states with coefficients decaying as $i^{-\gamma}$ $i^{- γ}$ , the advantage depends on the exponent $\gamma$ $γ$ :
- If $\gamma < 1/2$ or $\gamma > 1$ , a quadratic improvement ( $O(\epsilon)$ ) is achieved.
- If $1/2 < \gamma < 1$ , the improvement is sub-quadratic but still better than the deterministic $O(\sqrt{\epsilon})$ .
No Advantage Cases: For states where the weight is highly concentrated on a few entries (e.g., $v = (\sqrt{1-\epsilon}, \sqrt{\epsilon}, \dots)$ with $k=1$ ), the randomized method offers little to no asymptotic improvement in trace distance, though it remains the only way to achieve non-trivial robustness.

4.2 Application to Matrix Product States (MPS)

The authors apply their method to the truncation of Matrix Product States, a standard technique in simulating quantum many-body systems.

Method: Instead of keeping the top $\chi$ Schmidt coefficients deterministically at each bond, the algorithm samples a subset of coefficients according to the optimal randomized distribution.
Numerical Results: Simulations on 10-qubit states show that for power-law entanglement spectra with heavy tails (small $\gamma$ ), the randomized truncation reduces the relative error in estimating observables (like $\langle Z_5 Z_6 \rangle$ ) by an order of magnitude compared to deterministic truncation, particularly at low bond dimensions.
Cost: The computational overhead is dominated by the inference step for the sampling weights. The authors argue this cost is subleading compared to the SVD required for the deterministic truncation itself, making the method a viable "drop-in" replacement.

5. Significance and Claims

The paper claims that randomized truncation is a superior strategy for approximating pure quantum states when the goal is to minimize trace distance or robustness, provided the state has a sufficiently "spread out" spectrum.

Optimality: The authors provide the first efficient algorithms to find the optimal randomized approximation, moving beyond heuristics.
Efficiency: The algorithms run in polynomial time, with the most expensive step (inference) being comparable to or faster than the SVD used in standard tensor network algorithms.
Theoretical Insight: The work bridges quantum information theory with convex optimization and survey sampling, demonstrating that the "free" resource of randomness can be leveraged to overcome the limitations of deterministic sparsity constraints.
Practical Impact: The numerical results suggest that incorporating randomized truncation into MPS algorithms (like TEBD or DMRG) can significantly improve simulation accuracy without increasing the bond dimension or asymptotic runtime.

The authors remain modest regarding the universality of the improvement, noting that for highly localized states (e.g., $k=1$ with large gaps), the benefit is limited, and the method's utility depends on the specific decay of the target state's coefficients.