题目：量子算法的一些进展
报告人：龙桂鲁
时间：1月7日，09:00-09:45
地点：格物楼522学术报告厅
摘要：量子计算中利用量子平行能力，具有了经典计算没有的计算能力，实现了量子体系的模拟、大数分解和无序数据库搜索的显著加速。但是这些量子算法之后，没有更多的量子算法出现，以至于2003年Shor问了为什么没有更多的量子算法出现这一问题。他把这一问题的原因归结为“量子计算机的运行与经典计算的运行如此不同，以至于经典算法中的构造设计技巧和直觉在量子计算过程中不再成立（Quantum computers operate in a manner so differently from classical computers that our techniques for designing algorithms and our intuitions for understanding the computation process no longer works.）”。2009年以后情况有了一定的改善。2009年，Harrow等人给出了一个线性方程组的高效量子算法，对于一些特殊的线性方程组，可以比经典算法有指数加速。2012年Childs和Wiebe给出了一个哈密顿体系的模拟算法，其模拟精度达到当时的最优。2015年，Berry，Childs，Cleve，Kothari，Somma等澳大利亚、加拿大、美国的联合研究组给出了一个量子模拟算法，其精度达到了指数提高。简单地说，量子计算中只能用到酉算符的乘积（或者相除），而不能用到加和减的操作。2002年提出的对偶量子计算中不仅允许酉算符的乘积，而且允许使用酉算法的线性叠加，这样就可以将经典计算和量子计算联系起来，把一些经典计算中行之有效的方法用于量子算法的构造。数学家Gudder已经严格证明，对偶量子计算可以构造任意线性有界算符。上面所提到的三个算法都使用了酉算法的线性叠加，是对偶量子计算算法.
