Semidefinite-programming hierarchies for classically simulable state families

This paper introduces a complete semidefinite-programming hierarchy that characterizes classically simulable quantum state families by reformulating classical simulability as a feasibility problem, thereby providing systematic convex-optimization tools to certify simulability and compute critical classical visibility bounds.

The Gist

Imagine you have a box of different colored lights. Some of these lights are "classical" in the sense that you can turn them on and off independently without them interfering with each other. Others are "quantum," meaning they are superpositioned—like a light that is both red and blue at the same time until you look at it.

In the world of quantum physics, scientists often want to know: Is this specific collection of lights truly "quantum" in a way that gives us a superpower, or can we fake it using only classical tricks?

This paper introduces a new, highly systematic "truth detector" to answer that question. Here is how it works, broken down into simple concepts:

1. The Core Problem: The "Fake Quantum" Trap

Sometimes, a group of quantum lights looks very strange and non-classical. However, it might just be a mixture of many simple, boring, classical lights.

• The Analogy: Imagine a smoothie that tastes like a mix of exotic fruits. You might think it's a magical, new fruit. But if you look closely, it's just a blend of apples, bananas, and oranges. It looks complex, but it's actually just a combination of ordinary things.
• The Goal: The authors want to know if a "quantum smoothie" (a family of quantum states) is truly unique or if it can be built by mixing together simple, classical ingredients. If it can be built from classical ingredients, it's "classically simulable"—meaning a regular computer could mimic it perfectly, and it doesn't offer a true quantum advantage.

2. The Solution: A "Ladder" of Tests

The authors built a mathematical tool called a Semidefinite Programming (SDP) Hierarchy. Think of this as a ladder with many rungs.

• The Bottom Rung (Level 1): This is a quick, rough test. It asks, "Can we explain this with a simple mix?" If the answer is "No," we know for sure it's truly quantum. If the answer is "Maybe," we move up.
• Climbing the Ladder: As you go up the ladder (Level 2, Level 3, etc.), the tests become more detailed and strict. They look for more subtle ways the "smoothie" might be faked.
• The Top of the Ladder: The paper proves that if you keep climbing this ladder forever, you will eventually reach the absolute truth. There is no "fake quantum" that can hide from a high enough rung. The ladder is complete.

3. How the Test Works: The "Blueprint"

To check if a quantum family is fake, the authors translate the problem into a different language involving measurements (like taking a photo of the light).

• They ask: "Can we build a blueprint using only simple, one-dimensional 'projector' tools to recreate these complex lights?"
• If the answer is yes, the family is classical (fake).
• If the answer is no, the family is truly quantum.

4. The "Noise" Test: How Strong is the Quantumness?

Real-world quantum systems are messy; they get "noisy" (like static on a radio). The authors tested their ladder on families of lights mixed with this noise.

• The Question: How much noise can we add before the quantum family becomes so "dull" that a classical computer can mimic it?
• The Result: They calculated the exact "tipping point" (called critical visibility) for several famous quantum setups (like the BB84 protocol used in secure communication).
• The Discovery: For many symmetric, simple quantum families, even the second rung of the ladder was enough to find the exact tipping point. They didn't need to climb to the top to get the answer.

5. The "Certificate of Guilt"

If the test says a family is not classically simulable (i.e., it is truly quantum), the system doesn't just say "No." It produces a certificate.

• The Analogy: Imagine a detective not just saying, "This guy is innocent," but handing you a signed document that proves exactly why he is innocent, which anyone can check.
• In the paper, this is called an affine witness. It's a mathematical proof that you can use to certify that a specific set of lights cannot be faked by classical means.

Summary

The paper provides a systematic, step-by-step mathematical ladder that can definitively tell us if a group of quantum states is truly "quantum" or just a clever mix of classical states.

• It works for any size of quantum system.
• It guarantees that if you go high enough up the ladder, you get the perfect answer.
• In practice, for many common quantum setups, just the first few steps of the ladder are enough to find the exact answer.
• It gives us a way to measure exactly how much "noise" a quantum system can handle before losing its special quantum powers.

This tool helps scientists distinguish between "real" quantum magic and "fake" quantum that can be explained by old-school classical physics.

Technical Summary

Technical Summary: Semidefinite-Programming Hierarchies for Classically Simulable State Families

Problem Statement
The paper addresses the fundamental task in quantum resource theory of determining whether a family of quantum states $\{\rho_x\}$ admits an irreducible quantum advantage. While non-commutativity is a necessary condition for non-classicality, it is not sufficient; a family may be non-commuting yet lie within the convex hull of classical (pairwise commuting) families. Such families are termed "classically simulable" because their measurement statistics can be explained by a local hidden-variable model. The central challenge identified is the lack of a systematic, convergent method to characterize the set of all classically simulable state families in arbitrary finite dimensions, particularly beyond the restricted numerical searches of previous works.

Methodology
The authors develop a complete semidefinite-programming (SDP) hierarchy to characterize the set of classically simulable state families, denoted as $C(d, n)$. The methodology proceeds through three main logical steps:

1. Reformulation as a Feasibility Problem:
   The authors reformulate classical simulability as a feasibility problem involving deterministic response functions and auxiliary positive-operator-valued measures (POVMs). They establish that a state family is classically simulable if and only if it can be decomposed into a convex combination of classical families. This decomposition is shown to be equivalent to the existence of a set of auxiliary operators $\{\tau_{i,\mu}\}$ such that their normalized versions form POVMs that are simulable by rank-one projective measurements. This creates a direct bridge between the classical simulability of state families and the projective simulability of POVMs.

2. SDP Hierarchy for Rank-One Projective Simulability:
   To characterize the set of POVMs simulable by rank-one projective measurements, denoted $P(d, d; 1)$, the authors construct a sequence of semidefinite outer approximations $\{P_\ell(d, d; 1)\}_{\ell \geq 2}$. This hierarchy utilizes "lifted" operators acting on tensor product spaces $(\mathbb{C}^d)^{\otimes \ell}$ subject to positivity, trace normalization, marginal constraints, and swap constraints (ensuring consistency with the underlying quantum structure).

   • Completeness: The authors prove that this hierarchy is asymptotically complete: a POVM belongs to $P(d, d; 1)$ if and only if it belongs to $P_\ell(d, d; 1)$ for all $\ell \geq 2$.

3. Transfer to State Families and Dual Witnesses:
   The complete hierarchy for POVMs is transferred to the set of state families $C(d, n)$. By replacing the exact constraint in the feasibility problem with the level-$\ell$ relaxation, the authors define a sequence of outer approximations $C_\ell(d, n)$.

   • Primal Formulation: This yields a computable SDP feasibility test to determine if a given family belongs to the relaxed set.
   • Dual Formulation: The dual SDP provides explicit affine witnesses. If a dual-feasible point yields a negative value for a specific state family, it certifies that the family lies outside the relaxed set (and thus outside the set of classically simulable families).

Key Results
The authors apply their hierarchy to state families mixed with depolarizing noise, $\Lambda_v(\rho) = v\rho + [(1-v)/d]I$, to compute the critical classical visibility $\chi(\rho)$, defined as the maximum noise parameter $v$ for which the family remains classically simulable.

• Symmetric Qubit Families: For four symmetric families (BB84, six-state, trine, and tetrahedral), the level-2 hierarchy yields critical visibility bounds that match known analytical thresholds or are confirmed by explicit classical simulations constructed from the optimal SDP solutions. For these cases, levels $\ell=3$ and $\ell=4$ provide no improvement, indicating low levels capture the boundary.
• Higher-Dimensional Families: The hierarchy was applied to qutrit and higher-dimensional families, including Mutually Unbiased Bases (MUB) and Symmetric Informationally Complete (SIC) sets.
  • The results provide computable upper bounds on $\chi(\rho)$ (via the primal SDP) and lower bounds (via explicit simulations using finite collections of classical families).
  • For the qutrit MUB family $\rho_1$, the level-2 and level-3 bounds coincide at $\chi \approx 2/3$, which is matched by an explicit simulation.
  • Aggregated vs. Canonical Lifts: The authors compare two implementations: the "canonical lift" (tracking individual deterministic assignments) and the "aggregated relaxation" (tracking aggregate operators). For the highly symmetric families studied, both methods yielded identical numerical bounds, suggesting that for structured examples, the aggregated relaxation suffices to capture the relevant boundary information.

Significance and Claims
The paper claims to provide the first complete SDP hierarchy for characterizing classically simulable state families in arbitrary finite dimensions. Its significance lies in:

• Systematic Characterization: Moving beyond sufficient certificates (inner approximations) to a convergent sequence of necessary and sufficient conditions (outer approximations) for classical simulability.
• Operational Tools: Offering both primal feasibility tests and dual affine witnesses. The witnesses allow for the certification of irreducible quantumness (failure of classical simulability) without requiring full state-family tomography, relying only on expectation values.
• Quantifiable Robustness: Providing a systematic convex-optimization framework to compute the critical classical visibility, quantifying the robustness of quantum state families against depolarizing noise.

The authors note that while their approach starts from a reformulation involving deterministic response functions and rank-one projective simulability, it achieves convergence guarantees comparable to independent recent work by Cobucci et al. (which uses multipartite extensions and de Finetti theorems), but through a distinct derivation path. The framework is presented as a tool for certifying irreducible quantumness and may extend to related convex-geometric problems in quantum information.