Eur. Phys. J. Plus (2014) 129: 191
https://doi.org/10.1140/epjp/i2014-14191-2

Regular Article

Towards quantifying complexity with quantum mechanics

¹ Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, 117543, Singapore, Singapore
² Department of Physics and Astronomy, Macquarie University, 2109, Sydney, New South Wales, Australia
³ Department of Physics, University of Oxford, Clarendon Laboratory, OX1 3PU, Oxford, UK
⁴ Department of Physics, National University of Singapore, 2 Science Drive 3, 117551, Singapore, Singapore
⁵ 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

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 -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.