arXiv:2610.34972
Membership in the cone of quantum states over time is NP-hard
Matt Hoogsteder-Riera
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.
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