中山大学教授李绿周：容错率并非前置因素，一次查询精确量子算法

当前，以量子信息科学为代表的量子科技正在不断形成新的科学前沿，激发革命性的科技创新，孕育对人类社会产生巨大影响的颠覆性技术。量子信息科技的具体应用包括量子通信、量子计算和量子精密测量三方面。量子计算具有强大的并行计算和模拟能力，可为人工智能、密码分析、气象预报等所需的大规模计算难题提供解决方案。总体来看，我国在量子计算方面与发达国家处于同一水平线。我国量子领域在量子计算方面未来10到15年的发展目标是确立和巩固我国在全球第一方阵的地位，有效解决大尺度量子系统的效率问题，研制对特定问题的求解能力全面超越经典超级计算机的专用量子模拟机，并为最终实现通用量子计算机探索出一条切实可行的道路。日前，在由中国科学院物理研究所和量子计算研究中心主办、中国科学院物理研究所学术服务部协办的“量子计算及量子信息研讨会”上，中山大学李绿周教授作了题为《什么样的问题可以被一次查询精确量子算法解决？》的报告，探讨了一次查询精确量子算法解决以及量子计算与经典计算的差别与优势。什么叫做一次查询精确量子算法解决？该量子算法只执行一次查询操作，要求这一算法精确解决问题，没有出错概率，“这种情况下，它可能比经典算法有优势”李绿周教授表示。像我们所知道的常规的Shor算法、Gover算法都是有出错概率的。这个问题很简单，但到现在还未完全解决。探寻量子计算优势为什么会关注量子计算，量子计算对比经典计算，其优势在哪里？针对哪些工作、哪一方面？量子计算速度更快、更好，那么它是怎么更快、怎么更好？度量量子计算与经典计算差别的角度有很多，李绿周教授主要从查询复杂度方面分析了量子计算与经典计算的差别以及其优势所在。·通过基本量子酉变换可以构建一些特定的量子算法。有了高效的量子算法，量子计算机的并行计算就可以充分发挥其优势。量子经典模型为什么讨论这一模型？查询模型意义何在？·查询模型本质上是只关注某个子过程的调用次数，而不关心其内部结构。·查询模型具有现实意义：例如，在执行摸个计算任务时，我们可能只关心读取外存的次数，而不是在意外存内部的运行机制。·查询模型为度量复杂性提供了一个便利的视角：时间复杂度下界难以刻画或衡量（如P与NP的关系），二查询复杂度通常有系统的度量方法。·经典与量子计算二者计算能力的比较很多时候是从查询复杂度角度进行考量。比如Deutsch-Jozsa算法，Simon算法，Grover算法都是从查询复杂度方面去体现这一点。量子查询模型量子查询算法通过研究得出，经典情况下，一次只能查询一位；量子情况下，一次可以以叠加形式查询。其次，著名的Deutsch-Jozsa算法就是一次查询精确量子算法。那么，能否找到更多的问题可以被一次查询精确量子算法解决？除此之外，一次查询的有界误差量子算法得到了一些研究，但是结果对精确量子不适用。关于精确量子算法的意义，有观点认为“容忍出错概率才换来了算法的提速”，精确量子算法对此事很好的反驳，体现了概率算法的区别。精确这个词的说法体现了量子与概率从某种程度上的区别。什么样的函数可以被一次查询的量子算法精确计算？基于实验研究，得出三种结果：·对全函数的刻画；·部分函数方面，得到了一些充分必要条件的初步的结果；·基于等价条件，构建了新的可被一次查询量子算法精确计算的函数。上面提及的新的函数包含两类，它们都不是对称函数，据了解，之前所有的函数能被一次查询量子算法精确计算的函数都是对称函数。新的非对称函数目前还没有应用价值。附：Shor算法1994年，Shor提出因子分解的量子算法。该算法的基本思想是，首先通过量子并行性通过一步计算获得所有函数值，然后通过测量函数得到相关联的函数自变量的叠加态，并对其进行量子快速傅里叶变换，亦即将大数质因子分解转化为用QFFT在多项式步骤内完成的一个函数的周期问题。Gover算法1996年，贝尔实验室Gover提出。对于N个苑苏的数据库，用传统计算机平均要尝试N/2次才能成功，而用量子计算机辅以Grover算法不需要超过√N次。在很N大时，速度的优越性非常明显。这是因为量子计算机将N数据库的个被搜索的对象叠加为Hilbert空间中的个态，要搜索的态只是其中的一个分量。度量角度·时间复杂度，关注所耗费时间，如Shor算法；·查询复杂度，关注调用某一子过程的次数，如Gover算法，有根号的提速；·通信复杂度，关注双方协同完成某一任务时用了多少通信量；·电路深度复杂性，关注逻辑门、并行运行时间问题，如Science2018的工作，严格地证明了有一个问题量子的用常量深度电路就可以解决，但经典常量深度电路无法解决；·状态复杂度，关注一个状态变迁系统涉及到多少个状态，状态越少，系统越简单；·样本复杂度，关注学习某一目标函数需要多少样本。