Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.34972

Membership in the cone of quantum states over time is NP-hard

Matt Hoogsteder-Riera

quant-phmath-phSubmitted Oct 26, 2026• Announced Oct 27, 2026• 0 citations• Revised Oct 30, 2026 (v2)
v1 · Oct 26, 2026v2 · Oct 30, 2026
arXivHTMLPDF

Abstract

A state over time (stote) pairs a state $ρ$ with a channel $\mathcal{E}$ as the Hermitian, generally non-positive operator $(ρ\otimes\mathbf{1})\star J_\mathcal{E}$. Characterizing the convex cone $\widehat{\mathcal{Q}}$ these operators generate was posed as an open problem in Hoogsteder-Riera, Calsamiglia and Winter (2026). We exhibit a linear copy of the bipartite separable cone as an exposed face of $\widehat{\mathcal{Q}}$: for output systems of the form $B = A'R$ with $A'$ a copy of the input, there is an explicit witness $W_0\in\widehat{\mathcal{Q}}^*$ and an explicit injective linear map $L$ with $σ\in \mathrm{SEP}_{+}(A{:}R)\iff L(σ)\in\widehat{\mathcal{Q}}(A{:}A'R)$. Composing with the NP-hardness of separability shows that exact membership, weak membership, and weak optimization are NP-hard for $\widehat{\mathcal{Q}}$ and its dual. A quantitative stability bound makes the weak-membership reduction valid at inverse-polynomial accuracy. Thus polynomial-time membership tests do not exist unless $\mathrm{P}=\mathrm{NP}$. Independently of this complexity assumption, Fawzi's theorem implies that $\widehat{\mathcal{Q}}(A{:}A'R)$ admits no finite semidefinite representation when $d=\dim A\ge2$, $r=\dim R\ge2$, and $d+r>5$.

AI Summary

The paper studies membership in the convex cone $\widehat{\mathcal Q}$ generated by Jordan-product states over time, $Q=(\rho\otimes\mathbf1)\star J_{\mathcal E}$, which are Hermitian but need not be positive. This addresses a characterization problem motivated by quantum optimal transport. The object is the convex cone, not the set of operators realizable by a single state–channel pair. For outputs $B=A'R$, with $A'\cong A$ and dimensions $d=\dim A$, $r=\dim R$, it constructs an exposed face linearly isomorphic to $\mathrm{SEP}_+(A{:}R)$. The witness is $W_0=(d\mathbf1-S_{AA'})\otimes\mathbf1_R$, and the embedding is $L=\Gamma\otimes\mathrm{id}_R$, where $\Gamma(X)=\{X\otimes\mathbf1,S\}/2$. Zero witness pairing forces the channel to be identity transmission into $A'$ with an independently prepared state on $R$. Consequently, $\sigma$ is separable exactly when $L(\sigma)\in\widehat{\mathcal Q}$. The embedding establishes NP-hardness of exact membership. A stability bound, $\operatorname{dist}_1(Y,L(\mathrm{SEP}_+))\le2\sqrt2\,d^{3/2}\sqrt{\operatorname{Tr}Y\,\operatorname{Tr}(W_0Y)}$, combined with mixing toward the maximally mixed state, establishes strong NP-hardness of weak membership at inverse-polynomial accuracy. Oracle equivalences transfer hardness to weak optimization and dual-cone problems. Separately, Fawzi’s separability obstruction excludes every finite semidefinite lift when $d,r\ge2$ and $d+r>5$. The hardness statements concern variable dimensions and do not establish hardness for constant output dimension or constant Hilbert–Schmidt accuracy. The stability exponent $1/2$ is shown optimal, while its dimension dependence remains open. Exact membership lies in $\exists\mathbb R$; its precise complexity is unresolved.

Some signs of AI-generated textAI use disclosed
LLM assistance, in particular OpenAI's Codex, has been used to derive the results and to assist in writing the manuscript.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
23 pages, 2 Figures

Related papers

Convex semidefinite tensor optimization and quantum entanglement

Liding Xu, Ye-Chao Liu, Sebastian Pokutta

The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods.

math.OCCross-listedarXiv:2511.05258•Nov 10, 2025•1 citation

SEPARABILITY: A NEW APPROACH FROM THE CONIC STRUCTURE OF POSITIVE OPERATORS

David Cienfuegos Salgado, J. L. Sánchez‐Gómez, Miguel Ferrero

We exploit the cone structure of unnormalized quantum states to reformulate the separability problem. Firstly a convex combination of every quantum state ρ in terms of a state Cρ with the same rank and another one Eρ with lower rank is perfomed, with weights 1 − λρ and λρ, respectively. Secondly a scalar [Formula: see text] is computed. Then ρ is separable if, and only if, [Formula: see text]. The computation of [Formula: see text] has been undergone under the simplest choice for Cρ as a product matrix and Eρ being a pure state, valid for any bipartite and multipartite system in arbitrary dimensions. A necessary condition is also formulated when Eρ is not pure in the bipartite case.

International Journal of Quantum Information•Jan 1, 2011•0 citations

Checking 2×M quantum separability via semidefinite programming

Hugo J. Woerdeman

In this paper, we propose a sequence of tests which give a definitive test for checking $2\ifmmode\times\else\texttimes\fi{}M$ separability. The test is definitive in the sense that each test corresponds to checking membership in a cone, and that the closure of the union of all these cones consists exactly of all $2\ifmmode\times\else\texttimes\fi{}M$ separable states. Membership in each single cone may be checked via semidefinite programming, and is thus a tractable problem. This sequential test comes about by considering the dual problem, the characterization of all positive maps acting ${C}^{2\ifmmode\times\else\texttimes\fi{}2}\ensuremath{\rightarrow}{C}^{M\ifmmode\times\else\texttimes\fi{}M}.$ The latter in turn is solved by characterizing all positive quadratic matrix polynomials in a complex variable.

arXiv:quant-ph/0301058•Physical Review A•Jan 30, 2003•10 citations

FACIAL STRUCTURES FOR SEPARABLE STATES

Hyun-Suk Choi, Seung-Hyeok Kye

The convex cone $\mathbb{V}_1$ generated by separable states is contained in the cone $\mathbb{T}$ of all positive semi-definite block matrices whose block transposes are also positive semi-definite. We characterize faces of the cone $\mathbb{V}_1$ induced by faces of the cone $\mathbb{T}$ which are determined by pairs of subspaces of matrices.

Journal of the Korean Mathematical Society•May 1, 2012•17 citations

On the Chvátal-Gomory Closure of Integer Quadratic Programs

Linchuan Wei, Tong Xu, Kim Yu

The integer quadratic moment hull is the closed convex hull of the pairs $(z,zz^{\top})$ with $z\in\mathbb{Z}^n$. We prove that one round of Chvátal-Gomory (CG) cuts applied to its basic semidefinite relaxation recovers this hull exactly if and only if $n\le6$. Our approach identifies its facets with perfect Delaunay polyhedra and characterizes their recovery through depth, the gap between lattice and continuous minima of a defining quadratic after normalization. A facet inequality is valid for the rank-one CG closure exactly when its depth is less than one. We also analyze the complexity of deciding membership in the CG closure and finding violated inequalities. Every rational point outside the CG closure admits a violated CG inequality whose encoding length is polynomial in the input length. Membership is strongly coNP-complete and exact separation is strongly NP-hard. The same reduction proves strong NP-hardness of quadratic split-inequality separation, resolving a conjecture of Burer and Letchford.

arXiv:2610.34053•Oct 25, 2026•0 citations

The convex structure of the cone of N-fermion positive-semidefinite 1-particle operators

Hubert Grudziński, Jacek Hirsch

Reports on Mathematical Physics•Jun 1, 2000•0 citations
A state over time (stote) pairs a state ρρρ with a channel E\mathcal{E}E as the Hermitian, generally non-positive operator (ρ⊗1)⋆JE(ρ\otimes\mathbf{1})\star J_\mathcal{E}(ρ⊗1)⋆JE​. Characterizing the convex cone Q^\widehat{\mathcal{Q}}Q​ these operators generate was posed as an open problem in Hoogsteder-Riera, Calsamiglia and Winter (2026). We exhibit a linear copy of the bipartite separable cone as an exposed face of Q^\widehat{\mathcal{Q}}Q​: for output systems of the form B=A′RB = A'RB=A′R with A′A'A′ a copy of the input, there is an explicit witness W0∈Q^∗W_0\in\widehat{\mathcal{Q}}^*W0​∈Q​∗ and an explicit injective linear map LLL with σ∈SEP+(A:R)  ⟺  L(σ)∈Q^(A:A′R)σ\in \mathrm{SEP}_{+}(A{:}R)\iff L(σ)\in\widehat{\mathcal{Q}}(A{:}A'R)σ∈SEP+​(A:R)⟺L(σ)∈Q​(A:A′R). Composing with the NP-hardness of separability shows that exact membership, weak membership, and weak optimization are NP-hard for Q^\widehat{\mathcal{Q}}Q​ and its dual. A quantitative stability bound makes the weak-membership reduction valid at inverse-polynomial accuracy. Thus polynomial-time membership tests do not exist unless P=NP\mathrm{P}=\mathrm{NP}P=NP. Independently of this complexity assumption, Fawzi's theorem implies that Q^(A:A′R)\widehat{\mathcal{Q}}(A{:}A'R)Q​(A:A′R) admits no finite semidefinite representation when d=dim⁡A≥2d=\dim A\ge2d=dimA≥2, r=dim⁡R≥2r=\dim R\ge2r=dimR≥2, and d+r>5d+r>5d+r>5.
The paper studies membership in the convex cone Q^\widehat{\mathcal Q}Q​ generated by Jordan-product states over time, Q=(ρ⊗1)⋆JEQ=(\rho\otimes\mathbf1)\star J_{\mathcal E}Q=(ρ⊗1)⋆JE​, which are Hermitian but need not be positive. This addresses a characterization problem motivated by quantum optimal transport. The object is the convex cone, not the set of operators realizable by a single state–channel pair.
For outputs B=A′RB=A'RB=A′R, with A′≅AA'\cong AA′≅A and dimensions d=dim⁡Ad=\dim Ad=dimA, r=dim⁡Rr=\dim Rr=dimR, it constructs an exposed face linearly isomorphic to SEP+(A:R)\mathrm{SEP}_+(A{:}R)SEP+​(A:R). The witness is W0=(d1−SAA′)⊗1RW_0=(d\mathbf1-S_{AA'})\otimes\mathbf1_RW0​=(d1−SAA′​)⊗1R​, and the embedding is L=Γ⊗idRL=\Gamma\otimes\mathrm{id}_RL=Γ⊗idR​, where Γ(X)={X⊗1,S}/2\Gamma(X)=\{X\otimes\mathbf1,S\}/2Γ(X)={X⊗1,S}/2. Zero witness pairing forces the channel to be identity transmission into A′A'A′ with an independently prepared state on RRR. Consequently, σ\sigmaσ is separable exactly when L(σ)∈Q^L(\sigma)\in\widehat{\mathcal Q}L(σ)∈Q​.
The embedding establishes NP-hardness of exact membership. A stability bound, dist⁡1(Y,L(SEP+))≤22 d3/2Tr⁡Y Tr⁡(W0Y)\operatorname{dist}_1(Y,L(\mathrm{SEP}_+))\le2\sqrt2\,d^{3/2}\sqrt{\operatorname{Tr}Y\,\operatorname{Tr}(W_0Y)}dist1​(Y,L(SEP+​))≤22​d3/2TrYTr(W0​Y)​, combined with mixing toward the maximally mixed state, establishes strong NP-hardness of weak membership at inverse-polynomial accuracy. Oracle equivalences transfer hardness to weak optimization and dual-cone problems. Separately, Fawzi’s separability obstruction excludes every finite semidefinite lift when d,r≥2d,r\ge2d,r≥2 and d+r>5d+r>5d+r>5.
The hardness statements concern variable dimensions and do not establish hardness for constant output dimension or constant Hilbert–Schmidt accuracy. The stability exponent 1/21/21/2 is shown optimal, while its dimension dependence remains open. Exact membership lies in ∃R\exists\mathbb R∃R; its precise complexity is unresolved.
The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods.
We exploit the cone structure of unnormalized quantum states to reformulate the separability problem. Firstly a convex combination of every quantum state ρ in terms of a state Cρ with the same rank and another one Eρ with lower rank is perfomed, with weights 1 − λρ and λρ, respectively. Secondly a scalar [Formula: see text] is computed. Then ρ is separable if, and only if, [Formula: see text]. The computation of [Formula: see text] has been undergone under the simplest choice for Cρ as a product matrix and Eρ being a pure state, valid for any bipartite and multipartite system in arbitrary dimensions. A necessary condition is also formulated when Eρ is not pure in the bipartite case.
In this paper, we propose a sequence of tests which give a definitive test for checking $2\ifmmode\times\else\texttimes\fi{}M$ separability. The test is definitive in the sense that each test corresponds to checking membership in a cone, and that the closure of the union of all these cones consists exactly of all $2\ifmmode\times\else\texttimes\fi{}M$ separable states. Membership in each single cone may be checked via semidefinite programming, and is thus a tractable problem. This sequential test comes about by considering the dual problem, the characterization of all positive maps acting ${C}^{2\ifmmode\times\else\texttimes\fi{}2}\ensuremath{\rightarrow}{C}^{M\ifmmode\times\else\texttimes\fi{}M}.$ The latter in turn is solved by characterizing all positive quadratic matrix polynomials in a complex variable.
The convex cone V1\mathbb{V}_1V1​ generated by separable states is contained in the cone T\mathbb{T}T of all positive semi-definite block matrices whose block transposes are also positive semi-definite. We characterize faces of the cone V1\mathbb{V}_1V1​ induced by faces of the cone T\mathbb{T}T which are determined by pairs of subspaces of matrices.
The integer quadratic moment hull is the closed convex hull of the pairs (z,zz⊤)(z,zz^{\top})(z,zz⊤) with z∈Znz\in\mathbb{Z}^nz∈Zn. We prove that one round of Chvátal-Gomory (CG) cuts applied to its basic semidefinite relaxation recovers this hull exactly if and only if n≤6n\le6n≤6. Our approach identifies its facets with perfect Delaunay polyhedra and characterizes their recovery through depth, the gap between lattice and continuous minima of a defining quadratic after normalization. A facet inequality is valid for the rank-one CG closure exactly when its depth is less than one. We also analyze the complexity of deciding membership in the CG closure and finding violated inequalities. Every rational point outside the CG closure admits a violated CG inequality whose encoding length is polynomial in the input length. Membership is strongly coNP-complete and exact separation is strongly NP-hard. The same reduction proves strong NP-hardness of quadratic split-inequality separation, resolving a conjecture of Burer and Letchford.