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.

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

References in corpus (11)

• Computational Mechanics: Pattern and Prediction, Structure and Simplicity
• Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
• Time's Barbed Arrow: Irreversibility, Crypticity, and Stored Information
• Prediction, Retrodiction, and The Amount of Information Stored in the Present
• Distinguishability of States and von Neumann Entropy
• Experimental quantum processing enhancement in modelling stochastic processes
• Many Roads to Synchrony: Natural Time Scales and Their Algorithms
• Synchronization and Control in Intrinsic and Designed Computation: An Information-Theoretic Analysis of Competing Models of Stochastic Computation
• The classical-quantum divergence of complexity in modelling spin chains
• How Hidden are Hidden Processes? A Primer on Crypticity and Entropy Convergence
• Equality conditions for internal entropies of certain classical and quantum models

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