Exact distinguishability between real-valued and complex-valued Haar random quantum states

This paper analytically computes the spectral decomposition of the density matrix for $t$ copies of Haar random states on the orthogonal group to derive the exact trace distance between real and complex ensembles, thereby establishing a lower bound for real-valued state $t$-designs and improving the requirements for imaginarity testing.

The Gist

Imagine you are trying to bake the perfect, most random cake possible. In the world of quantum computing, this "perfect cake" is called a Haar random state. It represents the ultimate level of randomness, where every possible flavor (or quantum configuration) is equally likely. Scientists use these random states as a gold standard for testing computers, securing data, and understanding how the universe works.

However, baking a truly perfect random cake is incredibly hard and requires a massive, exponential amount of effort (like needing a kitchen the size of a galaxy). So, instead, scientists try to bake "good enough" approximations. They create ensembles of states that look random but are easier to make. These are called state t-designs.

The big question this paper tackles is: What happens if we try to bake these cakes using only "real" ingredients, without any "complex" ones?

In quantum mechanics, numbers come in two flavors: Real (like 1, 2, 3) and Complex (which include the imaginary number i, like 1 + 2i). Most quantum phenomena require Complex numbers to be described accurately. But some researchers have been trying to build quantum systems using only Real numbers to see if they can get away with it.

Here is what the authors discovered, broken down into simple concepts:

1. The "Real" vs. "Complex" Taste Test

The authors asked: If you give someone a sample of a "Real" random cake and a sample of a "Complex" random cake, can they tell the difference?

They found that yes, you can tell the difference, and they calculated exactly how easy it is to spot the fake.

• The Analogy: Imagine the "Complex" cake is a smooth, perfectly blended smoothie. The "Real" cake is a smoothie where the blender missed a few spots, leaving tiny, detectable chunks.
• The Result: The authors developed a mathematical recipe (a spectral decomposition) to count exactly how many "chunks" (differences) exist. They found that if you have enough copies of the cake (quantum states), you can distinguish the Real version from the Complex version with high certainty.

2. The Fundamental Limit (The "Ceiling")

The paper proves a hard limit on how good a "Real" approximation can ever be.

• The Analogy: Imagine you are trying to mimic a complex, swirling dance (the Complex state) using only moves that go strictly forward and backward (the Real state). No matter how hard you try, you can never perfectly mimic the swirls. There is a fundamental "wobble" that you cannot eliminate.
• The Claim: The authors show that any attempt to create a random-looking state using only Real numbers will always have a specific, unavoidable error rate. You cannot make a "Real" state design that is as perfect as a "Complex" one. There is a "ceiling" on their performance.

3. The "Imaginarity" Test

The paper also looks at a specific test called Imaginarity Testing. This is like a lie detector test for quantum states to see if they are "Real" or "Complex."

• The Discovery: To pass this test and prove a state is truly complex (and not just a clever Real imitation), you need a certain number of samples.
• The Improvement: Previous research suggested you needed a certain amount of samples (roughly the square root of the system size). The authors refined this math and showed you actually need 1.41 times more samples (the square root of 2) than previously thought to be absolutely sure.
• Why it matters: This means that if you are trying to trick a system into thinking a Real state is Complex, you need more copies of the state to pull off the deception than we thought. Conversely, if you are trying to detect the difference, you need more samples to be certain.

4. The "Magic" of Math

How did they figure this out? They used a clever mathematical trick.

• The Analogy: They realized that the messy quantum states could be translated into polynomials (mathematical expressions with variables like $x^2 + y$).
• The Breakthrough: They mapped the quantum states onto a special type of polynomial called "Harmonic Polynomials." By studying the "shape" and "vibrations" (eigenvalues) of these polynomials, they could calculate the exact differences between the Real and Complex quantum states without having to simulate the impossible quantum computers.

Summary

In short, this paper puts a "speed limit" on how well we can fake quantum randomness using only Real numbers.

1. Real numbers are not enough: You cannot perfectly mimic the randomness of Complex quantum states using only Real ones.
2. We can measure the gap: The authors gave an exact formula for how easy it is to spot the difference.
3. We need more proof: To prove a state is truly "Complex" (has "Imaginarity"), you need more copies of the state than previously calculated.

The authors conclude that while Real-valued quantum systems are useful, they have a fundamental flaw: they can never fully replicate the richness and randomness of the Complex quantum world.

Technical Summary

Problem Statement
Haar random quantum states are fundamental to quantum information theory, underpinning applications such as shadow tomography, quantum advantage demonstrations, and benchmarking. However, sampling from the Haar measure on the unitary group requires quantum circuits of exponential size, rendering it impractical. Consequently, research focuses on "approximate state $t$-designs"—ensembles of efficiently preparable states that mimic the first $t$ moments of the Haar distribution. A specific class of constructions, known as Asymptotically Random States (ARS), utilizes real-valued quantum states. While real-valued quantum theory can sometimes match complex theory in computational power, it is known to be insufficient for describing all quantum phenomena. A critical open question remains: Are there fundamental limitations on the performance of real-valued state $t$-designs compared to their complex-valued counterparts? Specifically, can real-valued ensembles approximate the Haar measure on the unitary group as closely as complex-valued ensembles, and what are the implications for cryptographic primitives like pseudorandom states (PRS) and imaginarity testing?

Methodology
The authors address this by analytically studying the density matrix resulting from sampling $t$ copies of a $d$-dimensional real-valued quantum state according to the Haar measure on the orthogonal group $O_d$. The core technical approach involves:

1. Spectral Decomposition: The authors derive the exact spectral decomposition of the density matrix $\rho^R_{d,t}$ associated with $t$ copies of a real Haar random state. This is achieved by leveraging the representation theory of the orthogonal group.
2. Isomorphism to Harmonic Polynomials: They establish an isomorphism between the symmetric subspace $\vee^t \mathbb{R}^d$ and the space of homogeneous polynomials $P^t_d$ of degree $t$ in $d$ variables. Using a classical result (Coifman and Weiss, 1968), they decompose this polynomial space into subspaces of harmonic polynomials $H^t_d$ and their multiples by the quadratic form $q = \sum X_i^2$.
3. Schur's Lemma Application: By showing that the representation of $O_d$ on these harmonic subspaces is irreducible, they apply Schur's lemma to determine that the density matrix acts as a scalar multiple of the identity on each subspace. This allows for the exact calculation of eigenvalues and their multiplicities.
4. Trace Distance Calculation: Using the derived eigenvalues, they compute the exact trace distance between $\rho^R_{d,t}$ (real Haar) and $\rho^C_{d,t}$ (complex Haar). This distance quantifies the distinguishability between the two ensembles.

Key Contributions and Results

1. Exact Spectral Decomposition (Theorem 1): The paper provides closed-form analytical expressions for the eigenvalues $\lambda_k$ and multiplicities $\alpha_k$ of $\rho^R_{d,t}$. The eigenvalues are given by:
   $$\lambda_k = \frac{t!(d-2)!!}{(2k)!!(d+2t-2k-2)!!}$$
   with multiplicities determined by the dimensions of the harmonic polynomial subspaces.
2. Exact Distinguishability (Corollary 1): The authors derive an exact formula for the trace distance between real and complex Haar random states. They show that for $t \sim \alpha\sqrt{d}$, the trace distance converges to $1 - e^{-\alpha^2/2}$. This completes a previously derived upper bound by providing the exact lower bound on distinguishability.
3. Fundamental Lower Bound on Approximation (Lemma 4 & Proposition 1): Using the data processing inequality for the trace norm, the authors prove that for any ensemble of real-valued states, the trace distance to the complex Haar measure is lower-bounded by the distance between the real Haar measure and the complex Haar measure. This establishes a fundamental limitation: no real-valued $t$-design can outperform the real Haar measure in approximating the complex Haar measure.
4. Implications for ARS and PRS: The results imply that real-valued ARS constructions have an approximation parameter $\epsilon$ that scales at best as $\Omega(t^2/d)$. This limits the performance of real-valued pseudorandom state constructions, suggesting that non-zero "imaginarity" (complex amplitudes) is a necessary condition for achieving approximation parameters that scale linearly with $t$ (i.e., $\epsilon \sim t/d$).
5. Improved Bounds for Imaginarity Testing (Proposition 2): The authors generalize and improve upon the work of Haug, Bharti, and Koh (2025) regarding the number of copies required to test for the imaginarity of a state. They refine the lower bound from $\Omega(\sqrt{2^n})$ to $\sqrt{2 \ln(3/2) d} + o(\sqrt{d})$ for arbitrary dimension $d$, improving the previous bound by a factor of $\sqrt{2}$. They also derive the distribution of imaginarity for Haar random states, showing it follows a power law (specifically a Beta distribution).

Significance
The paper claims to provide a fundamental understanding of the limitations of real-valued quantum state ensembles. By analytically characterizing the spectral properties of real Haar random states, it demonstrates that real-valued approximations cannot perfectly mimic complex Haar random states, regardless of the construction method. This has direct implications for:

• Quantum Cryptography: It sets a theoretical ceiling on the security and efficiency of real-valued ARS and PRS constructions, indicating that complex amplitudes are likely required for optimal performance in certain cryptographic regimes.
• Resource Theories: It provides precise quantitative bounds on the resources (number of copies) needed to detect the presence of complex numbers (imaginarity) in a quantum state, refining previous asymptotic results.
• Technical Utility: The derived spectral decomposition and the isomorphism between symmetric subspaces and harmonic polynomials are presented as tools with potential independent utility for future research in quantum information and representation theory.

The authors remain modest regarding the implementation of the distinguishing measurement, noting that while an explicit projective measurement exists to achieve the theoretical bound, its efficient implementation (e.g., via the Schur transform) remains an open question. Similarly, they acknowledge that while they prove complex amplitudes are necessary for certain scaling behaviors, the exact amount of imaginarity required for other specific approximation parameters is an open area for future study.