Tehnički vjesnik, Vol. 24 No. 5, 2017.
Izvorni znanstveni članak
https://doi.org/10.17559/TV-20160104014155
Link prediction using discrete-time quantum walk
Jing Qian
; College of Physical Science and Technology, Central China Normal University, No. 152, Luoyu Road, Wuhan 430079, China
Lintao Yang
; College of Physical Science and Technology, Central China Normal University, No. 152, Luoyu Road, Wuhan 430079, China
Zetai Yu
; College of Physical Science and Technology, Central China Normal University, No. 152, Luoyu Road, Wuhan 430079, China
Shouyin Liu
; College of Physical Science and Technology, Central China Normal University, No. 152, Luoyu Road, Wuhan 430079, China
Sažetak
Link prediction is one of the key issues of complex networks, which attracts much research interest currently. Many link prediction methods have been proposed so far. The classical random walk as an effective tool has been widely used to study the link prediction problems. Quantum walk is the quantum analogue of classical random walk. Numerous research results show that quantum algorithms using quantum walk outperform their classical counterparts in many applications, such as graph matching and searching. But there have been few studies of the link prediction based on quantum walk, especially on discrete-time quantum walk. This paper proposes a new link prediction method based on discrete-time quantum walk. Experiment results show that prediction accuracy of our method is better than the typical methods. The time complexity of our method running on classical computers, compared with the methods based on classical random walk, is slightly higher. But our method can be greatly accelerated by executing on quantum computers.
Ključne riječi
complex networks; discrete-time quantum walk; computer engineering; link prediction
Hrčak ID:
188227
URI
Datum izdavanja:
25.10.2017.
Posjeta: 2.367 *