Quantum walks on regular uniform hypergraphs

Abstract

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.