View Proposal

Proposer
Kai Lin Ong
Title
Quantum Walks for Enhanced PageRank Algorithms
Goal
This project aims to explore the quantisation of PageRank algorithm and evaluate its effectiveness in selected domains
Description
The efficiency of search engines relies on the ability of underlying ranking algorithms to deliver relevant information effectively. One of the most well-known is the PageRank algorithm, adopted by Google, which models a random walker navigating the web’s link structure to assign importance scores to pages. This project aims to explore the quantisation of PageRank algorithm and evaluate its effectiveness in selected domains. The core idea behind Quantum PageRank is the use of Szegedy’s quantum walk in place of classical random walkers. These quantum walks enable faster propagation and more efficient search and ranking through inherent quantum properties such as interference and amplitude amplification. Quantum PageRank is expected to address several shortcomings of the classical method by highlighting the structure of secondary hubs, partially resolving degeneracy among lower-ranked nodes, and exhibiting greater stability with respect to changes in the damping factor. The first phase of this project involves studying the framework of classical PageRank algorithm and the essential mathematical foundations of Szegedy’s quantum walk. A literature review will follow to analyse existing research and developments in Quantum PageRank. The project will then explore potential variants of the algorithm, consider possible extensions, and evaluate their effectiveness through practical experiments.
Resources
Chawla, P., Mangal, R. and Chandrashekar, C.M. (2020) 'Discrete-time quantum walk algorithm for ranking nodes on a network,' Quantum Information Processing, 19(5). https://doi.org/10.1007/s11128-020-02650-4. Paparo, G.D. et al. (2013) 'Quantum Google in a complex network,' Scientific Reports, 3(1). https://doi.org/10.1038/srep02773. Sánchez-Burillo, E. et al. (2012) 'Quantum navigation and ranking in complex networks,' Scientific Reports, 2(1). https://doi.org/10.1038/srep00605. Sharma, P.S., Yadav, D. and Garg, P. (2020) 'A systematic review on page ranking algorithms,' International Journal of Information Technology, 12(2), pp. 329–337. https://doi.org/10.1007/s41870-020-00439-3.
Background
Url
Difficulty Level
Challenging
Ethical Approval
None
Number Of Students
1
Supervisor
Kai Lin Ong
Keywords
quantum computing, page rank, quantum walks
Degrees
Bachelor of Science in Statistical Data Science
Back to List