报告题目：Playing Mastermind on quantum computers

报  告  人： 李绿周 教授 

报告摘要：Mastermind（中文名叫珠玑妙算）是一款流行的棋盘游戏，有两名参与方：编码者和解码者。编码者手里有一个n位的k进制秘密串，在每一轮交互中，解码者可以猜一个串发给编码者，而编码者将反馈所猜的串与秘密串的一些差异信息（例如汉明距离）。解码者的目的就是要使用尽可能少地与编码者的交互而获得秘密串，交互的轮次称为查询复杂度。关于该游戏的算法研究即为解码者设计查询复杂度尽可能低的策略。Mastermind由以色列通讯专家M.Meirowitz在1971年发明，最早可以追溯到1963年沃尔夫奖得主P. Erdős等人的工作。从20世纪70年代至今，其不仅作为一款游戏得到了大众的欢迎，而且也作为一个科学问题得到了学术界的深入研究,例如图灵奖得主D.Knuth解决了这方面的一个基本问题。我们在最近的一个工作中，对Mastermind游戏的量子策略进行了比较系统的研究，得到了体现实质性加速优势的量子算法。值得指出的是，我们的量子算法的查询复杂度通常与n无关，而经典复杂度是随n单调增长的。在技术层面，我们给出了一个三步求解框架，该框架不仅可用于Mastermind问题，也可能适用于更一般的串学习问题。

报告人简介：李绿周，中山大学计算机学院量子计算与计算机理论研究所教授、计算机科学系主任、中国计算机学会（CCF）量子计算专业组副主任、CCF理论计算机科学专委常务委员、CCF杰出会员、CCF杰出演讲者。主要从计算机科学角度出发，围绕量子计算模型、量子算法与复杂性、量子机器学习、量子编译与优化等方向开展研究，发表学术论文70余篇，出版学术专著1部。曾获广东省杰出青年基金、湖南省自然科学二等奖、CCF优秀博士学位论文奖、中山大学青年教师授课大赛一等奖等。

报告时间：2023年3月15日星期三 11:00-12:00

报告地点：腾讯会议ID：298-344-842（密码：0315）

学院联系人：张林

欢迎感兴趣的老师和同学参加！