2004/12/22 by C. Mora, Mora, C., H. J. Briegel +1 · 3 citations
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0412172
24 pages, no figures
arxiv created 2004/12/22 · arxiv updated 2009/12/01
In this paper we give a definition for the Kolmogorov complexity of a pure quantum state. In classical information theory the algorithmic complexity of a string is a measure of the information needed by a universal machine to reproduce the string itself. We define the complexity of a quantum state by means of the classical description complexity of an (abstract) experimental procedure that allows us to prepare the state with a given fidelity. We argue that our definition satisfies the intuitive idea of complexity as a measure of ``how difficult'' it is to prepare a state. We apply this definition to give an upper bound on the algorithmic complexity of a number of states.