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

Abstract

A state over time (stote) pairs a state $\rho$ with a channel $\mathcal{E}$ as the Hermitian, generally non-positive operator $(\rho\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 $\sigma\in \mathrm{SEP}_{+}(A{:}R)\iff L(\sigma)\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$.