Quantum Kolmogorov complexity

被引：3

作者：

Berthiaume, A ^{[1
]}

van Dam, W ^{[1
]}

Laplante, S ^{[1
]}

机构：

[1] Depaul Univ, Sch CTI, Chicago, IL 60604 USA

来源：

15TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 2000年

关键词：

D O I：

10.1109/CCC.2000.856755

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 carl 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 [20] 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 ill a quantum state.

引用

页码：240 / 249

页数：10

共 23 条

[1] Stabilization of quantum computations by symmetrization [J].