我院研究生量子算法研究成果被国际顶级学术会议SODA 2024录用

近日，来自中山大学计算机学院量子计算与软件研究所的研究成果论文Recovering the Original Simplicity: Succinct and Deterministic Quantum Algorithm for the Welded Tree Problem（《返璞归真：求解焊接树问题的简洁与确定性量子算法》）被国际顶级学术会议SODA录用。中山大学计算机学院为该论文的唯一署名单位，论文作者按字母序为：Guanzhong Li(李冠中)、Lvzhou Li(李绿周)、Jingquan Luo(罗镜泉)，其中李冠中和罗镜泉分别为李绿周教授团队的博士和硕士研究生。该论文重新审视了在量子算法领域备受关注的焊接树问题，基于硬币量子游走模型设计了求解该问题的具有指数加速优势的简洁确定性量子算法。这不仅打破了硬币量子游走只能实现比经典算法平方加速的刻板印象，而且为简化现有的基于量子游走的算法提供了新思路。据统计，这是SODA历史上首篇署名单位完全来自中国大陆研究机构的专注于量子算法的论文。

焊接树问题

焊接树问题是少数几个基于量子游走展现出量子指数加速优势的问题。形象地说，该问题是要从迷宫入口找到出口，每走一步只能探索周边有路径相连的位置。这里的“迷宫”是两棵深度为n的完全二叉树，它们水平相对放置，中间的叶子左右随机交替“焊接”起来形成一个回路，如下图中虚线所示。假设“迷宫”的信息存放在一张邻接表中。那么，在“迷宫”中每走一步，都需要访问一次邻接表以获取当前位置的相邻信息。焊接树问题即要求尽可能少地访问邻接表从入口找到出口，其中访问邻接表的次数称为查询复杂度。可以证明针对该问题的任何经典算法的查询复杂度都是n的指数量级，即为 Ω(2ⁿ)。

▲深度n=2的焊接树

指数加速确定性量子算法

针对焊接树问题，上述论文基于简单直观的硬币量子游走模型设计了简洁而高效的确定性量子算法。该工作价值体现在以下几点：(1)与Jeffery 和 Zur（STOC'2023）的算法相比，所得的量子算法相当简单，这不仅打破了硬币量子游走只能实现比经典算法二次方加速的刻板印象，而且还展示了最简量子游走模型的威力；(2) 所得的量子算法理论上可以百分之成功，而已有量子算法不可避免地具有失败概率。这也可能改变人们这样的看法：由于量子力学本质上是随机的，不可能存在具有指数加速的确定性量子算法求解焊接树问题；（3）文中展现的简洁的算法思路具有很强的启发意义。如同一位审稿人所说：“这篇论文可能会开创一条新的研究路线，简化现有基于量子游走的算法，并提高它们的效率”。

SODA会议简介

SODA（ACM-SIAM Symposium of Discrete Algorithms）是算法领域的国际顶级会议，主要关注解决离散问题的高效算法和相关数据结构的研究，与 STOC、FOCS 一起被公认为理论计算机科学的三大顶级学术会议，在计算机科学领域享有崇高的声望。

来源：学院党政办公室

编辑：李俊谕、吴晓鸿

初审：王冬梅
审核：颜晓辉
审核发布：马啸