量子马氏链与马氏决策过程的可达性分析

发布时间：2017-03-17 15:03

  本文关键词：量子马氏链与马氏决策过程的可达性分析，由笔耕文化传播整理发布。

【摘要】：经典确定性系统、随机系统的模型检验具有十分重要的意义。在模型检验中,不同种类的可达性定性、定量分析与系统的成功率、安全性、存活性、死锁检验具有十分紧密的联系。因此,可达性分析具有十分重要的地位。量子系统的模型检验同样具有十分重要的意义。其中,可达性分析不仅可以用于验证量子算法、协议的正确性,还可以应用于检验量子设备是否按设计运行。本文主要研究了量子马尔可夫链可达性的定量分析问题与量子马尔可夫决策过程的可达性问题。量子马尔可夫链作为经典马尔可夫链的量子扩展,可以用来刻画已有的大部分量子算法、协议。本文首先扩展量子底层强连通分支的概念,研究其性质以及与经典强连通分支的差异。然后依据这些性质,将量子马尔可夫链的状态空间分解。而后,结合超算子的基本性质,系统解决了量子马尔可夫链可达性、持续可达性、重复可达性的定量分析问题。量子马尔可夫决策过程是经典马尔可夫决策过程的扩展,能够有效刻画大部分离散时间量子系统。本文首先分析了量子马尔可夫决策过程与经典马尔可夫过程、量子马尔可夫链的异同点。而后,给出了其可达性分析中有限步问题的不可判定性。接着,在无限步问题中,证明了一般可达概率的不可计算性,给出了可达概率为1的最优调度程序存在的充分必要条件。最后,给出了量子马尔可夫决策过程可达性分析与联合谱半径、经典系统绝对渐近稳定性之间的关系。
【关键词】：可达性分析 量子马尔可夫链 量子马尔可夫决策过程 模型检验
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O211.62
【目录】：

• 摘要3-4
• abstract4-8
• 第1章 绪论8-14
• 1.1 问题背景及意义8-11
• 1.2 工作小结11-12
• 1.3 相关工作12-13
• 1.4 论文结构13-14
• 第2章 背景知识14-25
• 2.1 经典马氏链与马氏决策过程14-21
• 2.1.1 经典马氏链14-16
• 2.1.2 可达性、持续可达性、重复可达性16-18
• 2.1.3 底层强连通分支及可达性定量分析18-19
• 2.1.4 马氏决策过程及其可达性分析19-21
• 2.2 量子信息与量子计算基础知识21-23
• 2.3 计算复杂性与可判定性23-25
• 第3章 量子马氏链的可达概率分析25-51
• 3.1 量子马氏链与其图结构25-28
• 3.1.1 基本性质与符号25-28
• 3.2 量子马氏链28
• 3.3 量子马氏链的图结构28-30
• 3.4 底层强连通分支30-41
• 3.4.1 基本定义31-33
• 3.4.2 底层强连通分支的刻画33-35
• 3.4.3 底层强连通分支的验证35
• 3.4.4 量子状态空间的分解35-41
• 3.5 可达概率41-45
• 3.6 重复可达概率与持续可达概率45-50
• 3.7 本章小结50-51
• 第4章 量子马氏决策过程的可达性分析51-80
• 4.1 定义与基本性质51-60
• 4.1.1 量子马氏决策过程的定义51-52
• 4.1.2 （公共）不变子空间52-53
• 4.1.3 可达概率53-54
• 4.1.4 与经典马氏决策过程之间的区别54-55
• 4.1.5 与量子马氏链之间的差别55-56
• 4.1.6 量子算法与协议的模型56-59
• 4.1.7 一个并行量子程序59-60
• 4.2 有限步问题上的结果60-63
• 4.3 无限步问题上的可达性分析63-75
• 4.4 与联合谱半径的关系75-79
• 4.5 本章小结79-80
• 第5章 无后效性讨论80-82
• 第6章 量子游走的去测量化82-92
• 6.1 背景知识82-84
• 6.1.1 基本定义82-83
• 6.1.2 击中时83-84
• 6.1.3 振幅扩大法84
• 6.2 量子游走的去测量化84-86
• 6.2.1 方法设计84-85
• 6.2.2 状态演化85-86
• 6.3 应用与讨论86-91
• 6.3.1 加速量子游走86-87
• 6.3.2 加速已有算法、量子系统87-88
• 6.3.3 开发新算法88-89
• 6.3.4 抗干扰性89-91
• 6.3.5 讨论91
• 6.4 例3.3的可达性91
• 6.5 本章小结91-92
• 第7章 结论92-95
• 7.1 困难与创造性92
• 7.2 意义92-93
• 7.3 展望93-95
• 参考文献95-100
• 致谢100-102
• 附录A 经典马氏决策过程可达性问题的可判定性102-103
• 附录B 定理3.1的第二证明103-104
• 附录C 第6章补充104-107
• C.1 Oracle与时间花费104
• C.2 定理及引理的证明104-107
• 个人简历、在学期间发表的学术论文与研究成果107

【相似文献】

中国期刊全文数据库 前10条

1 秦佩恒;武剑峰;刘雅琴;曾辉;;快速城市化地区景观可达性及其对林地的影响——以深圳市宝安区为例[J];生态学报;2006年11期

2 方志祥;李清泉;萧世伦;;利用时间地理进行位置相关的时空可达性表达[J];武汉大学学报(信息科学版);2010年09期

3 张丽萍;侯卫生;杨志军;吴文龙;梁榕;刘小雨;;应急道路可达性模型改进的研究[J];测绘科学;2012年04期

4 曹U，

本文编号：253039