Semidefinite-programming hierarchies for classically simulable state sets

arXiv:2606.06204 · quant-ph · Submitted 2026-06-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai.

Mira: And I'm Mira, here with Lev.

Kai: We're looking at the paper: "Semidefinite-programming hierarchies for classically simulable state sets".

Mira: Here's the gist of the paper. Identifying whether a state family admits an irreducible quantum advantage is a fundamental task in quantum resource theory and quantum information processing.

Kai: This work develops a complete semidefinite-programming (SDP) hierarchy characterizing the set of classically simulable state families in arbitrary finite dimension.

Mira: Characterization of Classically Simulable Families The paper establishes a complete SDP hierarchy to characterize the set of classically simulable state families in arbitrary finite dimension.

Kai: This is achieved by reformulating classical simulability as a feasibility problem involving deterministic response functions and auxiliary positive-operator-valued measures (POVMs) simulable by rank-one projective measurements.

Title and authors: Kai: So we're looking at this paper titled "Semidefinite-programming hierarchies for classically simulable state sets." It seems like they're tackling the big question of what makes a quantum state family fundamentally different from something classical.

Mira: Yeah, it’s about characterizing the set of classically simulable families in any finite dimension. They use semidefinite programming to build a complete hierarchy to figure this out.

Lev: From an engineering standpoint, it sounds like they are building a mathematical filter that can tell you if your quantum state family is too complex for classical computers to handle easily. That’s useful for setting hardware requirements, I guess.

Kai: Exactly, and the authors are Mengyan Li, Yanning Jia, Fenzhuo Guo, Haifeng Dong, Sujuan Qin and Fei Gao. They're coming from a few different mathematical and physics backgrounds which is interesting for connecting the theory to actual physical systems.

Mira: Yeah, their approach seems to bridge that gap by translating the quantum state problem into a feasibility problem involving deterministic response functions and these auxiliary positive-operator-valued measures or POVMs that can be simulated by rank one projective measurements.

Lev: That sounds like a necessary step for any practical check because rank one measurements are what we actually build with on current hardware, so connecting it to that is smart.

The paper's summary: Kai: So, what the paper actually does is develop this complete semidefinite programming hierarchy to define the set of classically simulable state families in arbitrary finite dimension. They’re essentially creating a systematic way to check if a given family fits into that classical realm.

Mira: They achieve this by first proving completeness for a specific level of approximation involving rank one projectively simulable POVMs, which they call P ell d d one. Then, they transfer that result over to the state families themselves.

Lev: If I’m hearing you right, they establish that if you can approximate the required POVMs up to a certain level l greater than two, then you have characterized all of them exactly for the state families too. That asymptotic completeness is a strong claim because it means we don't need to check infinitely many levels.

Kai: Right, and they reduce deciding whether a specific state family belongs to that classically simulable set C d n down to checking if certain auxiliary POVMs belong to that rank one projectively simulable set P d d one.

Mira: And they show the final set of classically simulable families C d n is recovered exactly by taking the intersection of these outer approximations, specifically starting from level two and going up. That means you get a precise characterization through this hierarchy.

Lev: So for someone building an error correction code, this gives them a rigorous way to see what kind of entanglement or complexity they are dealing with before you even start simulating it on actual hardware.

The paper's improvements: Kai: One of the key improvements they highlight is that applying this hierarchy to state families mixed with depolarizing noise allows them to compute computable upper bounds for the critical classical visibility, which they call chi of rho.

Mira: That’s significant because it means we can get concrete numbers on how good a classical simulation can be, and those numbers match explicit simulations for some symmetric qubit families and even a qutrit mutually unbiased basis family.

Lev: Being able to compute these upper bounds for visibility is very valuable because it gives us a measurable threshold that tells us where the quantum advantage might start showing up when we add noise.

Kai: They also developed a dual formulation of the SDP hierarchy, which provides explicit witnesses that certify the failure of classical simulability. These witnesses are defined by operators W l x, S l mu and t l.

Mira: That’s a big deal because it gives us a way to directly test nonclassicality without needing to perform full state family tomography, which would be computationally prohibitive for large systems.

Lev: An explicit certificate of nonclassicality is much better than just an upper bound; it’s something you can check algorithmically, which is what we need when designing experiments or error correction protocols.

Conclusion: Kai: To wrap up, this paper establishes a complete semidefinite programming hierarchy that characterizes the set of classically simulable state families in any finite dimension. It boils down to checking membership in that specific set of POVMs.

Mira: The main implication is providing a rigorous, complete way to test for classical simulability and giving us computable upper bounds on visibility when noise is present. They also give us explicit dual witnesses that certify nonclassicality without needing full tomography.

Lev: For hardware implementation, they show two ways to solve this: the canonical lift and the aggregated relaxation. The canonical lift gives sharper approximations but costs a lot, scaling as O d n plus three l, while aggregated relaxation is cheaper but weaker for larger problems.

Kai: So we can choose our path based on what we need: if accuracy is paramount for smaller systems, use the canonical lift; otherwise, the aggregated relaxation might be a better screening tool for larger computations.

Mira: This work moves us closer to systematically identifying exactly where quantum mechanics starts to give us an advantage over classical physics in these state families.

Lev: I just think having that explicit certificate of nonclassicality is the most practical part for real-world research right now because it makes the theoretical idea actionable.

Kai: Thanks for listening, and we'll see you next time when we look at what’s next on arXiv.

Beijing University of Posts and Telecommunications · Beihang University

quant-ph

Submitted: 2026-06-04

Updated: 2026-11-10

DOI: 10.1103/6f3j-jx35

Code: https://github.com/Meng-yan-Li/Classical-Simulability

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: Identifying whether a state family admits an irreducible quantum advantage is a fundamental task in quantum resource theory and quantum information processing.

Key concepts

Classically Simulable State Families
This refers to sets of quantum states that can be perfectly replicated or approximated by classical methods. The paper establishes a complete mathematical tool, an SDP hierarchy, to definitively determine if a given state family belongs to this set in any finite dimension.
Rank-One Projectively Simulable POVMs
POVMs are quantum measurements. This concept focuses on measurements that can be simulated using only rank-one projective measurements. The paper proves a complete hierarchy for these specific types of POVMs, which serves as the foundation for characterizing the broader state families.
Semidefinite Programming (SDP) Hierarchy
This is a structured set of optimization problems used to solve complex decision problems in quantum information. The hierarchy consists of increasingly accurate outer approximations that help determine if a state family is classically simulable by checking feasibility across different levels of approximation.
Dual Witnesses
These are mathematical tools derived from the SDP formulation that explicitly prove when a state family *cannot* be classically simulated. They act as certificates, showing exactly why the system exhibits nonclassical behavior without needing a full quantum simulation.

Terminology

Summary

Identifying whether a state family admits an irreducible quantum advantage is a fundamental task in quantum resource theory and quantum information processing. p. 0

Where the paper says it

Semidefinite-programming hierarchies for classically simulable state families Mengyan Li,1, 2, 3 Yanning Jia,1, 2, 3 Fenzhuo Guo,1, 2, 3, ∗ Haifeng Dong,4 Sujuan Qin,3 and Fei Gao3 1School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China 2Key Laboratory of Mathematics and Information Networks, Beijing University of Posts and Telecommunications, Ministry of Education, Beijing 100876, China 3State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China 4School of Instrumentation Science and Opto-Electronics Engineering, Beihang University, Beijing 100191, China Identifying whether a state family admits an irreducible quantum advantage is a fundamental task in quantum resource theory and quantum information processing. Here we study classically simulable state families, namely those residing within the convex hull of pairwise commuting families and therefore admitting a classical explanation.

This work develops a complete semidefinite-programming (SDP) hierarchy characterizing the set of classically simulable state families in arbitrary finite dimension. p. 0
Where the paper says it

Here we study classically simulable state families, namely those residing within the convex hull of pairwise commuting families and therefore admitting a classical explanation. We develop a complete semidefinite-programming (SDP) hierarchy characterizing the set of classically simulable state families in arbitrary finite dimension.

Characterization of Classically Simulable Families

The paper establishes a complete SDP hierarchy to characterize the set of classically simulable state families in arbitrary finite dimension. This is achieved by reformulating classical simulability as a feasibility problem involving deterministic response functions and auxiliary positive-operator-valued measures (POVMs) simulable by rank-one projective measurements. p. 0

Where the paper says it

In this work, we develop a complete semidefiniteprogramming (SDP) hierarchy characterizing the set of classically simulable state families in arbitrary finite dimension. We first reformulate classical simulability as a feasibility problem involving deterministic response functions and auxiliary positive-operator-valued measures (POVMs) simulable by rank-one projective measurements [14].

The key step involves proving the completeness of an SDP hierarchy for rank-one projectively simulable POVMs and transferring this characterization to state families. p. 4
Where the paper says it

The key step was to reduce classical simulability to the rank-one projective simulability of auxiliary POVMs. By proving the completeness of the associated hierarchy and transferring the resulting characterization to state families, we obtained a hierarchy of computable SDP outer approximations whose intersection recovers C(d, n) exactly.

This leads to a complete hierarchy for classically simulable state families. p. 0
Where the paper says it

Here we study classically simulable state families, namely those residing within the convex hull of pairwise commuting families and therefore admitting a classical explanation. We develop a complete semidefinite-programming (SDP) hierarchy characterizing the set of classically simulable state families in arbitrary finite dimension.

Hierarchy Structure and Completeness

The paper introduces a hierarchy of semidefinite outer approximations to the set of rank-one projectively simulable POVMs, denoted as Pl(d, d; 1). The hierarchy is shown to be asymptotically complete, meaning that a POVM M belongs to Pl(d, d; 1) for every integer l ≥ 2 if and only if M belongs to P(d, d; 1). p. 6

Where the paper says it

Completeness of the Projective-Simulability Hierarchy We begin by recalling the larger set P(m, d) consisting of POVMs with m outcomes acting on a d-dimensional Hilbert space that are simulable by arbitrary projective measurements [14, 25, 26]. A POVM M = {Mi} m i=1 belongs to P(m, d) if there exists a probability distribution {wk}k and projective measurements {P k i } m i=1 such that Mi = P k wkP k i for all i.

This completeness of the rank-one projective simulability hierarchy induces a complete hierarchy for classically simulable state families. p. 0
Where the paper says it

This establishes a bridge between the classical simulability of state families and the projective simulability of POVMs. We then prove the completeness of an SDP hierarchy for rank-one projectively simulable POVMs, which in turn induces a complete hierarchy for classically simulable state families.

Characterization of State Families

The decision problem of whether a given family ρ belongs to C(d, n) is reduced to deciding membership of auxiliary POVMs in the rank-one projectively simulable set P(d, d; 1). This reduction is made possible by Theorem 1, which states that the complete hierarchy for P(d, d; 1) induces a complete hierarchy for C(d, n). p. 2

Where the paper says it

In this way, deciding classical simulability of state families is reduced to deciding membership of a collection of auxiliary POVMs in the rank-one projectively simulable set P(d, d; 1). Theorem 1 therefore makes this reduction algorithmically useful: the complete hierarchy for P(d, d; 1) induces a complete hierarchy for C(d, n).

The set C(d, n) is recovered exactly as the intersection of the outer approximations Cl(d, n)l≥2. p. 2
Where the paper says it

(6) introduces no relaxation beyond replacing P(d, d; 1) by Pℓ(d, d; 1), exact recovery of P(d, d; 1) in the hierarchy limit transfers directly to exact recovery of C(d, n). Theorem 2 therefore establishes a convergent semidefinite characterization of classical simulability: the set C(d, n) is recovered exactly as the intersection of the outer approximations {Cℓ(d, n)}ℓ≥2, reducing the original convex-simulations problem to a hierarchy of finitedimensional SDP feasibility tests.

Numerical Bounds and Dual Witnesses

Applying the hierarchy to state families mixed with depolarizing noise yields computable upper bounds on the critical classical visibility, denoted as χ(ρ). The paper provides numerical results for several symmetric qubit families and a qutrit mutually unbiased basis (MUB) family, where the numerical upper bounds are matched by explicit classical simulations. p. 4

Where the paper says it

Applied to state families mixed with depolarizing noise, the hierarchy yielded computable upper bounds on the critical classical visibility. Our numerical results identified critical classical visibilities for several symmetric qubit families and for a qutrit MUB family, with the numerical upper bounds matched by explicit classical simulations.

Furthermore, the SDP hierarchy admits a dual formulation which yields explicit witnesses certifying the failure of classical simulability. p. 2
Where the paper says it

Theorem 2 therefore establishes a convergent semidefinite characterization of classical simulability: the set C(d, n) is recovered exactly as the intersection of the outer approximations {Cℓ(d, n)}ℓ≥2, reducing the original convex-simulations problem to a hierarchy of finitedimensional SDP feasibility tests. The SDP hierarchy also admits a dual formulation, which yields explicit witnesses the failure of classical simulability.

Tradeoffs in Implementation

The paper discusses two implementation strategies for solving the problem: the canonical lift and the aggregated relaxation. The canonical lift imposes the conic lifted constraints separately for each deterministic assignment µ, providing a sharp level-l outer approximation at a substantial computational cost scaling as O(d n+3l). p. 2

Where the paper says it

(6) is obtained by imposing the conic lifted constraints for Pℓ(d, d; 1) separately for each deterministic assignment µ [17]. We refer to this as the canonical lift.

The aggregated relaxation is computationally cheaper but provides a weaker outer approximation by imposing the lifted constraints only once on an aggregate POVM. p. 2
Where the paper says it

A computationally cheaper alternative is obtained by first forming the aggregate operators τ¯i := P µ τi,µ and imposing the lifted constraints only on the single POVM {τ¯i} d i=1 . This aggregated relaxation removes the deterministic-assignment index from the lifted variables and substantially reduces the SDP size, at the cost of discarding part of the hidden-variable structure.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Precise certification of classical simulability for state families can be achieved by reducing it to a feasibility problem over deterministic response functions and auxiliary positive-operator-valued measures (POVMs) simulable by rank-one projective measurements. This allows an AI system to test whether a given family rho belongs to C(d, n) using the complete semidefinite programming hierarchy.

  2. Computationally tractable upper bounds for the critical classical visibility can be computed for state families mixed with depolarizing noise by applying the hierarchy to these noisy states. This enables an AI system to determine computable upper bounds on visibility, which are matched by explicit classical simulations in several symmetric examples.

  3. Explicit affine certificates for the failure of classical simulability can be generated using the dual formulation of the SDP hierarchy. These certificates, defined by operators W(l)x, S(l)µ, and t(l), provide a directly testable certificate of nonclassicality without requiring full state-family tomography.

  4. The system can distinguish between the canonical lift and aggregated relaxation approaches based on computational trade-offs. It can choose the canonical lift when accuracy is essential for manageable problem sizes, or use the aggregated relaxation as an effective screening tool for larger-scale computations due to its reduced computational cost.

Abstract

Determining whether a quantum state set admits a classical explanation is a fundamental problem in quantum information theory, as it reveals whether the information encoded in state preparation can be reproduced by classical means. Here we study classically simulable state sets, namely those admitting realizations using shared randomness and preparation devices that individually generate only pairwise commuting state sets. We develop a complete semidefinite programming (SDP) hierarchy to characterize the set of classically simulable state sets. The key step is a reformulation of classical simulability as a feasibility problem involving deterministic response functions and auxiliary positive-operator-valued measures (POVMs) simulable by rank-one projective measurements. We then establish a complete SDP hierarchy for rank-one projectively simulable POVMs, which in turn induces computable outer approximations converging to the set of classically simulable state sets. The corresponding dual SDP further yields affine witnesses that can be used to rule out classical simulability. Applying the hierarchy to state sets under depolarizing noise yields computable upper bounds on the critical visibility. For several highly symmetric examples, these bounds are matched by explicit classical simulations, providing evidence for the practical usefulness of the hierarchy.

Sources

Related papers