Quantum Kolmogorov Complexity

Simple item page
dc.creatorBerthiaume, Andre
dc.creatorvan Dam, Wim
dc.creatorLaplante, Sophie
dc.date2000-05-03
dc.date.accessioned2026-07-07T05:59:55Z
dc.date.available2026-07-07T05:59:55Z
dc.descriptionIn 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.
dc.description14 pages, LaTeX2e, no figures, \usepackage{amssymb,a4wide}. To appear in the Proceedings of the 15th IEEE Annual Conference on Computational Complexity
dc.identifierhttps://arxiv.org/abs/quant-ph/0005018
dc.identifierhttp://arxiv.org/abs/quant-ph/0005018
dc.identifierJournal of Computer and Systems Sciences, Volume 63, No. 2, September 2001, pages 201-221
dc.identifierdoi:10.1006/jcss.2001.1765
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/88863
dc.subjectQuantum Physics
dc.titleQuantum Kolmogorov Complexity
dc.typetext

Files

Collections

arXiv