Towards Quantifying Complexity with Quantum Mechanics

Abstract

While we have intuitive notions of structure and complexity, the formalization of this intuition is non-trivial. The statistical complexity is a popular candidate. It is based on the idea that the complexity of a process can be quantified by the complexity of its simplest mathematical model - the model that requires the least past information for optimal future prediction. Here we review how such models, known as $\epsilon$-machines can be further simplified through quantum logic, and explore the resulting consequences for understanding complexity. In particular, we propose a new measure of complexity based on quantum $\epsilon$-machines. We apply this to a simple system undergoing constant thermalization. The resulting quantum measure of complexity aligns more closely with our intuition of how complexity should behave.

10 pages, 6 figure, Published in the Focus Point on Quantum information and complexity edition of EPJ Plus

References in corpus (4)

• 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
• Information-theoretic bound on the energy cost of stochastic simulation

Cited by in corpus (17)

• Monotone measures of statistical complexity
• Information geometric methods for complexity
• The classical-quantum divergence of complexity in modelling spin chains
• Causal Asymmetry in a Quantum World
• Strong and Weak Optimizations in Classical and Quantum Models of Stochastic Processes
• Robust inference of memory structure for efficient quantum modelling of stochastic processes
• Thermodynamics of Random Number Generation
• One-parameter Fisher-Rényi complexity: Notion and hydrogenic applications
• The Markov Memory for Generating Rare Events
• ToyArchitecture: Unsupervised Learning of Interpretable Models of the World
• Extreme Quantum Advantage when Simulating Strongly Coupled Classical Systems
• Quantum-embeddable stochastic matrices
• Surveying structural complexity in quantum many-body systems
• Statistical complexity and the road to equilibrium in many-body chaotic quantum systems
• Quantum-inspired identification of complex cellular automata
• Enhancing quantum models of stochastic processes with error mitigation
• Optimizing Quantum Models of Classical Channels: The reverse Holevo problem