The Google's PageRank algorithm is one of the most famous algorithms in data mining. A quantum version of this algorithm has been proposed in 2012. It is a meaningful step towards the quantum search engine but it can not search solutions. In this paper, we integrate a special operator of quantum search into the quantum PageRank algorithm to make a new quantum algorithm. We called it the Search Rank algorithm. This new algorithm is able to search solutions and rank results according to their importance at the same time. It is the first algorithm possessing this ability as far as we know. And it outperforms all classical algorithms when searching an unsorted database.
The Google's PageRank algorithm is one of the most famous algorithms in data mining. A quantum version of this algorithm has been proposed in 2012. It is a meaningful step towards the quantum search engine but it can not search solutions. In this paper, we integrate a special operator of quantum search into the quantum PageRank algorithm to make a new quantum algorithm. We called it the Search Rank algorithm. This new algorithm is able to search solutions and rank results according to their importance at the same time. It is the first algorithm possessing this ability as far as we know. And it outperforms all classical algorithms when searching an unsorted database.
The PageRank algorithm is used to rank web pages by their importance. Since its development, the PageRank algorithm is a critical and fundamental part of search engines today. PageRank is a graph-based algorithm that ranks pages based on how many other pages link to them. This work develops a variational quantum version of the PageRank algorithm and compares the performance of the two algorithms. It is found that quantum PageRank performs better at ranking websites than the normal PageRank algorithm
The quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. However, this algorithm loses its functionality when the N / M ratio between the network size N and the number of marked nodes M is sufficiently large. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk. To maintain the same time complexity as the quantum SearchRank algorithm we propose a simplification of the algorithm. This new algorithm is called randomized SearchRank, since it corresponds to a quantum walk over a randomized mixed state. The performance of the SearchRank algorithms is first analyzed on an example network and then statistically on a set of different networks of increasing size and different number of marked nodes. On the one hand, to test the search ability of the algorithms, it is computed how the probability of measuring the marked nodes decreases with N / M for the quantum SearchRank, but remarkably it remains at a high value around 0.9 for our semiclassical algorithms, solving the quantum SearchRank problem. The time complexity of the algorithms is also analyzed, obtaining a quadratic speedup with respect to the classical ones. On the other hand, the ranking functionality of the algorithms has been investigated, obtaining a good agreement with the classical PageRank distribution. Finally, the dependence of these algorithms on the intrinsic PageRank damping parameter has been clarified. Our results suggest that this parameter should be below a threshold so that the execution time does not increase drastically. Published by the American Physical Society 2024
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.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
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.
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.