Algorithmic No-Cloning Theorem

Abstract

We introduce notions of algorithmic mutual information and deficiency of randomness of quantum states. These definitions enjoy conservation inequalities over unitary transformations and partial traces. We show that a large majority of pure states have minute self-algorithmic information. We provide an algorithmic variant to the no-cloning theorem, by showing that only a small minority of quantum pure states can clone a nonnegligible amount of algorithmic information. We also provide a chain rule inequality for quantum algorithmic entropy. We show that deficiency of randomness does not increase under POVM measurements.