Semidefinite-programming hierarchies for classically simulable state sets
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 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. 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.Where the paper says it
Where the paper says it
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 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 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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 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.Where the paper says it
Where the paper says it
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 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). (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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 (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. 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.Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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
- Robust certification of non-projective measurements: theory and experiment
- Simulating quantum measurements without superposition devices
- Quantum coherence as randomness under classical control
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements