讲座题目: State Complexity Advantage of Exact Quantum Finite Automaton：Theory & Experimental

讲座人：郑盛根 (深圳鹏城实验室量子计算研究中心) 副研究员

讲座时间：16:00-17:00

讲座日期：2019年10月26日

地点：长安校区 文津楼三段6层3607学术讨论室

主办单位：计算机科学学院 计算智能团队

讲座内容：In quantum information science, a major task is to find the quantum models that can outperform their classical counterparts. Automaton is a fundamental computing model that has wide applications in many fields. The potential of quantum finite automata producing outcomes not only with a (high) probability, but with certainty (so called exactly) is explored in the context of their uses for solving promise problems and with respect to the size of automata. It is shown that for solving particular classes of promise problems, even those without some very special structure, that succinctness of the exact quantum finite automata under consideration, with respect to the number of (basis) states,  can be very small (and constant) though it grows proportional to n in the case deterministic finite automata (DFAs) of the same power are used [1]. The method used can be applied in finding more exact quantum finite automata or quantum algorithms for other promise problems.

We also report an experimental demonstration of an optical quantum automaton, which is used to solve the promise problems of determining whether the length of an input string can be divided by a prime number P with no remainder or with a remainder of R [2]. Our quantum automaton can solve such problem using a state space with only 3 orthonormal states, whereas the classical automaton needs  no less than P states. Our results demonstrate the quantum benefits of a quantum automaton over its classical counterpart and paves the way for implementing quantum automaton for more complicated and practical applications.

讲座人简介：郑盛根，深圳鹏城实验室量子计算研究中心副研究员、主任助理，量子算法与复杂性理论子课题负责人。2012年在中山大学获得博士学位，2012-2015在捷克和拉脱维亚从事博士后工作，师从Gruska和Ambainis教授。2015.07-2018.03年在中山大学担任副研究员，2018.03至今南方科技大学副教授,2018.11月加入鹏城实验室。主要从事量子算法，量子计算复杂性理论研究。2015年与Ambainis一起合作证明了精确量子查询算法几乎对所有的布尔函数都有优势，解决了量子查询领域里一个十几年来的公开问题。在Information and Computation, Theoretical Computer Science,  Mathematical Structures in Computer Science, NPJ Quantum Information等以第一或者通讯作者发表SCI论文二十多篇。郑盛根将是第23届量子信息处理国际会议QIP'2020的Local Chair。