量子算法加速性差异研究及其应用

项目名称： 量子算法加速性差异研究及其应用

项目编号： No.61502041

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 自动化技术、计算机技术

项目作者： 胡滨

作者单位： 北京信息科学技术研究院

项目金额： 16万元

中文摘要： 尽管经过30多年的蓬勃发展量子算法的研究已取得丰富的成果，仍有一些关于量子计算的基本问题需要回答。这其中一个有趣的问题为：为什么有些算法，如Shor算法及其衍生算法，可以较已知最快的经典算法获得指数加速；而另一些算法，如Grover算法及其衍生算法，只能最多获得多项式加速。下述事实或许对上述问题的解释提供了一些线索：Shor类算法大多可约化为求解阿贝尔群上的某种隐藏结构；而Grover类算法大多可等效为执行对无结构数据集的搜索。结构性质优良的阿贝尔群和无结构数据集的对比暗示，量子算法的加速性或许与其背景问题的某种结构性相关。本项目将探索并量化这种结构性——通过深入研究量子测量所提取信息的全局/局域性以及中间态空间的结构特性这两个潜在影响因素，建立量化模型并分析其与量子算法加速性的内在联系。此外，本项目还将发展刻画该联系的理论并将其应用于量子加速性上界估计与紧致算法构造等实际问题中。

中文关键词： 量子加速性；结构特性；超多项式加速；全局/局域信息；量子加速性上界

英文摘要： Despite more than 30 years’ rapid growth in designing novel quantum algorithms, some fundamental questions about quantum computation are still awaiting to be answered. One particularly interesting one among them is about the gaps of quantum-speedup abilities: why Shor-like algorithms could reach exponential speedup over its classical counterpart, while Grover-like algorithms’ speedup is moderate. Noticing the following facts may shed a light on its potential explanation: Almost all Shor-like algorithms could be reduced to finding some hidden structures in highly ordered Abelian groups while in sharp contrast, Grover-like algorithms are somewhat like executing item-search in an unstructured random list. These facts implicitly indicate that the speedup abilities of a quantum algorithms are highly related with the problem structures they were sat in. Then it comes naturally to investigate what are these structures really mean, how to evaluate them and decide to what extends such structures are good or bad enough to generate an exponential、polynomial or not-at-all speedup. In this project, our goal is to give a consistent understanding of the gaps of quantum-speedup abilities of different quantum algorithms. By focusing on two relevant aspects concerning problems to be quantum-mechanically solved，i.e. the global/local information to be extracted by output measurement and the structural features of the content loaded in the register during the algorithm execution, we are going to develop a quantitative theory connecting the above features and the varies speedup abilities, a theory that could fully describe those already-known results towards quantum-speedups and could also make verifiable predictions on those unsettled issues like whether there exists super-polynomial speedup for shortest vector problem on lattice, etc. Furthermore, we are particularly concerned about how to incorporate our results to find upper bounds for certain quantum algorithms and how to construct the tight algorithms for those bounds by applying the theory we are developing.

英文关键词： quantum-speedup;structural features ;superpolynomial speedup;global/local information;quantum-speedup upper bounds