⚛️ quantum physics

The Sample Complexity of Fidelity Estimation to a Known Rank- $r$ Reference State Is $\widetilde{\Theta}(r^2/\varepsilon^2)$

This paper resolves the open problem of the sample complexity for estimating fidelity between an unknown quantum state and a known rank- $r$ reference state by proving it is $\widetilde{\Theta}(r^2/\varepsilon^2)$ , thereby closing the gap between previous lower and upper bounds through novel techniques involving spectral moment matching and random permutation analysis.

Original authors: Gye Jin Lee, Sunghyeon Jo

Published 2026-08-04

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Gye Jin Lee, Sunghyeon Jo

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 Quantum Detective's Dilemma

Imagine you are a detective trying to solve a mystery, but instead of a crime scene, you are looking at a tiny, invisible particle of light or matter called a "quantum state." In the quantum world, things are fuzzy and strange; you can't just peek at a particle to see exactly what it is without changing it. So, to figure out what a particle is doing, you have to make many copies of it and run tests on them. This is called "sample complexity"—it's basically asking, "How many copies do I need to look at before I can be sure of the answer?"

One of the most important things a quantum detective wants to know is how close two quantum states are to each other. This closeness is measured by something called "fidelity." Think of fidelity like a similarity score between two fingerprints. If you have a perfect reference fingerprint (a known state) and a mysterious one you found at the scene (an unknown state), fidelity tells you how much they match. Usually, if the reference fingerprint is simple (like a basic pattern with only a few lines), you'd think it would be easy to compare. But in the quantum world, even simple-looking patterns can be tricky because of a rule called "non-commutativity." This is like trying to measure the color of a ball and its temperature at the exact same time; the order in which you check them matters, and sometimes checking one messes up the other.

For a long time, scientists were arguing about how many copies of a quantum state you actually need to get a good similarity score when the reference state is simple (specifically, when it has a "rank" of $r$ , which is a fancy way of saying it has $r$ distinct features). Some thought you needed a number of copies that grew linearly with $r$ (like $r$ ), while others thought it might need to grow much faster, like $r$ squared ( $r^2$ ). This paper steps in to settle that argument.

The Paper's Big Discovery

This paper, written by Gye Jin Lee and Sunghyeon Jo, finally answers the question: How many copies do you need to estimate how close an unknown quantum state is to a known, simple one?

The authors prove that the answer is surprisingly high. They show that the number of copies you need grows roughly with the square of the rank ( $r^2$ ), divided by the square of how precise you want to be ( $\epsilon^2$ ). In their own words, the sample complexity is $\tilde{\Theta}(r^2/\epsilon^2)$ .

To put this in perspective, imagine you are trying to guess the flavor of a secret ice cream by tasting it. If the secret ice cream is made of just one flavor (rank 1), you might only need a few tastes. But if the secret ice cream is a complex swirl of $r$ different flavors, this paper proves that you don't just need $r$ tastes; you actually need something closer to $r \times r$ tastes to be confident you've got the recipe right. This closes a gap that had been open for a while, where previous research had only managed to prove you needed at least $r$ copies and at most $r^2$ copies. The authors show that the $r^2$ limit is the real deal.

How They Solved the Puzzle

To prove this, the authors didn't just run a simple experiment; they built a mathematical "trap" to show that any method trying to do it with fewer copies would fail.

The Twin Spectra: First, they created two different "spectra" (which are like lists of ingredients for the quantum states) that look almost identical if you check their basic properties (like their average weight or total volume) but are actually very different in their details. They used a clever mathematical trick involving "size-biased" random matrices—think of it as a way of weighting the ingredients so that the most common ones cancel out, leaving only the subtle differences hidden in the noise.
The Indistinguishability Trap: They showed that if you try to tell these two different states apart using fewer than $r^2$ copies, the results you get are so similar that even the smartest quantum detective couldn't tell them apart. The states are "indistinguishable" within the limits of the math.
The Non-Commuting Twist: A key part of their proof is that this difficulty isn't just because the states are simple; it happens even when the unknown state and the known reference state are "non-commuting." This means they are fundamentally incompatible, like trying to measure a spinning top's speed and its direction simultaneously. The authors proved that this incompatibility makes the job even harder, requiring that quadratic ( $r^2$ ) number of copies.

What This Means for Quantum Spectrum Estimation

The paper also uses this same logic to solve a related problem: estimating the "spectrum" of a quantum state (essentially, figuring out the exact list of ingredients). They prove that even if you just want to know the general shape of the list with constant accuracy, you still need about $r^2$ copies. This establishes a "near-quadratic barrier," meaning that no matter how clever your algorithm is, you can't beat this $r^2$ requirement without changing the rules of the game.

The Bottom Line

The authors have mathematically proven that estimating the similarity between a known, simple quantum state and an unknown one is inherently difficult. You cannot bypass the system by using fewer copies; the complexity is fundamentally tied to the square of the state's rank. While their proof leaves a tiny bit of wiggle room for logarithmic factors (tiny adjustments related to the size of the numbers), the main takeaway is clear: to get a good read on a quantum state, you need to look at it a lot more times than you might expect—specifically, a number of times proportional to the square of its complexity.

This result settles a debate in the field and sets a clear limit for future quantum technologies. If engineers want to build better quantum sensors or computers, they now know exactly how much data they need to collect to be sure of their measurements, and that amount is significantly larger than previously hoped.

Technical Summary: The Sample Complexity of Fidelity Estimation to a Known Rank-r Reference State

Problem Statement
The paper addresses the fundamental question of determining the sample complexity, denoted $S(r, \varepsilon)$ , for estimating the root Uhlmann fidelity $F(\rho, \sigma) = \text{tr}\sqrt{\sqrt{\sigma}\rho\sqrt{\sigma}}$ between an unknown quantum state $\rho$ and a known reference state $\sigma$ of rank $r$ . While previous work established a lower bound of $\Omega(r/\varepsilon^2)$ and an upper bound of $O(r^2/\varepsilon^2)$ , a gap of a factor $r$ remained unresolved. The authors investigate whether the sample complexity is inherently quadratic in the rank $r$ (up to logarithmic factors) or if the linear lower bound is tight.

Methodology
The proof employs a "two-prior method" to establish a lower bound. The authors construct two distinct priors over quantum states, $\Pi_0$ and $\Pi_1$ , such that:

The fidelity values to the reference state $\sigma$ are separated by a constant gap (i.e., $F(\rho, \sigma) \le L$ for $\rho \sim \Pi_0$ and $F(\rho, \sigma) \ge H$ for $\rho \sim \Pi_1$ , with $H - L > 2\varepsilon$ ).
The $n$ -copy average states corresponding to these priors are indistinguishable in trace distance (specifically, $d_{\text{tr}}(\mathbb{E}_{\Pi_0}[\rho^{\otimes n}], \mathbb{E}_{\Pi_1}[\rho^{\otimes n}]) = o(1)$ ) for $n$ up to the claimed lower bound.

The construction relies on three main technical components:

Exact Spectral Moment Matching: The authors construct two probability distributions (spectra) $a^{(0)}$ and $a^{(1)}$ on $r$ dimensions that share identical moments up to order $K \approx \Theta(\log r / \log \log r)$ . One distribution is sparse (support on $\alpha r$ elements), while the other is "well-conditioned" (mass distributed over $\beta r$ elements). This is achieved via a barycentric cancellation technique followed by a quantitative packet correction to ensure equal weights.
Size-Biased Doubly Correlated Wishart Model: The authors define a prior over matrices $G$ using a doubly correlated Wishart model ( $G = U D^{1/2} Z D^{1/2} V^*$ ). They introduce a radial size bias proportional to $\|G\|_F^{2m}$ . This bias cancels the normalization factor in the $m$ -copy average state, allowing the Schur-label distribution of the resulting state to be proportional to $s_\lambda(a)^2$ , where $s_\lambda$ is the Schur polynomial.
Cauchy Identity and Long-Cycle Estimates: Using the Cauchy identity and Frobenius formula, the authors relate the Hellinger affinity of the two priors to a weighted random permutation model. The matching of low-order moments ensures that contributions from short cycles in the permutation cancel out. The indistinguishability of the states is then reduced to bounding the probability of "long cycles" in this permutation model, which is shown to be negligible when the number of copies $m$ is below the quadratic threshold.

To extend the result from commuting states to the general non-commuting case, the authors utilize a direct-sum embedding. They embed the base states into a larger system $T \oplus B$ and introduce a known reference state $\sigma = \frac{1}{r} P_T$ . By constructing states $\omega_{G,q}$ that are non-commuting with $\sigma$ but maintain the fidelity gap, they ensure the lower bound holds without commutativity assumptions. Finally, binomial thinning is used to scale the number of copies from the base indistinguishability regime to the desired $1/\varepsilon^2$ dependence.

Key Contributions and Results

Resolution of the Fidelity Estimation Gap: The paper proves that for a known rank- $r$ reference state, the sample complexity is $S(r, \varepsilon) = \tilde{\Theta}(r^2/\varepsilon^2)$ . Specifically, they establish a lower bound of $\Omega\left(\frac{r^2}{\varepsilon^2 (\log r)^C}\right)$ , closing the factor- $r$ gap left by Wang's prior work. This holds even for a fixed reference state $\sigma = \frac{1}{r} P_T$ on a $2r$ -dimensional system and for hard families of states that do not commute with $\sigma$ .
Near-Quadratic Barrier for Spectrum Estimation: Applying the same framework, the authors derive a near-quadratic lower bound of $\tilde{\Omega}(r^2)$ for estimating the quantum spectrum (or the normalized square-root trace $\text{Tr}(\rho) = \frac{1}{\sqrt{r}}\text{tr}\sqrt{\rho}$ ) at constant accuracy. This result matches the recent upper bound of $O(r^2 (\frac{\log \log r}{\log r})^2)$ by Pelecanos–Spilecki–Tang–Wright up to polylogarithmic factors, effectively determining the polynomial order of the sample complexity for this regime.
Two-Sided Rank Testing: The techniques yield a lower bound for distinguishing between states of rank $\le \alpha r$ and states with a large distance to the set of rank- $\alpha r$ states, requiring $\tilde{\Omega}(r^2)$ copies.

Significance
The paper claims to settle the open problem regarding the dependence of fidelity estimation sample complexity on the rank of the reference state. By demonstrating that the complexity is inherently quadratic in $r$ (up to logarithmic factors), it establishes a "near-quadratic barrier" for both fidelity estimation and spectrum estimation. The work introduces novel tools, specifically the combination of exact moment matching with size-biased Schur measures and long-cycle estimates in weighted permutation models, which may have applications in analyzing other non-polynomial spectral functionals. The results hold under unrestricted collective measurements, confirming that the quadratic scaling is a fundamental limitation of the problem rather than an artifact of restricted measurement strategies.

The Quantum Detective's Dilemma

The Paper's Big Discovery

How They Solved the Puzzle

What This Means for Quantum Spectrum Estimation

The Bottom Line

More like this