Three approaches to the quantitative definition of information in an individual pure quantum state

被引:10
作者
Vitanyi, P [1 ]
机构
[1] CWI, NL-1098 SJ Amsterdam, Netherlands
来源
15TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 2000年
关键词
D O I
10.1109/CCC.2000.856757
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In analogy of classical Kolmogorov complexity we develop a theory of the algorithmic information in bits contained in any one of continuously many pure quantum states: quantum Kolmogorov complexity. Classical Kolmogorov complexity coincides with the new quantum Kolmogorov complexity restricted to the classical domain. Quantum Kolmogorov complexity is upper bounded and can be effectively approximated from above. With high probability a quantum object is incompressible. There are two alternative approaches possible: to define the complexity as the length of the shortest qubit program that effectively describes the object, and to use classical descriptions with computable real parameters.
引用
收藏
页码:263 / 270
页数:8
相关论文
共 5 条
[1]   Quantum computability [J].
Adleman, LM ;
Demarrais, J ;
Huang, MDA .
SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1524-1540
[2]   Quantum complexity theory [J].
Bernstein, E ;
Vazirani, U .
SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1411-1473
[3]  
Gacs P., 1994, Proceedings. Workshop on Physics and Computation PhysComp '94, P209, DOI 10.1109/PHYCMP.1994.363679
[4]  
LI M, 1997, INTRO KOLMOGOROV COM
[5]  
Peres A., 1995, QUANTUM THEORY CONCE