当前,以量子信息科学为代表的量子科技正在不断形成新的科学前沿,激发革命性的科技创新,孕育对人类社会产生巨大影响的颠覆性技术。量子信息科技的具体应用包括量子通信、量子计算和量子精密测量三方面。
量子计算具有强大的并行计算和模拟能力,可为人工智能、密码分析、气象预报等所需的大规模计算难题提供解决方案。总体来看,我国在量子计算方面与发达国家处于同一水平线。
我国量子领域在量子计算方面未来 10 到 15 年的发展目标是确立和巩固我国在全球第一方阵的地位,有效解决大尺度量子系统的效率问题,研制对特定问题的求解能力全面超越经典超级计算机的专用量子模拟机,并为最终实现通用量子计算机探索出一条切实可行的道路。
日前,在由中国科学院物理研究所和量子计算研究中心主办、中国科学院物理研究所学术服务部协办的 “量子计算及量子信息研讨会”上,中山大学李绿周教授作了题为《什么样的问题可以被一次查询精确量子算法解决?》的报告,探讨了一次查询精确量子算法解决以及量子计算与经典计算的差别与优势。
什么叫做一次查询精确量子算法解决?该量子算法只执行一次查询操作,要求这一算法精确解决问题,没有出错概率,“这种情况下,它可能比经典算法有优势”李绿周教授表示。像我们所知道的常规的 Shor 算法、Gover 算法都是有出错概率的。
这个问题很简单,但到现在还未完全解决。
探寻量子计算优势为什么会关注量子计算,量子计算对比经典计算,其优势在哪里?针对哪些工作、哪一方面?量子计算速度更快、更好,那么它是怎么更快、怎么更好?
度量量子计算与经典计算差别的角度有很多,李绿周教授主要从查询复杂度方面分析了量子计算与经典计算的差别以及其优势所在。
· 通过基本量子酉变换可以构建一些特定的量子算法。有了高效的量子算法,量子计算机的并行计算就可以充分发挥其优势。
量子经典模型
为什么讨论这一模型?查询模型意义何在?· 查询模型本质上是只关注某个子过程的调用次数,而不关心其内部结构。
· 查询模型具有现实意义:例如,在执行摸个计算任务时,我们可能只关心读取外存的次数,而不是在意外存内部的运行机制。
· 查询模型为度量复杂性提供了一个便利的视角:时间复杂度下界难以刻画或衡量(如 P 与 NP 的关系),二查询复杂度通常有系统的度量方法。
· 经典与量子计算二者计算能力的比较很多时候是从查询复杂度角度进行考量。比如 Deutsch-Jozsa 算法,Simon 算法,Grover 算法都是从查询复杂度方面去体现这一点。
量子查询模型
量子查询算法
通过研究得出,经典情况下,一次只能查询一位;量子情况下,一次可以以叠加形式查询。
其次,著名的 Deutsch-Jozsa 算法就是一次查询精确量子算法。那么,能否找到更多的问题可以被一次查询精确量子算法解决?
除此之外,一次查询的有界误差量子算法得到了一些研究,但是结果对精确量子不适用。
关于精确量子算法的意义,有观点认为 “容忍出错概率才换来了算法的提速”,精确量子算法对此事很好的反驳,体现了概率算法的区别。精确这个词的说法体现了量子与概率从某种程度上的区别。