由中山大学李绿周、北京邮电大学高飞、南京大学姚鹏晖、中科院计算所田国敬等几位老师及相关团队成员（北邮潘世杰，中大何键浩、叶泽坤）共同撰写的《CCF2019-2020中国计算机科学技术发展报告》之题为“量子算法与复杂性研究进展概述”的章节近日正式出版。虽然纰漏难免，但愿如文中所言“希望本文能够让更多计算机、 物理、数学等相关领域的研究人员更好地了解量子计算理论方面的进展，借此也呼吁更多的学者和青年学生加入这个极具挑战性的研究领域"
以下摘录引言部分，全文初稿见附件。如果成为CCF会员，可在中国计算机学会（CCF）官网访问机械工业出版社正式出版的电子版全文以及更多丰富的学术资源。
引用文章内容请标注：
李绿周，高飞，姚鹏晖，田国敬，何键浩，潘世杰，叶泽坤，量子算法与复杂性研究进展概述，CCF2019-2020中国计算机科学技术发展报告/ 中国计算机学会编，p. 1-59，机械工业出版社，2020.10.
毋庸置疑，量子计算作为一种颠覆性技术已经引起了各界的广泛关注。然而需指出是，就可计算性而言量子计算并没有超越经典计算，但就计算复杂性来说量子计算展现出巨大的优势。例如，Shor量子算法可以在多项式时间内解决大数因子分解问题，从而在理论上对现代密码造成了极大威胁。量子计算相对于经典计算在哪些方面有优势？有多大程度的优势？这些问题都远未搞清楚，需要持续深入地研究。相比于广阔的未知领域，目前能展现量子计算优势的例证不是太多，而是太少。探寻量子优势是量子计算研究的核心问题之一，有待广大研究者去发现新的大陆。
从理论计算机科学的角度来看，至少可以从以下一些不同的视角来探寻量子计算的优势：
查询复杂性。关注计算过程调用某一子过程的次数，而忽略其他计算代价。目前量子计算相对于经典计算的优势很多时候是通过查询复杂度得以体现，例如著名的Grover算法。这方面有一套比较系统的分析查询复杂度上下界的方法，并且量子计算的优势可以从查询复杂性角度得以严格证明。
交互计算复杂性。 关注多个计算个体协同完成某一个任务，由于信息不完备或者计算个体不可靠而产生的复杂性现象，包括交互式证明系统和通信复杂性。量子计算在这个模型中有着独特的优势。这方面目前已经取得了一系列重要成果。
时间复杂性。关注计算过程所耗费的时间，如Shor算法就在时间复杂度上展示出相对于目前最好的经典算法的优势。不过，从时间复杂性的角度目前暂时无法严格证明量子计算对于经典计算的优势，这与计算复杂性领域的重大理论问题P是否等于NP紧密相关。尽管如此，这并不妨碍开展量子计算研究，因为发现比目前最好的经典算法更好的量子算法总是一件振奋人心的事情。
样本复杂性。关注在学习某一个目标函数的过程中需要用到多少样本数据，这是学习理论领域研究的重要问题。近几年研究人员初步考虑了量子学习理论方面的问题，主要是通过比较量子样本复杂性与经典样本复杂性来刻画量子计算的优势。总的来说，量子计算在这方面的研究有待加强。
电路深度复杂性。关注逻辑电路中逻辑门的层数，即如何尽可能并行化地完成计算。量子计算相对于经典计算的优势可以在电路深度复杂性方面得以展示，例如最近Science上就有工作表明：存在计算问题能被常数深度的量子电路解决，而任意常数深度的经典电路不可能以高成功概率解决。
除此之外，还可以考虑有限自动机(状态变迁系统)的状态复杂性，这方面早就有研究成果表明：量子有限自动机相对于经典自动机在状态复杂性方面可以有指数性优势，有兴趣的读者可参考文献[1][2][3]，本文不对此进行详细介绍。
本报告主要集中关注与以上五个方面相关的量子计算理论的研究进展。同时必须要指出的是，无论从哪个角度来展示量子计算优势，都离不开量子算法，因为要说明量子计算有优势，通常需要设计一个量子算法过程去求解问题。由此可见，量子算法是量子计算的灵魂。从量子计算的发展史来看， 正是Shor算法的提出引起了学术界对量子计算的广泛关注。我们也坚信，未来必将由于量子算法的新突破带来量子计算领域的进一步发展。当然，量子算法需要运行在量子计算硬件平台上才能发挥优势。因此，量子计算研究要“软硬兼施”[4]。
围绕“算法”和“复杂性”两个关键词，本报告将从量子查询算法及复杂性、量子交互计算复杂性、量子机器学习、量子优化算法、量子电路优化与经典模拟等五个量子计算理论的主要研究方向进行阐述，分析与比较近年国内外研究进展，并对未来发展趋势进行展望。与本报告内容相关的中文综述性文献可参考[5]。下面对本文涉及到的主要内容进行概要性介绍。
量子查询算法及复杂性。这方面的主要研究可以概括为两方面：（1）通过设计精巧的量子查询算法展示量子计算优势，目前这方面取得了丰硕研究成果。事实上关于量子算法的研究很多时候都是从查询复杂度性角度进行讨论。（2）分析量子查询复杂性下界，目前已经得到一系列求解量子查询复杂性下界的方法，包括多项式方法、对手法、半正定规划方法等。不少问题都能通过这些方法得到非平凡的查询复杂性下界。
量子交互计算复杂性。量子交互计算复杂性理论包括量子交互式证明系统和量子通信复杂性。这一方面是经典计算复杂性在量子计算时代的进一步发展，另一方面也是满足当今量子信息与量子计算科学发展的需求。从现有技术来看，量子计算机的研制和维护成本高昂，未来量子计算或将以云计算的形式给一般用户提供服务。通过连接多个中等规模量子计算机，搭建量子网络实现高效的量子计算；将经典计算机或者小规模量子计算机连接到网络并与之交互，获得更强的量子计算能力是目前量子信息科学研究的一个主流方案。荷兰科学家Wehner等人在《科学》期刊撰文[6] 为这个量子计算方案给出一个清晰的发展纲领。量子交互计算复杂性为量子网络方案提供了理论框架。
量子机器学习。广义的来说，量子机器学习的研究包括两个方面：（1）利用量子计算技术提升经典机器学习方法，（2）利用经典机器学习方法解决量子力学领域的问题。目前这两方面的研究都受到了很大关注。狭隘的量子机器学习仅指上面第一点，这也是本报告所关注的。目前，研究者对机器学习领域的一些主要模型和方法都进行了量子化，即参考经典机器学习算法建立对应的量子算法。这些量子机器学习算法有些可以进行严格的理论分析，有些则是启发式的，依赖于实验分析。量子机器学习领域早期的发展很大程度是源于解线性方程组量子算法（HHL算法）的提出，而近期的研究工作更多集中在基于变分量子电路的算法方面。量子计算与AI的交叉研究值得进行深入探索，不过目前一些量子机器学习方面的研究有待更严肃的理论分析。
量子优化算法。与其他量子算法类似，量子优化的关注点仍然是量子计算的优势，即如何利用量子技术来对经典优化方法进行加速。目前量子优化领域相对于经典方法的加速效果主要体现在函数估值的查询复杂度上。另一方面，近年陆续有小规模或专用的量子计算机问世，无法严格理论分析优势的量子启发式优化算法得到了实验验证的可能，因此也有针对这方面的研究。
量子电路优化与经典模拟。目前由于量子计算机尚在实验研发阶段，量子比特个数、可实现的量子电路深度和规模都非常有限，所以现阶段的研究更应该关注在小规模量子电路的设计与优化上。本文将涉及浅层量子电路的优势、特定量子门构成的量子电路复杂性、受物理硬件结构限制的量子电路优化方法、量子随机电路的经典模拟算法等四个方面的研究进展。
需要指出的是，以上五方面的内容并非完全独立，本文只是相对集中的把它们分成五部分以便组织撰写。首先，量子通信复杂性与量子查询复杂性紧密相关。相比量子查询复杂性，在量子通信复杂性模型中，我们对参与方的局部计算能力不作任何限制，因此这个模型的表达能力更强，计算更加复杂。其次，量子机器学习和量子优化方向的很多算法都是从查询复杂性方面体现量子优势，因此本质上他们是量子查询算法。同时，从经典计算领域来看，优化是机器学习的技术基础，因此量子优化技术自然可以用来提升机器学习问题的求解。
另外，以上几个方面的研究内容也并不完全与前面五个研究视角一一对应。下面用表1把以上五方面的研究内容和五个研究视角的关系更清晰的表示出来，其中打勾表示有关系。例如，量子机器学习既可以从时间复杂性方面进行分析，也可以从查询复杂性角度考虑，还可以讨论样本复杂性问题。再如量子电路优化，如果我们关注的是基本门的个数，那本质上体现的是对应算法的时间复杂性，如果关注的是逻辑门的层数则体现的是电路深度复杂性。
当前，量子技术已经进入到NISQ时代 (带噪音中等规模量子技术，Noisy Intermediate-Scale Quantum Technology)[7]。如何基于现有的量子技术把量子计算推上实用不仅仅是技术问题，也面临计算理论上的挑战。它给理论计算机学家们提出了这样一个科学问题“如何利用带噪音的中等规模量子计算机实现高效和可靠的量子计算”。同时，量子计算领域的远期目标是实现通用量子计算，要达此目标量子纠错是至关重要且充满挑战的一步。目前在量子纠错的理论方面已经取得了丰富成果。由于量子纠错的重要性和内容的丰富性，需要一篇专门的文章才足以承载，因此本文不对此进行介绍，但我们应认识到其重要性所在。
[1] A Ambainis and R Freivalds. 1-way quantum finite automata: strengths, weaknesses and generalizations [C]. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, 1998. 332–341.
[2] A Ambainis and N Nahimovs. Improved constructions of quantum automata. Theor Comput Sci, 2009, 410: 1916–1922.
[3] D Qiu, L Li, P Mateus and A Sernadas. Exponentially more concise quantum recognition of non-RMM regular languages[J], Journal of Computer and System Sciences. 2015, 81: 359–375.
[4] 李绿周，量子计算研究要“软硬兼施”，《中国科学报》 (2020-05-07 第3版 信息技术)，http://www.scholat.com/teamwork/showPostMessage.html?id=7871
[5] 孙晓明, 量子计算若干前沿问题综述. 中国科学: 信息科学, 2016, 46: 982.
[6] S Wehner, D Elkouss, and R Hanson. Quantum internet: A vision for the road ahead [J]. Science, 2018. 362(6412):eaam9288.
[7] J Preskill. Quantum Computing in the NISQ era and beyond [J]. Quantum, 2018. 2:79.
附件
8096
0
2021-09-14
