Complexity in Dynamics and Computation

被引：0
作者：
Masanori Ohya
机构：
[1] Science University of Tokyo,Department of Information Sciences
来源：
Acta Applicandae Mathematica | 2000年 / 63卷
关键词：
complexity; information dynamics; chaos degree; SAT problem; quantum algorithm;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
A new description of chaos in both classical and quantum dynamical systems is discussed in the context of information dynamics, which is called the chaos degree. The algorithm computing this degree is shown. Quantum algorithm solving the SAT problem, on of the NP complete problems, is studied and it is discussed that the SAT problem can be solved in polynomial time when a certain mixture of two orthogonal vectors is physically detected.
引用
收藏
页码：293 / 306
页数：13
相关论文
共 50 条
[1]  
Accardi L.(1999)Compound channels, transition expectations and liftings Appl. Math. Optim. 39 33-59
[2]  
Ohya M.(1997)Dynamical entropy through Markov chain Open Systems Inform. Dynam. 4 71-87
[3]  
Accardi L.(1996)Note on quantum dynamical entropy Rep. Math. Phys. 38 457-469
[4]  
Ohya M.(1990)The asymptotic behavior of J. Math. Anal. Appl 153 250-257
[5]  
Watanabe N.(1976)-entropy of a compact positive operator Publ. RIMS Kyoto Univ. 11 809-833
[6]  
Accardi L.(1987)Relative entropy for states of von Neumann algebras Comm. Math. Phys. 112 691-719
[7]  
Ohya M.(1975)Dynamical entropy of C*-algebras and von Neumann algebras Acta Math 134 289-306
[8]  
Watanabe N.(1985)Entropy for automorphisms of II1 von Neumann algebras Proc. Royal Soc. London A 400 97-117
[9]  
Akashi S.(1992)Quantum theory, the Church–Turing principle and the universal quantum computer Proc. Royal Soc. London A 439 553-558
[10]  
Araki H.(1996)Rapid solution of problems by quantum computation Rev. Modern Phys 68 733-753
12345