arXiv:2610.22750
The Classical Boundary of Quantum Computation: History-Resolved Causal Stochastic Machines and the Cost of Classicalization
Kyoungho Cho, Junghee Ryu, Minsu Kim, Jeongho Bang
Abstract
What separates quantum computation from classical computation when a classical model may retain every branch history and arbitrary causal memory? We study this question using history-resolved causal stochastic machines (HCSMs), which describe positive causal history laws. Probabilistic Turing machines (PTMs) embed in stochastic-ensemble models (SEnMs), which in turn embed in HCSMs. We prove that HCSM history laws coincide exactly with the fixed-basis, prefix-preserving diagonal sector of ideal quantum processes, denoted by $\mathsf{PTM}_{\rm proc}$ and distinguished here from algorithmic quantum Turing machines (QTMs). Coherent quantum processes extend strictly beyond this sector. The boundary is already visible in reversibility. Born-probability shadows of unitary gates preserve inverse composition exactly for basis permutations with phases. Outside this class, an exact positive stochastic simulation that supports universal quantum continuations must retain predictive information absent from visible probabilities. An inverse-recovery identity quantifies this phase ledger, and universal continuation forces the retained probability law to be tomographically sufficient for the quantum state. Under continuous full-state encoding assumptions, this requirement yields quantum-state dimension lower bounds. The familiar slogan $\mathsf{PTM}\subseteq\mathsf{QTM}$ is thereby sharpened into a precise classical boundary and a no-free-classicalization principle. Complete classical branching does not remove the predictive information needed to represent quantum coherence.
AI Summary
The paper asks what information a positive classical stochastic model must retain to reproduce coherent quantum composition, rather than merely final output statistics. It defines history-resolved causal stochastic machines (HCSMs), whose transition kernels may depend on the complete past, for finite horizons and finite or countable configuration spaces. Using probability-chain-rule factorization and explicit Kraus maps, it identifies HCSM history laws with fixed-basis, prefix-preserving quantum processes whose channels satisfy $\Phi=D_{\rm out}\Phi D_{\rm in}$. For a unitary’s Born shadow, $B(U)_{yx}=|U_{yx}|^2$, it shows that $B(U^\dagger)B(U)=I$ holds exactly for monomial unitaries: permutations with phases. Beyond this visible-probability description, exact inverse recovery from a retained record $(Y,Z)$ requires $I(X;Z\mid Y)=H(X\mid Y)$; approximate recovery gives a Fano-type bound. Supporting tomographically complete future continuations requires distinct reachable density matrices to have operationally distinct retained laws. Continuous full-state encodings therefore need parameter dimension at least $2^{n+1}-2$ for pure $n$-qubit states, or $4^n-1$ for mixed states. Finite-precision simulations use continuation-distance incompatibility graphs to bound deterministic predictive codebooks; for finite binary-query banks, the optimum equals the graph’s chromatic number. Numerical examples compare restricted and universal continuation requirements. The stated scope excludes complexity-class separation or impossibility of positive classical simulation with sufficient memory. The dimension bounds require continuity and full-manifold coverage, concern probability-law parameters rather than sampled-state memory, and do not follow from a countable gate orbit. Codebook index bounds assume deterministic encodings; arbitrary real kernels receive ideal-process, not necessarily effective finite-gate, realizations.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 28 pages (including Appendix), 5 figures