Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1310.6676

Comment on "Adiabatic Quantum Algorithm for Search Engine Ranking"

Jonathan E. Moussa

Published Oct 24, 2013• 1 citation
arXivHTMLPDF

Abstract

In their Letter, Garnerone et al. claim that an adiabatic quantum algorithm can extract information about a PageRank vector with either a polynomial or exponential reduction in time resources over the classical algorithm with comparable space resources. Here we argue that the quantum algorithm offers no obvious advantage over the classical algorithm and fails to preserve the fundamental stability property of the classical PageRank algorithm.

DOI
10.48550/arxiv.1310.6676

Related papers

Adiabatic Quantum Algorithm for Search Engine Ranking

Silvano Garnerone, Paolo Zanardi, Daniel A. Lidar

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.

arXiv:1109.6546•Physical Review Letters•Jun 4, 2012•111 citations

Variational Quantum PageRank

Sims, Christopher

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

arXiv:2304.12232•Apr 19, 2023•0 citations

How powerful is adiabatic quantum computation?

W. van Dam, M. Mosca, U. Vazirani

The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.

arXiv:quant-ph/0206003•Annual Symposium on Foundations of Computer Science•Jan 1, 2001•236 citations

An Enhanced Quantum PageRank Algorithm Integrated with Quantum Search

Huiquan Wang, Junjie Wu, Xuejun Yang +2 more

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.

International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS)•Jul 1, 2014•5 citations

Power-law scaling for the adiabatic algorithm for search-engine ranking

Adam Frees, John King Gamble, Kenneth Rudinger +4 more

An important method for search engine result ranking works by finding the principal eigenvector of the ``Google matrix.'' Recently, a quantum algorithm for generating this eigenvector as a quantum state was presented, with evidence of an exponential speedup of this process for some scale-free networks. Here we show that the run time depends on features of the graphs other than the degree distribution, and can be altered sufficiently to rule out a general exponential speedup. According to our simulations, for a sample of graphs with degree distributions that are scale-free, with parameters thought to closely resemble the Web, the proposed algorithm for eigenvector preparation does not appear to run exponentially faster than the classical case.

arXiv:1211.2248•Physical Review A•Sep 5, 2013•4 citations

Randomized SearchRank: A semiclassical approach to a quantum search engine

Sergio A. Ortega, Miguel Angel Martin-Delgado

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

arXiv:2401.01554•Physical Review Research•Oct 4, 2024•3 citations
In their Letter, Garnerone et al. claim that an adiabatic quantum algorithm can extract information about a PageRank vector with either a polynomial or exponential reduction in time resources over the classical algorithm with comparable space resources. Here we argue that the quantum algorithm offers no obvious advantage over the classical algorithm and fails to preserve the fundamental stability property of the classical PageRank algorithm.
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.
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 authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.
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.
An important method for search engine result ranking works by finding the principal eigenvector of the ``Google matrix.'' Recently, a quantum algorithm for generating this eigenvector as a quantum state was presented, with evidence of an exponential speedup of this process for some scale-free networks. Here we show that the run time depends on features of the graphs other than the degree distribution, and can be altered sufficiently to rule out a general exponential speedup. According to our simulations, for a sample of graphs with degree distributions that are scale-free, with parameters thought to closely resemble the Web, the proposed algorithm for eigenvector preparation does not appear to run exponentially faster than the classical case.
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