Membership in the cone of quantum states over time is NP-hard
Abstract
A state over time (stote) pairs a state ρ with a channel ℰ as the Hermitian, generally non-positive operator (ρ⊗1)⋆ JE. Characterizing the convex cone 𝒬̂ 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 𝒬̂: for output systems of the form B = A'R with A' a copy of the input, there is an explicit witness W0∈𝒬̂* and an explicit injective linear map L with σ∈ SEP+(A:R)⟺ L(σ)∈𝒬̂(A:A'R). Composing with the NP-hardness of separability shows that exact membership, weak membership, and weak optimization are NP-hard for 𝒬̂ 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. Independently of this complexity assumption, Fawzi's theorem implies that 𝒬̂(A:A'R) admits no finite semidefinite representation when d=dim A≥2, r=dim R≥2, and d+r>5.
Related
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
- A Formal Proof of Riemann Hypothesis from Existence Alone, the Sign Excepted by Theorem: The Constructed Witness, the Identity Cone over the Fixed Locus, the Grounded Counter-Model, and the Cure Theorem Proved in Lean 4 and Re-executed in Fortran
- White's cone over the Möbius band is area-minimising
- Multi-Time States in Quantum and Operational Probabilistic Theories: An Axiomatic Framework
- Variance of relative entropy over random states
BibTeX
@misc{hoogstederriera2026membership,
title = {{Membership in the cone of quantum states over time is NP-hard}},
author = {Matt Hoogsteder-Riera},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34972},
eprint = {2610.34972},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34972},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Membership in the cone of quantum states over time is NP-hard
AU - Matt Hoogsteder-Riera
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.34972
UR - https://arxiv.org/abs/2610.34972
AB - A state over time (stote) pairs a state ρ with a channel ℰ as the Hermitian, generally non-positive operator (ρ⊗1)⋆ J_E. Characterizing the convex cone 𝒬̂ 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 𝒬̂: for output systems of the form B = A'R with A' a copy of the input, there is an explicit witness W_0∈𝒬̂^* and an explicit injective linear map L with σ∈ SEP_+(A:R)⟺ L(σ)∈𝒬̂(A:A'R). Composing with the NP-hardness of separability shows that exact membership, weak membership, and weak optimization are NP-hard for 𝒬̂ 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. Independently of this complexity assumption, Fawzi's theorem implies that 𝒬̂(A:A'R) admits no finite semidefinite representation when d=dim A≥2, r=dim R≥2, and d+r>5.
ER -