Occam's Quantum Strop: Synchronizing and Compressing Classical Cryptic Processes via a
- Author(s): Mahoney, J. R.;
- Aghamohammadi, C.;
- Crutchfield, J. P.
- et al.
Published Web Locationhttps://arxiv.org/pdf/1508.02760.pdf
A stochastic process's statistical complexity stands out as a fundamental property: the minimum information required to synchronize one process generator to another. How much information is required, though, when synchronizing over a quantum channel? Recent work demonstrated that representing causal similarity as quantum state-indistinguishability provides a quantum advantage. We generalize this to synchronization and offer a sequence of constructions that exploit extended causal structures, finding substantial increase of the quantum advantage. We demonstrate that maximum compression is determined by the process's cryptic order---a classical, topological property closely allied to Markov order, itself a measure of historical dependence. We introduce an efficient algorithm that computes the quantum advantage and close noting that the advantage comes at a cost---one trades off prediction for generation complexity.