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

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.

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

本课题针对量子与经典计算比较和分析问题，通过引入抽象的计算主体并逐层继承的方法构建了对量子与经典算法/协议/设备统一的表达范式。基于该表达范式，本课题建立了针对计算主体及计算主体间交互运算的统一分析框架。本课题给出了该分析框架的完整软、硬件实现，并为该框架的主要功能开发了图形用户界面。为了能够获取量子计算中间态等量子计算特性分析的必要数据，以及大规模积累量子算法样本和运行数据，本课题通过继承前述计算主体并对量子计算与经典计算的差异加以分析，给出了在经典计算机上模拟量子叠加态和量子纠缠以及施加多量子门的方法，并开发了与统一分析框架兼容的模拟量子计算机。该模拟机包含模拟量子态、量子门等主体模块,并提供了设定不同退相干过程的接口。本课题为该量子模拟计算机设计了涵盖量子线路设计、运行结果可视化、统计、存储等功能的人机交互界面。