Occam's Quantum Strop:
Synchronizing and Compressing Classical Cryptic Processes
via a Quantum Channel

John R. Mahoney, Cina Aghamohammdi, and James P. Crutchfield

Complexity Sciences Center
Physics Department
University of California at Davis
Davis, CA 95616

ABSTRACT: 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.


John R. Mahoney, Cina Aghamohammdi, and James P. Crutchfield, "Occam's Quantum Strop: Synchronizing and Compressing Classical Cryptic Processes via a Quantum Channel", Scientific Reports 6 (2016) 20495.
doi:10.1038/srep20495.
[pdf] 655 KB
Santa Fe Institute Working Paper 15-08-030.
arxiv.org:1508.02760 [quant-pht].