Accuracy vs Memory Advantage in the Quantum Simulation of Stochastic Processes
arXiv:2312.13473 · doi:10.1088/2632-2153/ad444a
Abstract
Many inference scenarios rely on extracting relevant information from known data in order to make future predictions. When the underlying stochastic process satisfies certain assumptions, there is a direct mapping between its exact classical and quantum simulators, with the latter asymptotically using less memory. Here we focus on studying whether such quantum advantage persists when those assumptions are not satisfied, and the model is doomed to have imperfect accuracy. By studying the trade-off between accuracy and memory requirements, we show that quantum models can reach the same accuracy with less memory, or alternatively, better accuracy with the same memory. Finally, we discuss the implications of this result for learning tasks.
References in corpus (23)
- The density-matrix renormalization group in the age of matrix product states
- Entanglement renormalization
- On quantum Renyi entropies: a new generalization and some properties
- The iTEBD algorithm beyond unitary evolution
- Computational Mechanics: Pattern and Prediction, Structure and Simplicity
- Generalization in Quantum Machine Learning: a Quantum Information Perspective
- Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
- Statistical Complexity of Simple 1D Spin Systems
- Mid-circuit cavity measurement in a neutral atom array
- An Algorithm for Pattern Discovery in Time Series
- Fast quantum circuit cutting with randomized measurements
- Formal Algorithms for Transformers
- Extreme dimensionality reduction with quantum modelling
- Optimization and learning of quantum programs
- Convex optimization of programmable quantum computers
- Informational and Causal Architecture of Continuous-time Renewal and Hidden Semi-Markov Processes
- Matrix Product States for Quantum Stochastic Modelling
- Memory compression and thermal efficiency of quantum implementations of non-deterministic hidden Markov models
- Statistical Complexity of Quantum Learning
- Uhlmann fidelities from tensor networks
- Quantum coarse-graining for extreme dimension reduction in modelling stochastic temporal dynamics
- Equivalence of History and Generator Epsilon-Machines
- Information-Theoretic Reduction of Markov Chains