Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization

Abstract:The chronological shared realization complexity (CRC) is the smallest normalized stochastic state dimension $C_{\rm seq}$ needed to reproduce a collection of future-response menus using one shared family of controlled transition dynamics. We focus on the rank-tight regime in which both the local realization dimension and the independent-query static carrier width equal $K$, thereby isolating the additional dimensional and computational constraints imposed by chronological consistency. This framework also serves as the classical baseline for state-dimension bounds in sequential quantum processes, where stochastic dynamics generalize to completely positive maps. We establish three results in this regime. First, an explicit payload--delay family exhibits an unbounded multiplicative state blow-up: $C_{\rm loc}=C_{\rm stat}=k$ while $C_{\rm seq}=k(L+1)$, isolating the intrinsic state cost of shared temporal pullbacks. Second, for explicitly listed rational finite menus over a fixed five-letter alphabet with a single Boolean terminal effect, exact shared realizability is $\exists\mathbb{R}$-complete, and the zero-versus-inverse-polynomial defect promise problem is $\mathsf{PromiseNP}$-complete, with local and static optima fixed at $K$. Third, a total five-letter chronology compiler translates bounded-rational Intermediate Simplex instances into a polynomially specified regular geometric family over the same fixed alphabet, preserving exact local and static width $K$. The compiled family yields strong $\mathsf{PromiseNP}$-hardness for shared realization on strongly bounded-rational inputs, together with an $\exists\mathbb{R}$ upper bound certified by an exact polynomial-size finite core. Together, these results show that exact local and static optimality need not compose under chronological sharing, even in the rank-tight regime.

arXiv:2609.19707 [quant-ph]

(or arXiv:2609.19707v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.19707 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.