量子信息论与计算经济学中若干算法与复杂性问题研究

论文题目: 量子信息论与计算经济学中若干算法与复杂性问题研究

论文类型: 博士论文

论文专业: 计算机科学与技术

作者: 孙晓明

导师: 马少平,姚期智

关键词: 量子复杂度,量子算法,量子信息,计算经济学,通信复杂性

文献来源: 清华大学

发表年度: 2005

论文摘要: 量子信息论和计算经济学是算法和复杂性研究中两个新的热点,其中涉及的一些问题,例如量子算法下界问题,量子信息分辨问题,Nash均衡问题,拍卖定价问题等等,无论在理论上还是在实际上都具有重要的意义。在本文中,我们研究了如下五个量子信息论和计算经济学中的算法和复杂性问题:1.针对量子算法下界问题,我们证明了对于任何图性质、轮换对称函数、弱对称函数,它们的量子查询复杂度下界至少是Ω( N1/4)。同时我们还给出了Scorpion图性质和一个轮换对称函数的例子,以及它们的量子算法,复杂度是O ( N1/4)。因此Ω( N1/4)的下界是最好的。2.借助另外一个量子纠缠态的帮助,一对量子纠缠态能够实现局部操作、经典通信下的转化。这一辅助状态被称作量子纠缠催化剂。本文给出了存在2×2量子态能够催化一对4×4量子态进行转化的充分必要条件（解析表达式）;对一般的n×n的情况,我们给出了多项式时间的算法来判定能否催化转化。在我们之前[47]给出了一些必要条件,[6]提出了一个指数时间的算法。3.我们证明了量子状态的无错分辨问题在数学上等价于一个半正定规划问题,利用这一结果我们给出了一系列分辨效率的下界。4.我们推广了[29]对于Fisher市场均衡问题的研究,从线性模型推广到凹函数收益模型。我们给出了一个均衡价格下买卖双方的对偶定理,并利用对偶定理给出了买方或者卖方有界时计算均衡价格的多项式时间算法。5.我们研究了一类特殊的组合拍卖——single-minded拍卖。我们给出了匹配的通信复杂性上下界,证明了判定Walrasian均衡的存在性是NP难的,同时给出了Walrasian均衡的对偶定理。

论文目录:

第1章 绪论

1.1 理论计算机科学发展的新趋势

1.1.1 量子计算和量子信息

1.1.2 计算经济学

1.1.3 生物信息学

1.2 本文研究的主要问题

第2章 轮换对称函数的量子算法及复杂度

2.1 本章引论

2.2 预备知识

2.2.1 判定树、图的性质

2.2.2 量子黑盒模型和Grover 搜索算法

2.2.3 Abmainis 的量子下界方法

2.3 Scorpion 性质的量子算法

2.3.1 Scorpion 性质

2.3.2 (O|~)(n~(3/4)) 的量子算法

2.3.3 改进的量子算法

2.4 轮换对称函数的量子算法

2.5 轮换对称函数的量子复杂性下界

2.6 本章小结

第3章 量子状态纠缠转化和无错分辨

3.1 本章引论

3.2 预备知识

3.2.1 张量积、纠缠态

3.2.2 量子测量

3.3 量子状态的催化纠缠转化

3.3.1 纠缠转化

3.3.2 催化纠缠转化

3.3.3 n=4,k=2 的充要条件

3.3.4 寻找“催化剂”的多项式时间算法

3.4 量子状态的无错分辨

3.5 本章小结

第4章 Fisher 市场均衡价格的计算问题

4.1 本章引论

4.2 Fisher 市场均衡模型

4.3 买卖双方之间的对偶定理

4.4 均衡价格的多项式算法

4.5 本章小结

第5章 Single-Minded 拍卖的计算复杂性

5.1 本章引论

5.2 Single-Minded 拍卖模型

5.3 通信复杂性

5.4 Walrasian 均衡的计算复杂性

5.5 Walrasian 均衡的对偶定理

5.6 本章小结

第6章 结论

6.1 研究总结

6.2 需进一步开展的工作

参考文献

致谢与声明

个人简历、在学期间发表的学术论文与研究成果

发布时间: 2006-06-29

参考文献

• [1].量子信息隐藏协议设计与分析的研究[D]. 瞿治国.北京邮电大学2011
• [2].量子信息隐藏协议研究[D]. 徐淑奖.北京邮电大学2014
• [3].量子秘密共享协议的设计与信息理论分析[D]. 肖鹤玲.西安电子科技大学2013
• [4].基于量子信息技术的网络安全协议研究[D]. 马鸿洋.中国海洋大学2011
• [5].量子信息论中的投影测量研究[D]. 高晶亮.西安电子科技大学2015
• [6].量子密码协议理论研究[D]. 王剑.国防科学技术大学2007
• [7].量子通信协议设计与安全性研究[D]. 张博.国防科学技术大学2015
• [8].安全多方量子计算理论与应用研究[D]. 何立宝.中国科学技术大学2013
• [9].量子信道编码与量子密码理论研究[D]. 张权.国防科学技术大学2001
• [10].关于量子信息传输的若干问题研究[D]. 王进伟.电子科技大学2015

相关论文

• [1].分布式计算中的共识问题研究[D]. 张家琳.清华大学2010
• [2].几何量子计算和量子信息传输问题的研究[D]. 郝三如.西北大学2003
• [3].量子通信理论研究[D]. 邓富国.清华大学2004
• [4].量子通信和概率克隆在量子计算中的应用[D]. 高亭.首都师范大学2005
• [5].基于Kolmogorov复杂性的知识获取方法研究[D]. 郝宇.清华大学2005
• [6].复杂性科学的方法论研究[D]. 黄欣荣.清华大学2005
• [7].Web挖掘中的降维和分类方法研究[D]. 孙建涛.清华大学2005
• [8].量子算法和量子信息处理的核磁共振实现[D]. 彭新华.中国科学院研究生院（武汉物理与数学研究所）2003
• [9].量子信息处理中的纠缠态及其应用[D]. 李晓宇.中国科学院研究生院（计算技术研究所）2004
• [10].量子信息处理方案研究及其应用[D]. 陈清.中国科学技术大学2006

标签：量子复杂度论文;  量子算法论文;  量子信息论文;  计算经济学论文;  通信复杂性论文;