⚛️ quantum physics

On estimating operator norm distance, with optimal trace distance estimation when one state is pure

This paper presents efficient, rank-independent quantum estimators for the operator norm distance between quantum states, achieving optimal $\Theta(1/\epsilon)$ query complexity when one state is pure and $\widetilde{O}(1/\epsilon^{3/2})$ for general states, thereby establishing the problem's BQP-completeness and significantly improving upon prior bounds that scaled with state rank.

Original authors: Yupan Liu, Qisheng Wang, Zhan Yu

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yupan Liu, Qisheng Wang, Zhan Yu

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, each containing a quantum state (a complex, invisible configuration of information). You want to know: How different are these two boxes?

In the quantum world, there are many ways to measure "difference." The most famous one is like measuring the total amount of ink spilled if you pour both boxes into a tray; this is called Trace Distance. But this paper focuses on a different, more extreme measure called Operator Norm Distance.

Think of Operator Norm Distance not as the total difference, but as the single biggest spike of difference between the two boxes. If one box has a tiny, massive spike of energy that the other doesn't, that spike defines the distance, even if the rest of the boxes are almost identical.

The authors of this paper asked a tough question: How hard is it to find this "biggest spike" using a quantum computer?

Here is the breakdown of their discovery, using simple analogies:

1. The "Pure" State Shortcut (The Easy Case)

Usually, quantum states are messy mixtures (like a smoothie with many ingredients). But sometimes, a state is "pure" (like a single, perfect apple).

The paper discovered a magical shortcut when one of the two boxes contains a "pure" state (the perfect apple).

The Old Way: Previous methods were like trying to find that biggest spike by looking at every single grain of sand in the mixture. If the mixture was huge (high "rank"), this took forever, scaling up with the size of the problem.
The New Way: The authors found that if you have a pure state, it acts like a flashlight. Because the pure state is so "focused," it naturally shines a light right on the biggest spike of difference. You don't need to scan the whole room; the flashlight points you straight to the answer.
The Result: They built an algorithm that finds this distance incredibly fast. The time it takes doesn't care how messy the other box is. It only depends on how precise you want to be. If you want a rough answer, it's instant. If you want a super-precise answer, it takes a little longer, but it's still efficient.

Analogy: Imagine trying to find the tallest person in a crowd.

Old method: You measure everyone's height. If the crowd is huge, this takes forever.
New method (Pure State): You have a friend (the pure state) who is standing right next to the tallest person and holding a sign that says "I'm next to the tallest." You just look at your friend and measure the distance to the sign. It's instant, regardless of how big the crowd is.

2. The General Case (The Harder Case)

What if neither box has a pure state? Both are messy mixtures (smoothies).

The Challenge: The "flashlight" trick doesn't work perfectly here. The biggest spike might be hidden deep inside the mixture, and your starting point might not be close to it.
The Solution: The authors used a technique called Amplitude Amplification. Imagine you are looking for a needle in a haystack, but you have a slightly better-than-random guess of where it might be. You use a quantum trick to "boost" your chances of finding it, repeating the process just enough to guarantee success.
The Result: They created an algorithm that works for any two states. It is slower than the "pure state" shortcut (it takes a bit more time as you demand higher precision), but it is still vastly faster than the old methods that required checking every single dimension of the system.

3. Why This Matters (The "Rank" Problem)

In quantum computing, the "size" of a problem is often defined by its rank (how complex the mixture is).

The Old Problem: Previous methods got slower and slower as the rank got higher. For very complex quantum states, the rank could be so huge that the calculation would take longer than the age of the universe.
The Breakthrough: This paper proves that you do not need to pay the price of the rank. Whether the state is simple or astronomically complex, their algorithm runs in a time that depends only on the precision you want, not the complexity of the state.

Summary of the "Magic"

The core intuition behind their success is a structural feature of the math:

When one state is pure, it is mathematically guaranteed to have a strong connection to the "biggest spike" of difference.
The authors realized they could use this connection as a "warm start" (a head start) for their quantum computer, skipping the need to search the entire space.

In a nutshell:
The paper provides a new, super-fast way for quantum computers to measure the "biggest difference" between two quantum states. If one state is simple (pure), the method is optimal and ignores the complexity of the other. If both are complex, the method is still efficient and avoids the exponential slowdown that plagued previous approaches. They turned a problem that seemed to require checking every grain of sand into one where you just need to follow a few smart clues.

Technical Summary: Estimating Operator Norm Distance with Optimal Trace Distance Estimation

Problem Statement

The paper investigates the computational complexity of estimating the operator norm distance $T_\infty(\rho_0, \rho_1)$ between two $n$ -qubit quantum states $\rho_0$ and $\rho_1$ . The distance is defined as $T_\infty(\rho_0, \rho_1) := \frac{1}{2}\|\rho_0 - \rho_1\|_\infty$ , where $\|\cdot\|_\infty$ denotes the operator norm (the largest singular value).

The states are provided via state-preparation circuits $Q_0$ and $Q_1$ of polynomial size. The goal is to design quantum algorithms that estimate this distance to within an additive error $\epsilon$ with query complexity that is independent of the rank (and thus the dimension $d=2^n$ ) of the states. This addresses an open problem regarding whether rank-independent bounds exist for the operator norm distance, analogous to classical results for $\ell_\alpha$ distances with $\alpha > 1$ .

Methodology

The authors employ a framework combining unitary dilation, qubitization, and maximum phase estimation. The core strategy involves mapping the eigenvalues of the Hermitian operator $\Delta = (\rho_0 - \rho_1)/2$ to the eigenphases of a unitary operator, allowing for efficient estimation via quantum phase estimation techniques.

1. Unitary Dilation and Qubitization

Given state-preparation circuits for $\rho_0$ and $\rho_1$ , the authors construct a unitary dilation $U_\Delta$ of $\Delta$ using the Linear Combination of Unitaries (LCU) technique and purified density matrix methods.

They define a qubitization unitary $W = U R U^\dagger R$ , where $R$ is a reflection operator.
This construction creates a monotone correspondence between the eigenvalues $\lambda$ of $\Delta$ and the eigenphases $\theta$ of $W$ , specifically $\theta = 2 \arccos(\lambda)$ (up to global phases).
The problem of estimating $\|\Delta\|_\infty$ (the largest eigenvalue magnitude) is reduced to estimating the maximum eigenphase of $W$ .

2. The "Warm Start" Strategy

A critical challenge in phase estimation is ensuring the input state has a non-negligible overlap with the target eigenspace (the top eigenspace of $\Delta$ ). The paper distinguishes two cases based on the purity of the input states:

Case 1: One State is Pure (Warm Start Lemma)
When one state (say $\rho_0 = |\psi\rangle\langle\psi|$ ) is pure, the authors prove a structural lemma (Lemma 3.1). They show that the pure state $|\psi\rangle$ itself has a squared overlap of at least $1/2$ with the unique eigenvector corresponding to the largest positive eigenvalue of $\Delta$ .
- Intuition: Since $\rho$ is positive semidefinite, the restriction of $\Delta$ to the subspace orthogonal to $|\psi\rangle$ is negative semidefinite. Thus, any positive eigenvalue must correspond to an eigenvector with substantial overlap with $|\psi\rangle$ .
- This "warm start" allows the use of Maximum Phase Estimation with a constant overlap parameter $\gamma = 1/2$ .
Case 2: General Mixed States (Eigenvalue-Scaled Overlap)
When both states are mixed, a constant overlap is not guaranteed. The authors derive a weaker bound (Lemma 4.1) showing that the overlap between the purification of the input state and the top eigenspace scales with the target eigenvalue: $\|\Pi_{\max} |\psi_0\rangle\|^2 \ge 2\lambda_{\max}(\Delta)$ .
- Since the target distance is $\epsilon$ , the overlap is roughly $O(\epsilon)$ .
- To compensate, the algorithm employs amplitude amplification (implicitly via the parameters of the maximum phase estimation routine), boosting the success probability to a constant.

Key Contributions and Results

1. Optimal Estimation for One Pure State

Theorem 1.1: When one state is pure, the quantum query complexity for estimating $T_\infty(\rho, |\psi\rangle\langle\psi|)$ or the trace distance $T(\rho, |\psi\rangle\langle\psi|)$ to within additive error $\epsilon$ is $\Theta(1/\epsilon)$ .

Significance: This matches the optimal bound for the pure-vs-pure case. Crucially, the complexity is rank-independent. Previous approaches (e.g., van Apeldoorn et al., Wang and Zhang) had query complexities scaling linearly with the rank $r$ (potentially $O(2^n)$ ), whereas this method runs in $\text{poly}(n)$ time for constant $\epsilon$ .
Sample Complexity: Via sample-to-query lifting, the sample complexity is $\Theta(1/\epsilon^2)$ .

2. Efficient Estimation for General States

Theorem 1.2: For general quantum states $\rho_0, \rho_1$ , there exists a quantum algorithm estimating $T_\infty(\rho_0, \rho_1)$ with query complexity $\tilde{O}(1/\epsilon^{3/2})$ .

Significance: This improves upon the previous best upper bounds for $\ell_\alpha$ distances with $\alpha > 1$ (which were generally $O(1/\epsilon^{\alpha+1})$ or worse). It leaves only a square-root gap to the known lower bound of $\Omega(1/\epsilon)$ .
Sample Complexity: The sample complexity is $\tilde{O}(1/\epsilon^3)$ .

3. Complexity Class Results

The paper establishes the computational complexity of the promise problem QSD $_\infty$ (testing if $T_\infty \ge 2/5$ or $\le 1/5$ ):

Corollary 1.3: QSD $_\infty$ is BQP-complete.
Corollary 1.4: The restricted variant OnePureQSD $_\alpha$ (at least one state pure) is BQP-complete for all $\alpha \in [1, \infty]$ .
These results improve upon prior QMA upper bounds and confirm that estimating operator norm distance is efficiently solvable on a quantum computer without requiring a quantum witness.

Significance and Claims

The paper claims to resolve a long-standing open problem regarding the rank-independence of estimating operator norm distance.

Structural Insight: The authors highlight a specific structural feature of the operator norm distance: when one state is pure, the pure state serves as a "warm start" for the top eigenspace of the difference operator. This is a rank-one perturbation phenomenon that does not hold for general mixed states.
Efficiency: The proposed estimators achieve exponential speedups over state-tomography-based approaches (which scale with dimension $d=2^n$ ) and polynomial speedups over previous rank-dependent estimators.
Hierarchy Context: The results suggest that the operator norm distance ( $\alpha = \infty$ ), often viewed as the most relaxed notion of closeness, is actually the "easiest" case in the quantum $\ell_\alpha$ hierarchy in terms of query complexity, being easier than intermediate cases like $\alpha=2$ or $\alpha=3$ .

The paper concludes by noting that a square-root gap remains between the upper bound ( $\tilde{O}(1/\epsilon^{3/2})$ ) and the lower bound ( $\Omega(1/\epsilon)$ ) for the general mixed-state case, posing the optimality of this bound as an open problem.