Quantum PageRank

Overview

PageRank is the algorithm that Google's founders used to rank web pages by importance. It models a random surfer who follows links from page to page, and ranks pages by how often the surfer visits them in the long run. Quantum PageRank replaces the random surfer with a quantum walker, a particle that moves in superposition across the network.

Two lines of work share the name. Paparo and Martin-Delgado defined a quantum PageRank based on a quantum walk whose time-averaged visit probabilities rank the nodes, and found that the resulting ranking differs from the classical one, especially for nodes with similar scores. Garnerone, Zanardi, and Lidar proposed an adiabatic quantum algorithm that estimates the ranks of the top nodes quickly. Neither has been shown to give a proven speedup, and neither is used in production search.

The problem it solves

Ranking nodes in a network (like web pages) by importance, based on the structure of links between them.

History and background

PageRank was described by Sergey Brin and Larry Page in 1998 and builds on the mathematics of Markov chains. In 2012 Paparo and Martin-Delgado published Google in a Quantum Network in Scientific Reports, introducing a quantum walk on the directed graph of the web based on Szegedy's quantization of Markov chains. Sánchez-Burillo and coauthors published related work on quantum navigation and ranking in complex networks in the same year.

Also in 2012, Garnerone, Zanardi, and Lidar published an adiabatic quantum algorithm for search engine ranking in Physical Review Letters. Their numerical results on scale-free networks suggested that the top-ranked pages could be identified with a runtime that grows polylogarithmically in the number of pages, though that rests on numerical evidence and assumptions. Later studies, including Paparo, Müller, Comellas, and Martin-Delgado in 2013 and comparative analyses in 2017, examined how quantum PageRank behaves on different network types and how robust it is to noise.

How it works

Replaces the classical random walk underlying PageRank with a quantum walk, which explores the network differently and can reveal structural features classical PageRank misses, particularly for networks with certain symmetries.

Classical PageRank defines a transition matrix in which each page passes its importance to the pages it links to, mixed with a small chance of jumping to a random page. This is the Google matrix. The ranking is its stationary distribution, found by repeated multiplication, which is the power method.

A quantum walk on the same network moves a particle in a superposition of edges instead of choosing one link at random. Interference between paths changes how probability spreads. After running the walk for a long time, the time-averaged probability at each node serves as the quantum PageRank. Nodes whose classical scores are nearly equal can have different quantum scores because interference favors some structural features.

The adiabatic approach encodes the Google matrix in a Hamiltonian whose ground state corresponds to the stationary distribution, and slowly evolves toward it. The quantum state then holds the rank vector in its amplitudes, from which the top-ranked nodes can be sampled quickly if the spectral gap is large.

Step by step

1. Represent the web or network as a directed graph and build the Google matrix, mixing link-following with a damping factor.
2. Define the quantum walk by applying Szegedy's construction to the Markov chain, giving a unitary on pairs of nodes.
3. Prepare an initial state, evolve the walk for many steps, and record the probability of finding the walker at each node at each time.
4. Average the probabilities over time to obtain the quantum PageRank vector, and sort the nodes by their values.
5. Alternatively, in the adiabatic version, prepare the ground state of an initial Hamiltonian and evolve slowly toward one that encodes the stationary distribution, then sample the result.
6. Compare the ordering with the classical PageRank, in particular for nodes that the classical method ranks almost equally.

A worked example

Consider a small network of six pages where two pages receive similar numbers of incoming links, giving them nearly identical classical PageRank scores. In the quantum walk, the two pages sit at different places in the network's structure, so interference gives them different long-term visit probabilities, and the quantum ranking breaks the tie.

Researchers have also reported that for some networks the quantum ranking of the highest-ranked nodes is more strongly separated than the classical one, which could help in distinguishing important pages. Whether that matches human notions of importance, or helps real search, has not been demonstrated.

Complexity and resources

What hardware it needs

• Fault-tolerant hardware for large networks, since the walk or adiabatic evolution is deep.
• Efficient quantum access to the graph structure, for example through quantum memory.
• For small demonstrations, a few qubits can encode networks of a handful of nodes.

Applications

• Studying network structure and ranking nodes in social, biological, and citation networks.
• Distinguishing nodes that classical PageRank scores as equal.
• Research on quantum walks and Markov chains in complex networks.

Limitations and caveats

• No proven speedup over classical PageRank, which is already very efficient.
• Reading out the whole rank vector would need as many measurements as nodes, removing any exponential gain.
• The quantum ranking is not necessarily better, only different.
• Real search engines use many signals beyond link structure.

Common misconceptions

• Quantum PageRank is not used by Google or any search engine.
• It does not guarantee a faster ranking. The speedup claims are numerical and limited to the top nodes.

How it compares

• Classical PageRank uses the power method on the Google matrix, which converges in tens of iterations for web-scale graphs.
• Quantum walk search uses the same walk machinery to find marked nodes with a speedup.
• Quantum linear algebra could in principle compute the stationary distribution, but with similar caveats about input and output.

Real-world impact

Primarily a research tool for studying network structure differently than classical methods, rather than a faster drop-in replacement for existing web search ranking systems.

Why it matters

Quantum PageRank is a good example of using quantum walks for network analysis and of how a familiar algorithm can behave differently in the quantum setting. It has sparked work on quantum centrality measures and on how interference reveals network structure.

It is also a case study in being honest about advantage. A different result is not the same as a faster or better result.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Walk Algorithms
• Related algorithm: Quantum Walk Approaches to Graph Isomorphism
• Related algorithm: HHL Algorithm
• Related algorithm: Adiabatic Quantum Computation

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database