The quantum walk is a powerful tool to develop quantum algorithms, which usually are based on searching for a vertex in a graph with multiple marked vertices, Ambainis's quantum algorithm for solving the element distinctness problem being the most shining example. In this work, we address the problem of calculating analytical expressions of the time complexity of finding a marked vertex using quantum walk-based search algorithms with multiple marked vertices on arbitrary graphs, extending previous analytical methods based on Szegedy's quantum walk, which can be applied only to bipartite graphs. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.


翻译:量子漫步是开发量子算法的有力工具,它通常基于在带有多标记的脊椎的图表中搜索一个顶点,即Ambainis的量子算法,以解决元素差异性问题的量子辨别问题是最光辉的例子。在这项工作中,我们解决了使用在任意图形上带有多标记的垂直点的量子漫步搜索算法来计算一个标志性顶点的时间复杂性分析表达方式的问题,该算法以量子漫步法为基础,扩展了以前基于Szegedy量子漫步的分析方法,该方法只能应用于双方图。基于在二维层和超立方的硬体上的量子漫步的两个实例显示了我们方法的细节。

0
下载
关闭预览

相关内容

系列教程GNN-algorithms之七:《图同构网络—GIN》
专知会员服务
47+阅读 · 2020年8月9日
【DeepMind】强化学习教程,83页ppt
专知会员服务
152+阅读 · 2020年8月7日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
3+阅读 · 2018年4月10日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
Arxiv
0+阅读 · 2021年5月26日
Arxiv
0+阅读 · 2021年5月21日
Arxiv
0+阅读 · 2021年5月20日
Optimization for deep learning: theory and algorithms
Arxiv
104+阅读 · 2019年12月19日
Arxiv
4+阅读 · 2018年4月30日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
3+阅读 · 2018年4月10日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
Top
微信扫码咨询专知VIP会员