A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression

Abstract

The causal structure of a stochastic process can be more efficiently transmitted via a quantum channel than a classical one, an advantage that increases with codeword length. While previously difficult to compute, we express the quantum advantage in closed form using spectral decomposition, leading to direct computation of the quantum communication cost at all encoding lengths, including infinite. This makes clear how finite-codeword compression is controlled by the classical process' cryptic order and allows us to analyze structure within the length-asymptotic regime of infinite-cryptic order (and infinite Markov order) processes.

21 pages, 13 figures; http://csc.ucdavis.edu/~cmg/compmech/pubs/eqc.htm

References in corpus (2)

• Experimental quantum processing enhancement in modelling stochastic processes
• The classical-quantum divergence of complexity in modelling spin chains

Cited by in corpus (27)

• A practical, unitary simulator for non-Markovian complex processes
• Extreme dimensionality reduction with quantum modelling
• Optimal stochastic modelling with unitary quantum dynamics
• Extreme Quantum Advantage for Rare-Event Sampling
• Thermodynamics of complexity and pattern manipulation
• Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes
• Unbounded memory advantage in stochastic simulation using quantum mechanics
• The classical-quantum divergence of complexity in modelling spin chains
• Matrix Product States for Quantum Stochastic Modelling
• Causal Asymmetry in a Quantum World
• Strong and Weak Optimizations in Classical and Quantum Models of Stochastic Processes
• Single-shot quantum memory advantage in the simulation of stochastic processes
• Memory-efficient tracking of complex temporal and symbolic dynamics with quantum simulators
• Thermal Efficiency of Quantum Memory Compression
• Robust inference of memory structure for efficient quantum modelling of stochastic processes
• Fraudulent White Noise: Flat power spectra belie arbitrarily complex processes
• Thermodynamics of Random Number Generation
• Measurement-Induced Randomness and Structure in Controlled Qubit Processes
• The Markov Memory for Generating Rare Events
• Extreme Quantum Advantage when Simulating Strongly Coupled Classical Systems
• The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications
• Quantum Statistical Complexity Measure as a Signalling of Correlation Transitions
• Optimality and Complexity in Measured Quantum-State Stochastic Processes
• The Ambiguity of Simplicity
• Optimizing Quantum Models of Classical Channels: The reverse Holevo problem
• Ideal stochastic process modeling with post-quantum quasiprobabilistic theories
• Quantum Dimension Reduction of Hidden Markov Models