Memory-efficient tracking of complex temporal and symbolic dynamics with quantum simulators

Abstract

Tracking the behaviour of stochastic systems is a crucial task in the statistical sciences. It has recently been shown that quantum models can faithfully simulate such processes whilst retaining less information about the past behaviour of the system than the optimal classical models. We extend these results to general temporal and symbolic dynamics. Our systematic protocol for quantum model construction relies only on an elementary description of the dynamics of the process. This circumvents restrictions on corresponding classical construction protocols, and allows for a broader range of processes to be modelled efficiently. We illustrate our method with an example exhibiting an apparent unbounded memory advantage of the quantum model compared to its optimal classical counterpart.

arXiv comment15 pages, 5 figures

References in corpus (19)

• Computational Mechanics: Pattern and Prediction, Structure and Simplicity
• Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
• Statistical Complexity of Simple 1D Spin Systems
• A practical, unitary simulator for non-Markovian complex processes
• The Computational Structure of Spike Trains
• Computational Mechanics of Input-Output Processes: Structured transformations and the $\epsilon$-transducer
• Experimental quantum processing enhancement in modelling stochastic processes
• Inferring hidden Markov models from noisy time sequences: a method to alleviate degeneracy in molecular dynamics
• Complexity analysis of the stock market
• A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression
• The application of computational mechanics to the analysis of geomagnetic data
• Informational and Causal Architecture of Discrete-Time Renewal Processes
• Using quantum theory to reduce the complexity of input-output processes
• Informational and Causal Architecture of Continuous-time Renewal and Hidden Semi-Markov Processes
• Extreme Quantum Advantage for Rare-Event Sampling
• 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
• Structure and Randomness of Continuous-Time Discrete-Event Processes

Cited by in corpus (12)

• Extreme dimensionality reduction with quantum modelling
• Optimal stochastic modelling with unitary quantum dynamics
• Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models
• Quantum adaptive agents with efficient long-term memories
• Robust inference of memory structure for efficient quantum modelling of stochastic processes
• Quantum coarse-graining for extreme dimension reduction in modelling stochastic temporal dynamics
• Quantum Encoding and Analysis on Continuous Time Stochastic Process with Financial Applications
• Measures of distinguishability between stochastic processes
• Embedding memory-efficient stochastic simulators as quantum trajectories
• Surveying structural complexity in quantum many-body systems
• Quantum-inspired identification of complex cellular automata
• Quantum Dimension Reduction of Hidden Markov Models