The Optimal Rate Function in Covariant Quantum State Tomography

This paper proves Keyl's conjecture that a specific Schur sampling-based covariant quantum state tomography protocol achieves the optimal rate function, which is an annealed version of quantum relative entropy bounded by the standard quantum relative entropy due to the cost of learning the eigenbasis.

The Gist

Imagine you are a detective trying to identify a mysterious, invisible object. You have a stack of $n$ identical copies of this object in front of you. Your goal is to figure out exactly what the object is (its "quantum state") by performing tests on these copies.

In the world of quantum physics, this is called Quantum State Tomography. The problem is that you can't just look at the object; you have to measure it, and measuring quantum objects is tricky. Every time you measure, you get a result, but it's probabilistic. If you have only a few copies, your guess might be wrong. If you have infinite copies, you can be perfect. But in the real world, you only have a finite number.

This paper asks a simple but deep question: Is there a "best possible" way to guess the object's identity that works for any object, without us knowing anything about it beforehand?

Here is the breakdown of their discovery, using some everyday analogies.

1. The "Rate Function": How Fast Do You Learn?

The authors introduce a concept called the Rate Function. Think of this as a "speedometer for error."

• Imagine you are guessing the object. Sometimes you guess it's a "Red Ball" when it's actually a "Blue Ball."
• The Rate Function tells you how unlikely that mistake is as you get more copies ($n$) of the object.
• If the Rate Function is high, the probability of making that specific mistake drops to zero incredibly fast (exponentially fast).
• If the Rate Function is low, you might keep making that mistake even with lots of data.

The goal of a good detective (a good tomography protocol) is to have a high Rate Function for all wrong guesses. This means you want to be extremely confident that you are not making a mistake.

2. The Two Types of Detectives: "Covariant" vs. "Cheating"

The paper distinguishes between two types of strategies:

The "Cheating" Strategy (Non-Covariant):
Imagine you have a specific suspect in mind (a specific quantum state $\sigma$) and you want to prove it's not that suspect. You can design a test specifically tailored to catch that one specific lie.

• The Result: The authors show that if you tailor your test to a specific pair of "True Object" and "Wrong Guess," you can achieve the absolute theoretical limit of speed. This limit is called the Quantum Relative Entropy. It's the "Gold Standard" of how fast you can learn.
• The Catch: This strategy only works for that one specific pair. If you change the object or the wrong guess, your test fails. It's like having a key that opens only one specific door.

The "Honest" Strategy (Covariant):
In the real world, you don't know the object beforehand. You need a strategy that works no matter what the object is, and no matter how you rotate or re-orient your view of it. This is called a Covariant Protocol.

• Think of this as a universal key that must work on any door, regardless of how the door is painted or where it's located.
• Because you have to be "blind" to the specific orientation of the object, you pay a "tax" on your learning speed. You can't be as fast as the "cheating" strategy.

3. The Main Discovery: Keyl's Algorithm is the Best "Honest" Detective

For years, a physicist named Keyl proposed a specific method (using a mathematical tool called Schur sampling) to guess the quantum state. He guessed that this method was the absolute best possible "Honest" strategy.

This paper proves Keyl was right.

They showed that among all strategies that don't cheat (covariant protocols), Keyl's method has the highest possible Rate Function. It is the fastest you can possibly learn without prior knowledge.

4. The "Annealed" vs. "Quenched" Analogy

Why is the "Honest" strategy slower than the "Cheating" one? The authors use a beautiful analogy from statistical physics to explain the difference.

• The "Cheating" Speed (Relative Entropy): Imagine you are trying to find the average temperature of a room. You have a thermometer that is already perfectly calibrated to the room's layout. You just read the numbers. This is a "Quenched" average. The environment is fixed, and you just measure it.
• The "Honest" Speed (Keyl's Rate): Now imagine you are trying to find the temperature, but you also have to build the thermometer while you are measuring. You have to figure out where the hot spots are (the eigenbasis) at the same time you are measuring the heat (the spectrum).
  • This is an "Annealed" average. The system you are measuring and the tool you are using to measure it are evolving together.
  • Because you have to spend time and resources figuring out how to measure (learning the "eigenbasis") while you are actually measuring, you learn slightly slower.

The paper shows that Keyl's formula is exactly this "Annealed" version. It accounts for the extra cost of learning the orientation of the quantum state while you are trying to identify it.

Summary

• The Problem: How do we best guess a quantum state from limited data?
• The Limit: There is a theoretical speed limit (Relative Entropy) if you tailor your guess to a specific scenario.
• The Reality: If you need a strategy that works for any unknown state (Covariant), you hit a slightly lower speed limit.
• The Solution: Keyl's algorithm hits this lower limit perfectly. It is the optimal way to guess a quantum state when you have no prior information.
• The Cost: The reason it's slower than the theoretical maximum is that you have to "learn the map" (the eigenbasis) at the same time you are "exploring the territory" (the state), which adds a small but unavoidable delay.

In short: If you want to be the best possible detective without knowing the suspect's face in advance, Keyl's method is the best tool you can use.

Technical Summary

Technical Summary: The Optimal Rate Function in Covariant Quantum State Tomography

Problem Statement
The paper addresses the fundamental problem of quantum state tomography: estimating an unknown quantum state $\rho$ given $n$ copies of the state, $\rho^{\otimes n}$. While the asymptotic limit $n \to \infty$ allows for perfect determination, the paper focuses on the finite-$n$ regime and the asymptotic behavior of estimation errors. Specifically, the authors seek to characterize the "best possible" estimation scheme by analyzing the exponential rate at which the probability of making a large error decays.

This is formalized through the rate function $I(\sigma \| \rho)$, defined as:
$$I(\sigma \| \rho) \equiv -\lim_{n \to \infty} \frac{1}{n} \log P_n(\sigma | \rho)$$
where $P_n(\sigma | \rho)$ is the probability that a tomography protocol outputs an estimate $\sigma$ given the true state $\rho$. A larger rate function implies that the error of mistaking $\rho$ for $\sigma$ becomes exponentially less likely as $n$ increases.

The central question is whether there exists a universal protocol that maximizes this rate function for all pairs of states $(\sigma, \rho)$ without prior knowledge of $\rho$. The authors distinguish between general protocols and covariant protocols, which are basis-independent and transform equivariantly under unitary rotations ($M^{(n)}_{U\sigma U^\dagger} = U^{\otimes n} M^{(n)}_\sigma (U^\dagger)^{\otimes n}$).

Methodology and Framework
The authors employ tools from representation theory, specifically Schur-Weyl duality, and the theory of Large Deviation Principles (LDP).

1. Representation-Theoretic Characterization:
   The paper utilizes the decomposition of the $n$-copy Hilbert space $(\mathbb{C}^d)^{\otimes n}$ into irreducible representations of the symmetric group $S_n$ and the unitary group $U(d)$. Any covariant protocol can be characterized by a Positive Operator-Valued Measure (POVM) in the Schur basis. The measurement outcomes are indexed by Young diagrams $\lambda$ (representing the spectrum) and unitaries $U$ (representing the eigenbasis).

2. Rate Function Analysis:
   The authors analyze the asymptotic probability of obtaining an estimate $\sigma$ by examining the behavior of the POVM elements acting on $\rho^{\otimes n}$. They utilize properties of Schur polynomials, weight spaces of $GL(d)$ representations, and concentration of Young diagrams to bound the probability of error.

3. Two-Part Proof Strategy:

   • Achievability (Non-Covariant): To establish the upper bound of the quantum relative entropy $D(\sigma \| \rho)$, the authors construct a non-covariant protocol. This protocol splits samples into two parts: a small fraction used for a consistent baseline tomography, and the remainder used for a "Stein test" tailored specifically to the pair $(\sigma, \rho)$. This demonstrates that pointwise, the relative entropy is achievable.
   • Optimality (Covariant): To prove the optimality of Keyl's protocol within the covariant class, the authors decompose the general covariant POVM into blocks indexed by Young diagrams. They show that consistency forces the protocol to concentrate on specific "typical" Young diagrams. By analyzing the weight spaces within these blocks and applying a principal-minor lower bound, they derive an upper bound on the rate function for any consistent covariant protocol.

Key Contributions and Results

1. Pointwise Optimality of Relative Entropy (Theorem 1.1):
   The authors prove that for any specific pair of states $(\sigma, \rho)$, the quantum relative entropy $D(\sigma \| \rho)$ is the sharp upper bound for the rate function among all consistent tomography protocols.
   $$\sup_{I \in \mathcal{E}} I(\sigma \| \rho) = D(\sigma \| \rho)$$
   However, the protocol achieving this bound depends on the specific pair $(\sigma, \rho)$ and is generally non-covariant.

2. Optimality of Keyl's Protocol (Theorem 1.2):
   The paper proves Keyl's conjecture: among all covariant tomography protocols (which assume no prior information about the basis), the protocol proposed by Keyl [Key06] is optimal.
   For any consistent covariant protocol satisfying an LDP with rate function $I(\sigma \| \rho)$, the following inequality holds:
   $$I(\sigma \| \rho) \leq S_{\text{Keyl}}(\sigma \| \rho)$$
   where $S_{\text{Keyl}}$ is Keyl's rate function.

3. Characterization of Keyl's Rate Function:
   The rate function $S_{\text{Keyl}}(\sigma \| \rho)$ is explicitly given by:
   $$S_{\text{Keyl}}(\sigma \| \rho) = -H(x) - \sum_{k=1}^d (x_k - x_{k+1}) \log \Delta_k(U^\dagger \rho U)$$
   where $x$ is the spectrum of $\sigma$ (ordered decreasingly), $H(x)$ is the Shannon entropy, and $\Delta_k$ is the determinant of the leading $k \times k$ principal minor.

   • The authors show that $S_{\text{Keyl}}(\sigma \| \rho) \leq D(\sigma \| \rho)$, with equality if and only if $\sigma$ and $\rho$ commute.
   • The difference between the two is interpreted physically: $D(\sigma \| \rho)$ corresponds to a "quenched" average (knowing the eigenbasis), while $S_{\text{Keyl}}$ corresponds to an "annealed" average, reflecting the additional cost of learning the eigenbasis simultaneously with the spectrum in a covariant setting.

4. Connection to Hypothesis Testing:
   The paper identifies $S_{\text{Keyl}}$ with the reverse quantum relative entropy $D_R(\sigma \| \rho)$, which appears in composite quantum hypothesis testing and "right-pinched" relative entropy scenarios.

Significance and Claims
The paper claims to resolve the question of optimal state estimation within the class of covariant protocols. It establishes that the "cost" of basis independence in quantum tomography is precisely quantified by the gap between the standard quantum relative entropy and Keyl's rate function.

• Theoretical Resolution: The work confirms that Keyl's algorithm, which uses Schur sampling to estimate the spectrum followed by a covariant measurement for the eigenbasis, is the optimal strategy for covariant tomography in the large-deviation limit.
• Physical Interpretation: The results provide a rigorous statistical mechanics analogy, distinguishing between the "quenched" cost of estimation when the basis is known versus the "annealed" cost when the basis must be learned concurrently with the spectrum.
• Limitations and Open Questions: The authors modestly note that their optimality result is restricted to covariant protocols. They leave open whether a regularity condition (lower semicontinuity) alone, without assuming covariance, is sufficient to enforce the $S_{\text{Keyl}}$ bound. Furthermore, they highlight the need to clarify the relationship between these large-deviation rates and finite-sample complexity bounds (sample complexity) for mixed-state tomography.

In summary, the paper provides a definitive characterization of the asymptotic error landscape for covariant quantum state tomography, proving that Keyl's protocol achieves the best possible exponential decay of error rates under the constraint of basis independence.