Quantum Kolmogorov Complexity

Details Quantum Kolmogorov Complexity Quantum Kolmogorov Complexity

2000-05-03

arxiv.org/abs/quant-ph/0005018v1

Journal of Computer and Systems Sciences, Volume 63, No. 2, September 2001, pages 201-221

Physics

Quantum Physics

14 pages, LaTeX2e, no figures, \usepackage{amssymb,a4wide}. To appear in the Proceedings of the 15th IEEE Annual Conference on

Scientific paper

10.1006/jcss.2001.1765

In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as the length of the shortest quantum input to a universal quantum Turing machine that produces the initial qubit string with high fidelity. The definition of Vitanyi (Proceedings of the 15th IEEE Annual Conference on Computational Complexity, 2000) measures the amount of classical information, whereas we consider the amount of quantum information in a qubit string. We argue that our definition is natural and is an accurate representation of the amount of quantum information contained in a quantum state.

Affiliated with

Also associated with

No associations

Rating

Quantum Kolmogorov Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Kolmogorov Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Kolmogorov Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-231307