南京大学同时实现了机器学习和通信复杂度的量子优越性
来源：南京大学物理学院
近期，南京大学物理学院固体微结构物理国家重点实验室、人工微结构科学与技术协同创新中心尹华磊、陈增兵课题组的最新研究成果同时实现了机器学习和通信复杂度的量子优越性。
通过巧妙地设计相干态优惠券协议，本工作成功地使用线性光学量子技术实验演示了量子优惠券收集任务，利用“可能近似正确”（PAC）学习理论，首次实验证明了量子技术可以为机器学习提供具有量子优势的学习算法。为了进一步展示量子优惠券理论的潜在应用价值，文章针对备受年轻人追捧的盲盒游戏，设计了其量子版本并成功地进行了实验演示。这些结果有力地证明了利用量子技术可以在机器学习和通信复杂度方面实现相对于经典技术的量子优越性。
相关研究成果以“Experimental Quantum Advantage with Quantum Coupon Collector”为题于2022年4月30日发表在美国《Science》杂志首个合作期刊《Research》【Research 2022,9798679 (2022)】上。
论文共同第一作者为南京大学物理学院研究生周民罡、曹啸宇和陆玉硕，通信作者为南京大学尹华磊副教授和陈增兵教授。该研究工作得到国家自然科学基金、江苏省自然科学基金、中央高校基本科研业务费、南京江北新区重点研发计划等的支持。
机器学习可以从数据中提取有用的信息与知识，从而对基础理论、先进技术和社会生产力等方面产生重大的影响。精确调控量子态技术在通信安全、计算速度和测量精度等方面已经展现出超越经典技术的量子优势。通过利用量子技术来改进机器学习或者实现量子机器学习是近年来的研究热点，当前已经有大量的研究工作开展了创新性探索【Nature 549, 195(2017)】。
然而，这些尝试大多都是启发式的，并没有从理论上证明量子机器学习比经典机器学习表现出更好的性能或拥有更短的训练时间。PAC学习理论量化了一个学习算法能够有效学习一个学习任务所需的最小样本数，因此，利用该理论研究量子机器学习，可以为探索机器学习中的量子优势奠定理论基础。2020年，荷兰阿姆斯特丹大学研究团队和美国IBM公司研究团队共同提出了量子优惠券收集问题，并用PAC学习理论首次严格地证明了该问题存在具有量子优势的学习算法 【In 15th Conference On the Theory of Quantum Computation, Communication and Cryptography (2020)】。
具体来说，所有希望学习到的目标函数所构成的集合称为“概念类”；给定一个学习算法，它所考虑的所有可能映射的集合称为“假设空间”。若在PAC学习中，假设空间和概念类完全相同，则为恰PAC可学习（properly PAC learnable）；否则，称为不恰PAC可学习（improperly PAC learnable）。一般来说，经典恰和不恰PAC可学习的样本复杂度是不一样的，然而，对于优惠券收集问题来说，恰和不恰PAC可学习所需的样本复杂度在量子算法下是可以相同的。因此，该量子优惠券收集算法是第一个依据PAC学习理论展现经典和量子机器学习之间存在根本性不同的算法。
原始的量子优惠券算法的实验演示需要用到高度复杂的单光子量子指纹态，以及远超当前实验技术的高度非线性测量装置实现超高维半正定算子测量（POVM）。为此，本工作提出相干态量子优惠券协议，巧妙地将单光子量子指纹态转换为等效的相干态张量积形式，将单光子在维数上的振幅信息转换为相干态在时间箱上的相位信息。文章理论证明了相干态量子优惠券与原始量子优惠券在机器学习量子优势方面的等价性，从而实现了利用当前广泛使用的光量子通信技术（激光器、线性光学元器件和单光子探测器）来演示量子优惠券收集任务。
实验中，本工作需要最大限度地降低量子态干涉测量的噪声：（1）利用Sagnac干涉仪实现稳定的时间和相位对准；（2）利用高精度的相位调制技术实现高速π相位精确制备；（3）利用高对称的保偏分数器实现偏振和强度对准；（4）利用高效率和超低暗计数的超导纳米线单光子探测器实现近似完美测量。基于这些实验技术，课题组最终清晰地演示了量子优越性，如下图所示。
量子优惠券实验结果
此外，本工作还针对火遍全球的盲盒游戏进行了量子版本设计并成功地进行了实验演示，充分地展示了量子优惠券理论的潜在应用价值和量子技术在通信复杂度上的优势。在游戏中，商家将不同图案的小球分别装进不同的盒子里形成盲盒，商家从中挑选几乎全部盒子作为盲盒套装，并制作了相同配置的多套盲盒套装。顾客只能在每套盲盒套装中抽取一个盲盒，来确认整套盲盒套装中所有小球的图案。顾客每消耗一套盲盒套装就需要支付一定数额的费用，若顾客成功猜对，商家就会奖励给顾客奖金，奖金的数额为经典策略下所消耗盲盒套装费用的期望值。使用量子资源对盲盒进行编码，顾客就可以通过设计量子编码和量子测量来降低自己的成本，从而在这个游戏中获得更多的回报。
量子优惠券实验结果表明，量子协议可以有效地减少学习具有多达14000个元素的优惠券所需的样本数量。此外，量子盲盒游戏实验结果（如下图所示）表明，针对不同类型的盲盒套装，顾客总可以通过选择合适的光强来降低成本以获得更多的回报，这说明量子优惠券协议在这种游戏中消耗的资源少于最好的经典策略。这些结果有力地证明了即使没有使用多粒子纠缠态和量子门操控，仅仅利用线性光学的量子技术就可以在机器学习和通信复杂度方面实现相对于经典技术的量子优越性。
量子盲盒游戏实验结果
论文链接：
https://spj.sciencemag.org/journals/research/2022/9798679/