On new PageRank computation methods using quantum computing

被引：3

作者：

Chapuis-Chkaiban, Theodore ^{[1
]}

Toffano, Zeno ^{[2
]}

Valiron, Benoit ^{[3
]}

机构：

[1] Cent Supelec, Dept Comp Sci, 3 Rue Joliot Curie, F-91190 Gif Sur Yvette, France

[2] Univ Paris Saclay, CNRS, Cent Supelec, Lab Signaux & Syst, F-91190 Gif Sur Yvette, France

[3] Univ Paris Saclay, CNRS, Cent Supelec, Lab Methodes Formelles,ENS Paris Saclay, F-91190 Gif Sur Yvette, France

来源：

QUANTUM INFORMATION PROCESSING | 2023年 / 22卷 / 03期

关键词：

Quantum computing; PageRank; Graph Fourier transform; Spectral graph theory; Information theory; SEARCH;

D O I：

10.1007/s11128-023-03856-y

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

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.

引用

页数：40

共 41 条

[1] Statistical mechanics of complex networks
Albert, R
Barabási, AL
[J]. REVIEWS OF MODERN PHYSICS, 2002, 74 (01) : 47 - 97
[2] On the robustness of bucket brigade quantum RAM
Arunachalam, Srinivasan
Gheorghiu, Vlad
Jochym-O'Connor, Tomas
Mosca, Michele
Srinivasan, Priyaa Varshinee
[J]. NEW JOURNAL OF PHYSICS, 2015, 17
[3] Baeza-Yates R., 2006, Proceedings of the Twenty-Ninth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, P308, DOI 10.1145/1148170.1148225
[4] Emergence of scaling in random networks
Barabási, AL
Albert, R
[J]. SCIENCE, 1999, 286 (5439) : 509 - 512
[5] BOLDI P., 2007, WAW2006 4 INT WORKSH, P107, DOI [DOI 10.1007/978-3-540-78808-9_10, 10.1007/978-3-540-78808-9_10]
[6] Brassard G., 2002, CONT MATH, V305, DOI DOI 10.1090/CONM/305/05215
[7] The anatomy of a large-scale hypertextual Web search engine
Brin, S
Page, L
[J]. COMPUTER NETWORKS AND ISDN SYSTEMS, 1998, 30 (1-7): : 107 - 117
[8] Scale-Free Graph with Preferential Attachment and Evolving Internal Vertex Structure
Choromanski, Krzysztof
Matuszak, Michal
Miekisz, Jacek
[J]. JOURNAL OF STATISTICAL PHYSICS, 2013, 151 (06) : 1175 - 1183
[9] Chung F., 1997, SPECTRAL GRAPH THEOR, V92
[10] Preconditioned Quantum Linear System Algorithm
Clader, B. D.
Jacobs, B. C.
Sprouse, C. R.
[J]. PHYSICAL REVIEW LETTERS, 2013, 110 (25)

← 1 2 3 4 5 →