澳门新葡亰平台游戏

澳门新葡亰平台游戏 学术动态

【学术预告】Controlled quantum search on structured databases

报告题目:Controlled quantum search on structured databases

报告专家:吴盛俊 教授 (南京大学匡亚明学院)

报告时间:2018年12月18日(星期二) 下午3:00-4:00

报告地点:行健楼 437室

内容概况:

Grover's algorithm provides a quadratic quantum speedup for searches on unsorted databases, and a simple approach via continuous-time quantum walk (CTQW) can also achieve the quantum speedup on certain graphs like the complete graphs. However, a standard approach via CTQW cannot achieve the same quantum advantage on databases with tree structures like the telephone directories. We propose quantum algorithms to search on databases with tree structures via generalized CTQWs. In order to find a marked vertex on a balanced tree of height $r$ with $N$ vertices, we adopt a multi-stage search process with suitable jumping rates at each stage. A success probability close to $100\%$ is achieved and a runtime with the dominant term proportional to $N^{(2r-1)/2r}$ is obtained when the branching factor is large. We further find that the number of stages can be actually controlled while keeping the high success probability. By adjusting the edge weights on the graphs, we can merge the multi-stage search process into a single stage, and achieve an optimal runtime $\Theta(\sqrt{N})$! Our search algorithms also work for real trees with unbalanced structures and are quite robust against various kinds of small perturbations.

报告人概况:
 

吴盛俊,南京大学物理学教授,在匡亚明荣誉学院从事教学科研,为南京大学大理科试验班培养拔尖人才。主要研究领域为量子信息与量子物理,研究的课题包括量子关联、弱测量理论、量子游走、量子算法和量子人工智能等。已主持4项国家自然科学基金面上项目,参与多项国家重点研发计划;在物理评论快报、物理评论A等 SCI 国际期刊发表论文40多篇。

发布时间:2018/12/05
XML 地图 | Sitemap 地图