Liu Ying, Yuan Jiabin, Duan Bojia, Li Dan
Nanjing University of Aeronautics and Astronautics, College of Computer Science and Technology, Nanjing, 211106, China.
Sci Rep. 2018 Jun 22;8(1):9548. doi: 10.1038/s41598-018-27825-z.
Quantum walks on graphs have shown prioritized benefits and applications in wide areas. In some scenarios, however, it may be more natural and accurate to mandate high-order relationships for hypergraphs, due to the density of information stored inherently. Therefore, we can explore the potential of quantum walks on hypergraphs. In this paper, by presenting the one-to-one correspondence between regular uniform hypergraphs and bipartite graphs, we construct a model for quantum walks on bipartite graphs of regular uniform hypergraphs with Szegedy's quantum walks, which gives rise to a quadratic speed-up. Furthermore, we deliver spectral properties of the transition matrix, given that the cardinalities of the two disjoint sets are different in the bipartite graph. Our model provides the foundation for building quantum algorithms on the strength of quantum walks on hypergraphs, such as quantum walks search, quantized Google's PageRank, and quantum machine learning.
图上的量子游走已在广泛领域展现出显著优势和应用。然而，在某些场景中，由于超图内在存储信息的密集性，规定超图的高阶关系可能更自然且准确。因此，我们可以探索超图上量子游走的潜力。在本文中，通过呈现正则均匀超图与二分图之间的一一对应关系，我们利用塞格迪量子游走构建了正则均匀超图二分图上的量子游走模型，该模型带来了二次加速。此外，鉴于二分图中两个不相交集合的基数不同，我们给出了转移矩阵的谱性质。我们的模型为基于超图上量子游走构建量子算法奠定了基础，如量子游走搜索、量化的谷歌网页排名和量子机器学习。
