量子算法—从理论到实践-郑盛根.pdf

1、郑盛根粤港澳大湾区量子科学中心量子算法从理论到实践12025/9/162科学的发展 哲学解释数学解释物理解释Science is being born of a faith in the(philosophical,mathematical,physical)information processinginterpretation of nature.新观点：万物起源于量子信息文小刚2025/9/163为什么量子计算与量子信息如此重要？该学科可以看成是二十世纪最重要的新兴科学量子物理和新兴技术信息处理与计算的结合，所以人们期待该学科在新的世纪能发挥重要的作用和更为广泛的应用。1）数学游戏 2）

2、有用理论 3）超越经典“量子霸权”4）实用算法 5）应用尝试？2025/9/164数学游戏 Deutsch 算法经典2次查询 f量子1次查询 f2025/9/1651,01,0:f没有误差数学游戏2025/9/166DeutschJozsa algorithm (promise problem)经典查询量子查询1次允许误差（优势消失）1,01,0:nf DeutschJozsa 算法 (promise problem)数学游戏数学游戏2025/9/167 Simon 算法数学游戏nnf1,01,0:找出s 经典查询量子查询有误差数学游戏2025/9/16有用理论Shors algorithm(

3、大数分解)在1994年Shor证明了大数分解问题可以被量子图灵机在多项式时间内解决，该问题在经典计算机下的难解性是RSA公钥密码系统之所以存在的理论依据。（优势不可严格证明）大数分解例子：479447963918289*2621512025/9/169Grovers algorithm（无序搜索）问题：从N个未分类的客体中寻找出某个特定客体。例如:从按姓序排列的个电话号码中找出某个特定的号码。一个个查询，直到找到所要的号码。平均讲，要查次1/2N，找到的几率为1/2采用并行处理，只需次 ，找到的几率接近100(Grover算法)。有用理论2025/9/1610有用理论 HHL算法（解线性方程组

4、）量子启发式算法（quantum-inspired）2025/9/1611若干优势查询算法公开问题：精解量子算法对什么布尔函数有优势？对几乎所有的布尔函数 对一些特殊的布尔函数有优势1,01,0:nf2025/9/1612若干优势查询算法Deutsch 算法 精确一次查询DeutschJozsa 算法 精确一次查询问题：精确一次查询算法还能干点啥？结论：任意对称布尔函数的精确查询复杂度为1当且仅当它可以被DeutschJozsa 算法计算 2025/9/1613若干优势查询算法问题：精确一次查询算法还能干点啥？结论：任意对称布尔函数的精确查询复杂度为1当且仅当它可以被DeutschJozsa

5、算法计算 问题：对一般的函数呢？部分刻画：完全刻画：1 Zekun Ye,Lvzhou Li,Characterization of exact one-query quantum algorithms(ii):for partial functions，arXiv preprint arXiv:2008.119982 Guoliang Xu,Daowen Qiu,Partial Boolean functions with exact quantum 1-query complexity,arXiv preprint arXiv:2007.109242025/9/1614若干优势查询算法De

6、utschJozsa问题 DJ(x)=01if x=0 orx=if|x|=/2推广：2025/9/1615超越经典“量子霸权”量子霸权 (量子优势)能比经典计算机更好地解决一个特定计算问题 Noisy Intermediate-Scale Quantum(NISQ)随机电路采样53Qbit2025/9/1616超越经典“量子霸权”量子霸权 (量子优势)中科大，九章：玻色采样中科大，祖冲之号：62比特中科大，祖冲之二号：66比特中科大，九章：玻色采样中科大，九章三号2025/9/1617实用算法2025/9/161