当前位置： 首页 >讲座预告

南京大学吴盛俊教授将于8月6日在研究所做学术报告

作者：admin123 来源： 发布时间：2018-08-01 11:51:47 阅读次数：

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

吴盛俊  南京大学

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

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