中科院数学与系统科学研究院

数学研究所

学术报告

计算机科学研讨班

报告人：李绿周（中山大学）   

题  目：返璞归真：求解焊接树问题的简洁确定性量子算法

时  间：2023.05.27（星期六）09:00-10:00

地  点：数学院南楼N802

摘  要：We present a concise quantum algorithm based on the simplest coined quantum walks to address the well-known welded tree problem. It not only exhibits exponential speedups over any classical algorithm, but also returns the correct answer deterministically.

Compared to the recent algorithm (Jeffery and Zur, STOC'2023), our algorithm is quite concise, breaking the stereotype that coined quantum walks can only achieve quadratic speedups over  classical algorithms, and demonstrating the power of the simplest quantum walk model. Our algorithm  theoretically achieves zero-error, which is not possible with existing methods. As such, it becomes one of the few examples that exhibit exponential separation between deterministic (exact) quantum and randomized query complexities, which may also change people's perception that since quantum mechanics is inherently probabilistic, it impossible to have a deterministic quantum algorithm with exponential speedups for this problem.

简  介：李绿周，中山大学计算机学院教授、量子计算与软件研究所所长、中国计算机学会（CCF）量子计算专业组副主任。长期从事量子计算研究，解决了量子自动机的等价性、最小化等开放问题，目前主要研究兴趣为量子算法与复杂性、量子计算模型、量子机器学习、量子电路编译与优化等，在主流国际学术期刊发表学术论文70余篇，出版学术专著1部。