⚛️ quantum physics

On estimating Schatten norm and power distances between quantum states

This paper establishes the computational complexity of estimating Schatten $\alpha$ -norm distances between quantum states by presenting an efficient polynomial-time quantum estimator for $\alpha > 1$ that achieves an exponential speedup over prior work, while proving that the problem becomes QSZK-complete and intractable for $1 \leq \alpha \leq 1 + \text{negl}(n)$ and $0 < \alpha < 1$ under standard complexity assumptions.

Original authors: Yupan Liu, Qisheng Wang

Published 2026-06-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yupan Liu, Qisheng Wang

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 have two mysterious boxes, Box A and Box B. Inside each box is a complex, invisible quantum state (think of it as a unique, shimmering cloud of probability). Your goal is to figure out: How different are these two clouds?

In the quantum world, we have many ways to measure "difference." The most famous one is the Trace Distance. Think of this like measuring the distance between two cities on a map using a straight line. It's the gold standard for telling if two quantum states are distinct.

However, sometimes the straight line isn't enough. Maybe you want to measure the "curved" distance, or the distance through a specific type of terrain. This is where Schatten Norms come in. They are like different types of rulers or maps. Some rulers (called $\alpha$ ) are straight and sharp, while others are rounded or soft.

This paper is about building a super-fast, high-tech scanner that can measure the difference between these two quantum clouds using these different rulers, and figuring out exactly how hard it is to do so.

The Two Main Rules of the Game

The authors discovered a fascinating split in how hard this measurement is, depending on which ruler you pick:

1. The "Easy" Zone: Rulers with $\alpha > 1$

Imagine you have a ruler that is slightly curved or stretched (where $\alpha$ is a number bigger than 1, like 1.5 or 2).

The Old Way: Previous scientists tried to measure this by first listing every single tiny detail of the clouds (their "rank"). If the clouds were huge and complex, this took forever—like trying to count every grain of sand on a beach to measure the distance between two piles. The time it took grew exponentially with the size of the clouds.
The New Way (This Paper): The authors built a new scanner that doesn't care how complex the clouds are. It ignores the "grains of sand" and looks at the big picture directly.
- The Result: They created an algorithm that is rank-independent. Whether the clouds are simple or incredibly complex, the scanner takes roughly the same amount of time.
- The Analogy: It's like switching from counting every single brick in a wall to simply measuring the wall's shadow with a laser. It's exponentially faster.

2. The "Hard" Zone: Rulers with $\alpha < 1$

Now, imagine a ruler that is very squishy or compressed (where $\alpha$ is a number between 0 and 1).

The Problem: In this zone, the "straight line" distance doesn't work well anymore. The math gets messy, and the distance measure stops behaving like a normal ruler (it breaks the triangle inequality, meaning the shortest path between two points might not be a straight line).
The Solution: The authors suggest using a "powered" version of this distance (squaring or cubing the result) to make it behave like a proper ruler again.
The Catch: For these squishy rulers, you cannot escape the complexity. The scanner still needs to know roughly how complex the clouds are (their rank). The time it takes grows with the complexity, though the authors made it much more efficient than before.

The "Dichotomy" (The Big Split)

The paper reveals a sharp "phase transition" in the quantum world, similar to how water instantly turns to ice at 0°C.

If you use a ruler where $\alpha = 1$ (The Trace Distance): The problem is "QSZK-complete." This is a fancy way of saying it's very hard for a quantum computer to solve efficiently. It's like trying to solve a complex puzzle where you have to prove you know the answer without showing your work. It's a cryptographic-level difficulty.
If you use a ruler where $\alpha > 1$ (Even slightly bigger, like 1.001): The problem suddenly becomes easy (BQP-complete). A quantum computer can solve it efficiently.
The Surprise: The authors show that you don't need to jump to a huge number like 2 or 3 to get this speedup. Even a tiny step above 1 (like 1.001) changes the problem from "impossible to solve quickly" to "easy to solve quickly."

How Did They Do It? (The Secret Sauce)

To build their super-fast scanner, the authors used a mathematical trick called Quantum Singular Value Transformation (QSVT).

Think of QSVT as a magical lens that can reshape the light coming from the quantum clouds.

The Challenge: To measure the distance, they needed to apply a specific mathematical function to the clouds. But this function was "signed" (it had positive and negative parts) and "power-based" (it involved exponents).
The Trick: They found a way to approximate this complex function using simple polynomials (like drawing a smooth curve with a series of straight lines).
The Innovation: Previous methods required them to know the "rank" (complexity) of the clouds to draw these lines. The authors found a specific type of polynomial approximation that works perfectly well without knowing the rank. This allowed them to build a scanner that works equally fast for simple and complex clouds.

Summary of Findings

For $\alpha > 1$ : We can now estimate the distance between quantum states exponentially faster than before. We don't need to know how complex the states are. This makes the problem easy for quantum computers.
For $0 < \alpha < 1$ : We can estimate the distance, but we still need to know the complexity (rank) of the states. However, the authors made this process much more efficient than previous attempts.
The Boundary: There is a sharp line between "hard" and "easy" right at $\alpha = 1$ . As soon as you go even a tiny bit above 1, the problem becomes easy.

What This Means (According to the Paper)

The paper focuses entirely on the computational complexity (how hard it is to calculate) and the algorithms (the steps to calculate it).

It proves that for certain types of quantum distance measurements, quantum computers have a massive advantage over older methods.
It provides the specific "blueprints" (algorithms) for these new scanners.
It establishes the theoretical limits: some problems are inherently hard (requiring knowledge of the state's rank), while others are inherently easy (independent of rank).

The authors do not claim this will immediately fix medical devices or create new quantum computers. Instead, they have solved a fundamental puzzle in the theory of quantum computing: How do we efficiently measure the difference between quantum states using different mathematical lenses? They found that for most lenses, the answer is "very efficiently," provided you use their new method.

Technical Summary: Estimating Schatten Norm and Power Distances Between Quantum States

Problem Statement

The paper investigates the computational complexity of estimating the distance between two $n$ -qubit quantum states, $\rho_0$ and $\rho_1$ , given by their state-preparation circuits. The primary focus is on the Quantum Schatten $\alpha$ -norm distance, defined as $T_\alpha(\rho_0, \rho_1) := \frac{1}{2}\|\rho_0 - \rho_1\|_\alpha = \frac{1}{2}\text{tr}(|\rho_0 - \rho_1|^\alpha)^{1/\alpha}$ , and its powered version, the Quantum Schatten $\alpha$ -power distance, $\Lambda_\alpha(\rho_0, \rho_1) := \frac{1}{2}\text{tr}(|\rho_0 - \rho_1|^\alpha)$ .

The central question addressed is the computational complexity of the Quantum State Distinguishability Problem with Schatten $\alpha$ -norm (QSD $_\alpha$ ): deciding whether $T_\alpha(\rho_0, \rho_1) \geq 2/5$ or $T_\alpha(\rho_0, \rho_1) \leq 1/5$ . The authors aim to resolve a dichotomy in complexity between the trace distance ( $\alpha=1$ ), which is known to be QSZK-complete, and $\ell_2$ -like measures (e.g., Hilbert-Schmidt distance, $\alpha=2$ ), which are in BQP. Specifically, they ask whether this dichotomy holds for all constants $\alpha > 1$ or if the complexity depends on whether $\alpha$ is an even or odd integer.

Additionally, the paper studies the regime $0 < \alpha < 1$ . In this range, $T_\alpha$ is no longer a metric (failing the triangle inequality), whereas $\Lambda_\alpha$ remains a valid distance metric (a quasi-norm power). The authors seek efficient estimators for $\Lambda_\alpha$ in this regime.

Methodology

1. Efficient Quantum Estimators

The authors develop quantum algorithms based on Quantum Singular Value Transformation (QSVT) and Linear Combinations of Unitaries (LCU).

For $\alpha > 1$ (Rank-Independent):
The core challenge is approximating the function $f(x) = \text{sgn}(x)|x|^{\alpha-1}$ efficiently. The authors utilize best uniform polynomial approximations (inspired by Bernstein's work and recent results on Tsallis entropy) for signed positive powers.
- They construct a polynomial $P(x)$ that approximates $\frac{1}{2}\text{sgn}(x)|x|^{\alpha-1}$ with uniform error $\epsilon$ over $[-1, 1]$ .
- Using QSVT, they implement a block-encoding of $\text{sgn}(\nu)|\nu|^{\alpha-1}$ where $\nu = \rho_0 - \rho_1$ .
- The distance is estimated by computing $\text{tr}(\rho_0 \cdot \text{sgn}(\nu)|\nu|^{\alpha-1}) - \text{tr}(\rho_1 \cdot \text{sgn}(\nu)|\nu|^{\alpha-1})$ via Hadamard tests.
- Key Innovation: Unlike prior approaches (e.g., [WGL+24]) that relied on rank-dependent block-encodings of projectors, this method uses polynomial approximations that do not depend on the rank of the states, achieving rank-independent query and sample complexity.
For $0 < \alpha < 1$ (Rank-Efficient):
In this regime, the function $x^{\alpha-1}$ has a singularity at $x=0$ . The authors use polynomial approximations for scaled signed powers that are valid away from zero (using a cutoff $\delta$ ).
- The algorithm estimates $\Lambda_\alpha$ by approximating $\text{sgn}(\nu)|\nu|^{\alpha-1}$ with a polynomial that is bounded but incurs error near zero.
- This approach results in a rank-dependent complexity, specifically polynomial in the rank $r$ , but improves upon previous bounds.

2. Hardness and Lower Bounds

To establish computational hardness, the authors derive new rank-dependent inequalities relating the trace distance $T(\rho_0, \rho_1)$ to $T_\alpha$ and $\Lambda_\alpha$ .

Inequalities: They prove that for pure states, $T_\alpha$ and $T$ are related by a constant factor, but for mixed states, the relationship depends on the ranks of the states. Specifically, $T(\rho_0, \rho_1) \leq 2(\text{rank}(\rho_0)^{1-\alpha} + \text{rank}(\rho_1)^{1-\alpha})^{-1/\alpha} T_\alpha(\rho_0, \rho_1)$ .
Reductions:
- BQP-hardness: By restricting to pure states, the authors show that distinguishing states via $T_\alpha$ (for $\alpha \geq 1$ ) or $\Lambda_\alpha$ (for $0 < \alpha < 1$ ) is as hard as the standard BQP-complete problem (PureQSD).
- QSZK-hardness: For $\alpha$ negligibly close to 1 (specifically $1 \leq \alpha(n) \leq 1 + \text{negl}(n)$ ), they use a partial polarization lemma for $T_\alpha$ . This lemma allows them to amplify the gap in $T_\alpha$ similar to how polarization works for trace distance, proving that QSD $_\alpha$ is QSZK-complete in this regime.
- For constant $0 < \alpha < 1$ , they show PoweredQSD $_\alpha$ is QSZK-hard by applying polarization to the trace distance and using the upper bound of $\Lambda_\alpha$ in terms of $T^\alpha$ and rank.

Key Contributions and Results

1. Efficient Quantum Algorithms

For constant $\alpha > 1$ : The authors present an efficient quantum algorithm to estimate $T_\alpha(\rho_0, \rho_1)$ $T_{α} (ρ_{0}, ρ_{1})$ with additive error $\epsilon$ $ϵ$ using $O(1)$ queries (rank-independent). The time complexity is $\text{poly}(n)$ $poly (n)$ if the state-preparation circuits are of polynomial size.
- This represents an exponential speedup over the previous best result [WGL+24], which had query complexity $\tilde{O}(r^{3+1/\{\alpha/2\}}/\epsilon^{4\alpha+\dots})$ dependent on the rank $r$ .
- Sample complexity is also improved to $\tilde{O}(1/\epsilon^{3\alpha+2+\dots})$ (rank-independent).
For constant $0 < \alpha < 1$ : An efficient algorithm estimates $\Lambda_\alpha(\rho_0, \rho_1)$ with query complexity $\tilde{O}(r^{2/(\alpha-1)}/\epsilon^{2/\alpha})$ . This improves the previous best bound of $\tilde{O}(r^{5/\alpha}/\epsilon^{5/\alpha+1})$ but remains dependent on the rank $r$ .

2. Computational Complexity Dichotomy

The paper establishes a sharp phase transition in the complexity of QSD $_\alpha$ :

Case $\alpha > 1$ (Fixed Constant): QSD $_\alpha$ is BQP-complete. The problem is efficiently solvable on a quantum computer, and the estimator is rank-independent.
Case $1 \leq \alpha(n) \leq 1 + \text{negl}(n)$ : QSD $_\alpha$ is QSZK-complete. No efficient quantum estimator exists unless BQP = QSZK.
Case $0 < \alpha < 1$ (Fixed Constant): PoweredQSD $_\alpha$ is QSZK-hard.

3. New Inequalities

The authors provide new rank-dependent inequalities connecting the trace distance to Schatten norms and power distances. These inequalities are of independent interest and are crucial for the hardness reductions, particularly showing how the "easy" regime (pure states) transitions to the "hard" regime (mixed states with high rank) as $\alpha$ approaches 1.

Significance

The paper resolves Problem 1 posed in the introduction regarding the computational complexity of closeness testing with respect to general Schatten $\alpha$ -norms.

It demonstrates that the dichotomy between QSZK-hardness (for $\ell_1$ -like measures) and BQP-containment (for $\ell_2$ -like measures) is not merely a distinction between even and odd integers, but a sharp transition occurring between $\alpha=1$ and any constant $\alpha > 1$ .
The development of rank-independent estimators for $\alpha > 1$ is a significant technical advancement, removing a major bottleneck in quantum state property testing that previously required knowledge of or dependence on the state rank.
The results clarify the landscape of quantum state distinguishability, showing that while $T_\alpha$ for $\alpha > 1$ provides a natural lower bound on the trace distance, it becomes efficiently computable for any fixed $\alpha > 1$ , unlike the trace distance itself.

The authors note that the case $\alpha = \infty$ remains an open problem, with the associated promise problem QSD $_\infty$ being BQP-hard and contained in QMA, but its containment in BQP is currently unknown. Additionally, they leave open the question of whether the quantitative bounds in Table 1 can be tightened further.