We present a quantum algorithm for obtaining a quantum state that encodes the PageRank vector of the Google matrix through multistep quantum resonant transition (mQRT). In the algorithm, the PageRank vector is encoded in the ground state of a problem Hamiltonian associated with the Google matrix. By dividing the web graph corresponding to the Google matrix into a series of subgraphs with nested structure, we construct a sequence of Hamiltonians based on the subgraphs to form a Hamiltonian evolution path from a simple initial Hamiltonian to the problem Hamiltonian. The ground state of the problem Hamiltonian is obtained by going through ground states of the intermediate Hamiltonians via QRT step by step. This algorithm requires only one ancillary qubit, and the runtime of the algorithm is proportional to the number of steps. It provides a new way for efficiently obtaining the quantum state of the PageRank vector of large-scale networks.
Journal reference
Journal of Computational and Applied Mathematics 491 (2027) 118059
We present a quantum algorithm for obtaining a quantum state that encodes the PageRank vector of the Google matrix through multistep quantum resonant transition (mQRT). In the algorithm, the PageRank vector is encoded in the ground state of a problem Hamiltonian associated with the Google matrix. By dividing the web graph corresponding to the Google matrix into a series of subgraphs with nested structure, we construct a sequence of Hamiltonians based on the subgraphs to form a Hamiltonian evolution path from a simple initial Hamiltonian to the problem Hamiltonian. The ground state of the problem Hamiltonian is obtained by going through ground states of the intermediate Hamiltonians via QRT step by step. This algorithm requires only one ancillary qubit, and the runtime of the algorithm is proportional to the number of steps. It provides a new way for efficiently obtaining the quantum state of the PageRank vector of large-scale networks.
The classification of information contained in complex networks such as the WWW is a central problem in network science for its technological impact. A highly successful methodology for this purpose is Google’s PageRank algorithm. It allows to measure the importance or relevance of a web page depending on the relationship between pages and its connections, i.e, the hyperlink structure. Finding ways to apply the advantages of quantum computers to real world computational tasks is an active research area. In this thesis, we implement a quantum gate-based algorithm that replicates the behaviour of the Quantum PageRank algorithm. We present a comprehensive analysis with the Szegedy quantum walk formalism. The implementation procedure is based in the quantum circuit model of quantum computing. Here, we review a Quantum PageRank algorithm and illustrate the main findings. We show the behaviour of the quantum PageRank algorithm using the IBM’s Q experience framework for quantum computing. We investigate the behavior of the Quantum PageRank algorithm using quantum walks by giving explicit connections with corresponding classical algorithm. We make a comparative analysis of our findings and discuss the capabilities of a quantum computing platform applied to the Quantum PageRank algorithm. Within the restrictions imposed by hardware, we implement a multiple-controlled gate using ancilla qubits and all other elements required for implementing our quantum algorithm.
The PageRank of a web page denotes popularity of a web page, higher the PageRank wider the popularity. The explosion of the number of web pages propel us to fasten the search time. The quantum version of Google PageRank has recently been investigated by various groups [1], [2] and shown to be quadratically faster in time than the classical PageRank algorithm. In this paper, we follow Quantum PageRank Class defined in [2]. We have modelled the web pages as quantum states and the search as a quantum stochastic walk. The evolution of the density matrix is computed using the Kossakowski-Lindblad master equation, which has reversible and irreversible evolution terms. The reversible term gives the coherent evolution, while the irreversible term adds noise to the system. The stochastic convergence of the diagonal elements of the density matrix gives the Quantum PageRank values, and to observe this it is essential to get consistent PageRank ordering, after the quantum fluctuations have been stabilized (insignificant). In our paper, we propose a method for faster convergence of the Quantum PageRanks by adding limited quantity of noise values during computation of the Kossakowski-Lindblad master equation, and the results obtained are an improvement over [2], where the quantum fluctuations do not stabilize and the ordering of PageRanks is not consistent. Addition of noise in limited amount during computation helps in limiting quantum fluctuations and in convergence of the Quantum PageRanks.
Abstract We present a quantum algorithm for finding the minimum of a function based on multistep quantum computation, and apply the algorithm for solving optimization problems with continuous variables. We construct the state space of the problem by discretizing the variables of the problem, and divide the state space according to the function values of the vectors of the state space. By comparing the function values of the vectors with a series of threshold values in decreasing order, we construct a sequence of Hamiltonians where the search space of a Hamiltonian is nested in that of the previous one. By applying a multistep quantum computation process for finding the ground state of the last Hamiltonian, the optimal vector of the state space of the problem is located in a small search space and can be determined efficiently. One of the most difficult problems in optimization algorithms is that a trial vector is trapped in a deep local minimum while the global minimum is missed, this problem can be alleviated in our algorithm and the run time is proportional to the number of the steps of the algorithm, provided that the reduction rate of the search spaces is polynomial large. We discuss the implementation of the algorithm and test the algorithm for some test functions.
We propose an adiabatic quantum algorithm for generating a quantum pure state encoding of the PageRank vector, the most widely used tool in ranking the relative importance of internet pages. We present extensive numerical simulations which provide evidence that this algorithm can prepare the quantum PageRank state in a time which, on average, scales polylogarithmically in the number of web pages. We argue that the main topological feature of the underlying web graph allowing for such a scaling is the out-degree distribution. The top-ranked log(n) entries of the quantum PageRank state can then be estimated with a polynomial quantum speed-up. Moreover, the quantum PageRank state can be used in "q-sampling" protocols for testing properties of distributions, which require exponentially fewer measurements than all classical schemes designed for the same task. This can be used to decide whether to run a classical update of the PageRank.
This article presents a new quantum PageRank algorithm on graphs using discrete-time open quantum walks. Google's PageRank is a widely used algorithm for ranking the web pages on the world wide web in classical computation. From a broader perspective, it is also a fundamental measure for quantifying the importance of vertices in a network. Similarly, the new quantum PageRank also serves to quantify the significance of a network's vertices. In this work, we extend the concept of discrete-time open quantum walk on arbitrary directed and undirected graphs by utilizing the Weyl operators as Kraus operators. This new model of quantum walk is useful for building up the quantum PageRank algorithm, discussed in this article. We compare the classical PageRank and the newly defined quantum PageRank for different types of complex networks, such as the scale-free network, Erdős-Rényi random network, Watts-Strogatz network, spatial network, Zachary Karate club network, GNC, GN, GNR networks, Barabási and Albert network, etc. In addition, we study the convergence of the quantum PageRank process and its dependency on the damping factor α. We observe that this quantum PageRank procedure is faster than many other proposals reported in the literature.
In classical computation, a problem can be solved in multiple steps where the calculated results of each step can be copied and used repeatedly.However, in quantum computation, it is difficult to realize a similar multistep computation process because the no-cloning theorem forbids making copies of an unknown quantum state perfectly.We find a method based on a quantum resonant transition to protect and reuse an unknown quantum state that encodes the calculated results of an intermediate step without copying it, and present a quantum algorithm that solves a problem via multistep quantum computation.We demonstrate that this algorithm can solve a type of structured search problems efficiently.