https://doi.org/10.1140/epjp/i2014-14191-2
Regular Article
Towards quantifying complexity with quantum mechanics
1
Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, 117543, Singapore, Singapore
2
Department of Physics and Astronomy, Macquarie University, 2109, Sydney, New South Wales, Australia
3
Department of Physics, University of Oxford, Clarendon Laboratory, OX1 3PU, Oxford, UK
4
Department of Physics, National University of Singapore, 2 Science Drive 3, 117551, Singapore, Singapore
5
Centre for Quantum Information, Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
* e-mail: thompson.jayne2@gmail.com
Received:
29
March
2014
Revised:
22
June
2014
Accepted:
21
July
2014
Published online:
11
September
2014
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 
-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 -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.
© Società Italiana di Fisica and Springer-Verlag Berlin Heidelberg, 2014
