计算机科学中若干难解问题的量子算法研究

摘要

计算机科学中难解问题是计算机算法和计算机理论界长期研究的课题,它们大都具有深刻的应用背景.量子算法是一种新的计算方法,利用量子力学的迭加和纠缠等特性进行的量子计算是计算技术的巨大飞跃,它能够比经典计算远为有效地解决一些问题.其中最为著名的Shor的算法,原则上能够以多项式的时间因了化大的合数,从而使得经典计算机难以计算的这一问题得以解决.因此研究人员可以考虑用量子计算技术来求解某些计算机科学中的NP难解问题,该文正是利用这种方法来求解某些典型的NP难解问题,并证明了这样做的确是可行和非常有效的.该文的主要贡献和创新如下:首次针对0/1背包问题和整数规划问题这一类的NP难解问题提出了相应的量子算法,证明了这两个算法在没有使用任何可以提高搜索效率的经典策略的情况下,能够在O(c2<'n/2>)步以至少1-1/2<'c>的概率求解问题规模为n的0/1背包问题和整数规划问题(c为常数),同时也指出这两个算法实际的物理可操作性.该文受到973重大基础理论研究计划和国家863计划项目的资助.

目录

文摘

英文文摘

第一章绪言

1.1物理学方法和计算的紧密结合

1.2量子计算的起源和发展

1.3算法和算法复杂性

1.4 P问题和NP问题分类

1.5量子计算机和经典计算机的比较

1.6算法的描述和分析技术

1.7论文的组织

参考文献

第二章量子信息学的量子力学基础

2.1量子运动与哥本哈根解释

2.2量子运动的测量

2.2.1第一种测量

2.2.2第二种测量

2.2.3新的测量方式

2.3量子力学的几条基本假设

2.3.1量子力学的第一条假设：量子态的描述

2.3.2量子力学的第二条假设：态叠加原理

2.3.3量子力学第三条假设：力学量的线性厄米算子的表示

2.3.4量子力学的第四条假设：测量力学量算子的取值

2.3.5幺正变换的性质和量子态的演化

2.4小结

参考文献

第三章量子计算机简介

3.1量子计算机的起源，概念及发展背景

3.2量子计算机的构造及实验方案

3.3量子计算机的应用及其与经典计算机的比较

3.4量子计算的困难及其克服方法

3.5量子计算机的未来与展望

3.6小结

参考文献

第四章典型量子算法介绍

4.1相对“黑盒”加速的一些量子算法

4.1.1 Deutchs问题的量子算法

4.1.2 Deutsch-Jozsa问题的量子算法

4.1.3 Bernstein-Vaziani问题的量子算法

4.1.4 Simon问题的量子算法

4.2 Shor大数因子分解的量子算法

4.2.1大数因子分解问题的数论基础

4.2.2求随机数阶的量子算法

4.2.3量子离散Fourier变换及其有效执行

4.2.4 Shor分解因子算法的有效性

4.3 Grover随机数据库搜索的量子算法

4.3.1随机数据库搜索问题

4.3.2搜索问题中的量子黑盒作用

4.3.3 Grover算法及其迭代

4.3.4从N中找1的具体过程

4.4小结

参考文献

第五章计算机科学中某些难解问题的量子算法

5.1引言

5.1.1 0/1-背包问题

5.1.2整数规划问题

5.2 0/1-背包问题的量子算法

5.2.1 0/1-背包问题的量子算法

5.2.2 0/1-背包问题的量子算法分析

5.3整数规划问题的量子算法

5.3.1整数规划问题的量子算法

5.3.2整数规划问题的量子算法分析

5.4小结

参考文献

第六章总结与展望

6.1本文的工作

6.2本文的主要贡献和创新

6.3进一步的研究

致谢

作者在读博士期间从事的科研项目

作者在读博士期间发表和已录用的论文

错误表