次模优化问题的量子算法
Organizers
Speaker
Shengminjie Chen
Time
Friday, May 8, 2026 4:00 PM - 5:30 PM
Venue
Shuangqing-B626
Online
Zoom 230 432 7880
(BIMSA)
Abstract
次模函数刻画了一类具有边际收益递减性质的函数，广泛出现在人工智能、数据挖掘、社会福利分配等重要场景中。本报告聚焦于具有次模性的组合优化问题，重点探讨两类量子算法：量子零阶算法与变分量子算法。首先，针对次模函数最大化问题，我们设计了量子零阶算法。该算法利用相位Oracle与量子层析技术来估计目标函数的有偏随机梯度，在保证相同近似比的条件下理论上证明了量子零阶算法能够达到经典一阶算法的收敛速度，展现出量子方法在零阶优化中的潜在加速优势。其次，针对变分量子算法，我们建立了基于Lyapunov函数的变分分析框架。通过构造与算法近似比直接关联的Lyapunov函数，并严格控制其单调性，该框架能够直接导出算法的近似比下界，为变分量子算法的性能分析提供了一种新的理论工具。
Speaker Intro
陈晟敏杰，中国科学院计算技术研究所特别研究助理、助理研究员。2024年于中国科学院大学数学科学学院获博士学位，曾荣获中国科学院院长特别奖。主要研究兴趣包括组合优化、量子组合优化及量子优化算法。近年来，在ICLR、ICML、JORSC、TCS、IEEE TNSE、IEEE TCSS、JOCO等国内外学术会议与期刊上发表论文10余篇。