On new PageRank computation methods using quantum computing

Théodore Chapuis-Chkaiban (1) , Zeno Toffano (2) , Benoît Valiron (3, 1, 4)

1 CentraleSupélec
2 L2S - Laboratoire des signaux et systèmes
3 QuaCS - Quantum Computation Structures
4 LMF - Laboratoire Méthodes Formelles

In this paper we propose several new quantum computation algorithms as an original contribution to the domain of PageRank algorithm theory, Spectral Graph Theory and Quantum Signal Processing. We first propose an application to PageRank of the HHL quantum algorithm for linear equation systems. We then introduce one of the first Quantum-Based Algorithms to perform a directed Graph Fourier Transform with a low gate complexity. After proposing a generalized PageRank formulation, based on ideas stemming from Spectral Graph Theory, we show how our quantum directed graph Fourier Transform can be applied to compute our generalized version of the PageRank.

Mots clés: Quantum computing; PageRank; Graph Fourier transform; Spectral graph theory; Information theory

Domaines: Recherche d'information [cs.IR]; Physique Quantique [quant-ph]

Théodore Chapuis-Chkaiban, Zeno Toffano, Benoît Valiron. On new PageRank computation methods using quantum computing. Quantum Information Processing, 2023, 22 (3), pp.138. ⟨10.1007/s11128-023-03856-y⟩. ⟨hal-04056045⟩