Using quantum theory to reduce the complexity of input-output processes

Abstract

All natural things process and transform information. They receive environmental information as input, and transform it into appropriate output responses. Much of science is dedicated to building models of such systems -- algorithmic abstractions of their input-output behavior that allow us to simulate how such systems can behave in the future, conditioned on what has transpired in the past. Here, we show that classical models cannot avoid inefficiency -- storing past information that is unnecessary for correct future simulation. We construct quantum models that mitigate this waste, whenever it is physically possible to do so. This suggests that the complexity of general input-output processes depends fundamentally on what sort of information theory we use to describe them.

10 pages, 5 figures

References in corpus (13)

• The classical-quantum boundary for correlations: discord and related measures
• Bound states of spatially dependent mass Dirac equation with the Eckart potential including Coulomb tensor interaction
• Device-independent tests of classical and quantum dimensions
• Experimental Device-independent Tests of Classical and Quantum Dimensions
• Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
• Memory cost of quantum contextuality
• Computational Mechanics of Input-Output Processes: Structured transformations and the $\epsilon$-transducer
• Complexity analysis of the stock market
• Provable Quantum Advantage in Randomness Processing
• Thermodynamical cost of some interpretations of quantum theory
• Communication tasks with infinite quantum-classical separation
• Experimental Quantum Randomness Processing
• Information-theoretic bound on the energy cost of stochastic simulation

Cited by in corpus (28)

• Quantum stochastic processes and quantum non-Markovian phenomena
• Kolmogorov extension theorem for (quantum) causal modelling and general probabilistic theories
• A practical, unitary simulator for non-Markovian complex processes
• Extreme dimensionality reduction with quantum modelling
• Optimal stochastic modelling with unitary quantum dynamics
• Optimal classical simulation of state-independent quantum contextuality
• Resource theories of multi-time processes: A window into quantum non-Markovianity
• Thermodynamics of complexity and pattern manipulation
• Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes
• The classical-quantum divergence of complexity in modelling spin chains
• Causal Asymmetry in a Quantum World
• Non-Markovian quantum control as coherent stochastic trajectories
• Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models
• Quantum Cognitive Triad. Semantic geometry of context representation
• Single-shot quantum memory advantage in the simulation of stochastic processes
• Contextuality and The Single-Qubit Stabilizer Formalism
• Quantum adaptive agents with efficient long-term memories
• 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
• Quantum Uncertainty Principles for Measurements with Interventions
• An Experimental Quantum Bernoulli Factory
• Quantum Causal Unravelling
• Quantum coarse-graining for extreme dimension reduction in modelling stochastic temporal dynamics
• Surveying structural complexity in quantum many-body systems
• Error-tolerant witnessing of divergences in classical and quantum statistical complexity
• The fundamental thermodynamic bounds on finite models
• Energetic advantages for quantum agents in online execution of complex strategies