报告题目：基于量子游走的采样和和搜索算法

报告人：尚云教授（中国科学院数学与系统科学研究院）

报告时间：2023年10月21日（周六）上午9:00-10:30

报告地点：科技楼三楼报告厅

报告摘要：量子游走是强有力的量子计算模型。本报告将介绍我们在马尔可夫链上的量子采样和搜索算法中的两个工作。（1）将量子fast-forwarding思想用于量子插值游走模型构建了一个新的量子平稳分布采样算法，该算法不仅可以对非正则图加速，而且可以保持现有量子算法对正则图的加速。特别是在稀疏图上，与现有量子算法相比，我们算法的复杂度降低Θ (log𝑛)倍，其中𝑛是图的顶点数。在非正则图中，我们的算法相比当前离散时间和连续时间的最先进量子平稳分布采样算法均有加速。在正则图中，复杂度与其它量子算法保持一致，相比经典情况关于马尔可夫链的谱隙实现了二次加速；（2）基于离散时间量子游走，构造了一个针对可逆马尔可夫链单标记顶点的搜索算法。目前大多数量子搜索算法及采样算法的成功概率较小，通常运用振幅放大思想来提高成功概率。但是，振幅放大的调用会引发soufflé问题，为算法的实际应用带来困难。我们定义了广义插值量子游走，改进后的搜索算法和平稳分布采样算法，在提高搜索算法的成功概率的同时也避免了soufflé问题。随后，通过引入量子fast-forwarding思想减少了调用量子插值游走算子的次数和辅助量子比特的数量。最后，给出了广义插值量子游走在绝热计算量子态制备中的一个重要应用。

个人简介：尚云，中国科学院数学与系统科学研究院研究员，博士生导师，CCF杰出会员。已主持完成多项国家自然科学基金，获得CCF自然科学奖二等奖、英国皇家物理学会IOP高引用作者奖、王宽诚教育基金会“优秀女科学家专项奖”、陕西省科学技术奖励二等奖等荣誉。研究领域：量子计算和量子信息基础，具体方向包括量子游走、量子算法、量子机器学习、基于量子逻辑的计算理论、量子点元胞电路的自动设计以及量子程序语言。