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
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~\cite{HoogstederCalsamigliaWinter2025}. 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$.

Comments
22 pages, 2 Figures

Related papers

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•8 citations

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•0 citations

Semidefinite descriptions of separable matrix cones

Roland Hildebrand

Let K, K' be convex cones residing in finite-dimensional real vector spaces E, E'. An element in the tensor product E \otimes E' is K \otimes K'-separable if it can be represented as finite sum \sum_l x_l \otimes x'_l with x_l \in K and x_l' \in K' for all l. Let S(n), H(n), Q(n) be the spaces of n x n real symmetric, complex hermitian and quaternionic hermitian matrices, respectively. Let further S_+(n), H_+(n), Q_+(n) be the cones of positive semidefinite matrices in these spaces. If a matrix in H(mn) = H(m) \otimes H(n) is H_+(m) \otimes H_+(n)-separable, then it fulfills also the so-called PPT condition, i.e. it is positive semidefinite and has a positive semidefinite partial transpose. The same implication holds for matrices in the spaces S(m) \otimes S(n), H(m) \otimes S(n), and for m < 3 in the space Q(m) \otimes S(n). We provide a complete enumeration of all pairs (n,m) when the inverse implication is also true for each of the above spaces, i.e. the PPT condition is sufficient for separability. We also show that a matrix in Q(n) \otimes S(2) is Q_+(n) \otimes S_+(2)-separable if and only if it is positive semidefinite.

arXiv:math/0701571•Jan 20, 2007•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

A cone approach to the quantum separability problem

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

Exploiting the cone structure of the set of unnormalized mixed quantum states, we offer an approach to detect separability independently of the dimensions of the subsystems. We show that any mixed quantum state can be decomposed as $ρ=(1-λ)C_ρ+λE_ρ$, where $C_ρ$ is a separable matrix whose rank equals that of $ρ$ and the rank of $E_ρ$ is strictly lower than that of $ρ$. With the simple choice $C_ρ=M_{1}\otimes M_{2}$ we have a necessary condition of separability in terms of $λ$, which is also sufficient if the rank of $E_ρ$ equals 1. We give a first extension of this result to detect genuine entanglement in multipartite states and show a natural connection between the multipartite separability problem and the classification of pure states under stochastic local operations and classical communication (SLOCC). We argue that this approach is not exhausted with the first simple choices included herein.

arXiv:1003.3545•Mar 18, 2010•1 citation

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
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~\cite{HoogstederCalsamigliaWinter2025}. 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.
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 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.
Let K, K' be convex cones residing in finite-dimensional real vector spaces E, E'. An element in the tensor product E \otimes E' is K \otimes K'-separable if it can be represented as finite sum \sum_l x_l \otimes x'_l with x_l \in K and x_l' \in K' for all l. Let S(n), H(n), Q(n) be the spaces of n x n real symmetric, complex hermitian and quaternionic hermitian matrices, respectively. Let further S_+(n), H_+(n), Q_+(n) be the cones of positive semidefinite matrices in these spaces. If a matrix in H(mn) = H(m) \otimes H(n) is H_+(m) \otimes H_+(n)-separable, then it fulfills also the so-called PPT condition, i.e. it is positive semidefinite and has a positive semidefinite partial transpose. The same implication holds for matrices in the spaces S(m) \otimes S(n), H(m) \otimes S(n), and for m < 3 in the space Q(m) \otimes S(n). We provide a complete enumeration of all pairs (n,m) when the inverse implication is also true for each of the above spaces, i.e. the PPT condition is sufficient for separability. We also show that a matrix in Q(n) \otimes S(2) is Q_+(n) \otimes S_+(2)-separable if and only if it is positive semidefinite.
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.
Exploiting the cone structure of the set of unnormalized mixed quantum states, we offer an approach to detect separability independently of the dimensions of the subsystems. We show that any mixed quantum state can be decomposed as ρ=(1−λ)Cρ+λEρρ=(1-λ)C_ρ+λE_ρρ=(1−λ)Cρ​+λEρ​, where CρC_ρCρ​ is a separable matrix whose rank equals that of ρρρ and the rank of EρE_ρEρ​ is strictly lower than that of ρρρ. With the simple choice Cρ=M1⊗M2C_ρ=M_{1}\otimes M_{2}Cρ​=M1​⊗M2​ we have a necessary condition of separability in terms of λλλ, which is also sufficient if the rank of EρE_ρEρ​ equals 1. We give a first extension of this result to detect genuine entanglement in multipartite states and show a natural connection between the multipartite separability problem and the classification of pure states under stochastic local operations and classical communication (SLOCC). We argue that this approach is not exhausted with the first simple choices included herein.
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.