The Classical Boundary of Quantum Computation: History-Resolved Causal Stochastic Machines and the Cost of Classicalization
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 PTMproc 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 PTM⊆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.
Related
- HTM: A Hybrid Classical-Quantum Computation Model
- Classical Algorithms for Function Computation in Gaussian Boson Sampling
- The Breakdown of Classical Minicrypt Equivalences in the Quantum-Computation Classical-Communication Model
- QRecoupling.jl: numerical and exact computation of classical and quantum recoupling coefficients
- Generators of stability-preserving semigroups, spectral gaps, and classical ground-state computation
BibTeX
@misc{cho2026classical,
title = {{The Classical Boundary of Quantum Computation: History-Resolved Causal Stochastic Machines and the Cost of Classicalization}},
author = {Kyoungho Cho and Junghee Ryu and Minsu Kim and Jeongho Bang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22750},
eprint = {2610.22750},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22750},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - The Classical Boundary of Quantum Computation: History-Resolved Causal Stochastic Machines and the Cost of Classicalization
AU - Kyoungho Cho
AU - Junghee Ryu
AU - Minsu Kim
AU - Jeongho Bang
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.22750
UR - https://arxiv.org/abs/2610.22750
AB - 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 PTM_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 PTM⊆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.
ER -