当前位置: 首页 >讲座预告
南京大学吴盛俊教授将于8月6日在研究所做学术报告
作者:admin123 来源: 发布时间:2018-08-01 11:51:47 阅读次数:

​报告题目:有结构的数据库上的量子搜索算法 

吴盛俊  南京大学

摘要:Grover遍历搜索算法在量子算法中具有举足轻重的地位。在实际物理数据的搜索中,因为数据结构本身的原因,Grover算法的实现有较大的限制。Grover算法对应于完全图上的物理数据的量子游走,当图有N个数据时,能到达根号N的最佳时长。而对于有一般结构的物理数据上的搜索,未必能实现最佳时长。我们针对具有Cayley树结构的这类型的图上的数据搜索开展了研究,发现树的高度决定了搜索的阶段数;在无法改变连接权重的情况下,我们给出了最好的算法;对于含N个顶点的高度为rCayley树,实现了时长为N^((2r-1)/2r)量子搜索算法。但是这种多阶段的算法仍然无法取得根号N的最佳时长。当我们可以控制不同层之间的权重时,可以把多个阶段的搜索变成一个阶段,从而实现根号N的最佳时长。我们的算法,不管是多阶段的还是可控权重的单阶段算法,都能达到很高的成功概率,而且不会随着树高度和分叉数的增加而降低。 

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

常用链接

联系我们   |   访问接待  |   校址:山西省大同市兴云街405号   邮政编码:037009   Copyright © 2019 山西大同大学 All Rights Reserved.