Quantum PageRank

Rank the nodes of a network with a quantum walk — evolving a continuous-time open-system process whose steady state encodes node importance. It is the quantum analogue of classical PageRank, and in one place it fills in exactly the blind spot the classical version leaves behind.

The problem it solves

Given a directed graph — web pages and hyperlinks, papers and citations, accounts and transfers — we want to know: which nodes are most "important"? The naive idea is to count incoming edges, but that is easy to game, and it ignores the fact that being pointed to by an important node should carry more weight than being pointed to by an unknown one. PageRank's core insight is to define importance recursively: a node's importance is the sum of the importances of the nodes that point to it.

Classical PageRank realises this recursion as a random walk on the graph: a "surfer" hops along outgoing edges at random, occasionally restarting from a random page. Each node's importance is the long-run occupation probability of the walk sitting on it. Quantum PageRank keeps this whole idea but replaces the classical random walk with a quantum walk.

Encoding the graph — the Google matrix

To feed the graph to the algorithm, we first build its stochastic matrix: normalise each node's outgoing edges uniformly to get one-step hopping probabilities. But a pure stochastic matrix has two defects — "dangling" nodes with no outgoing edges trap the walk, and isolated subgraphs cannot reach one another. PageRank patches both with a "teleportation" term: with probability α (typically 0.85) follow a link, and with probability 1−α teleport to an arbitrary node. The convex combination of the two is the Google matrix

G = α·S + (1−α)·(1/N)·𝟙

where S is the link matrix (with dangling nodes patched), 𝟙 is the all-ones matrix, and N is the number of nodes. Classical PageRank is then the principal eigenvector of G corresponding to eigenvalue 1.

Watch the convention: whether S is row- or column-stochastic decides whether the ranking is the left or right eigenvector, and references differ on this. The (1−α)·(1/N)·𝟙 term is exactly a uniform teleport — it sends weight to every node with equal probability.

From a classical walk to a quantum walk

A classical random walk is incoherent: every step is a probabilistic hop, with no phase and no interference. A quantum walk instead places the "surfer" in a superposition over many nodes, with each branch carrying a coherent complex amplitude that can interfere with the others. But a purely unitary quantum walk never settles into a steady state — it oscillates forever, and ranking demands a stable reading.

The remedy is to use an open-system quantum walk: encode the Google matrix into a Lindblad generator and layer a little dissipation on top of the coherent quantum evolution. Under a suitable Lindblad construction and connectivity/ergodicity conditions, the dissipation can drive the dynamics to converge to a steady state; the quantum coherence that survives gives that steady state a resolving power the classical version lacks. Integrating the resulting open-system dynamics, the steady-state occupation probability of each node gives the ranking.

Its relation to classical PageRank — and that blind spot

When dissipation dominates, the quantum PageRank ranking smoothly reduces to classical PageRank — the classical algorithm is a limiting case of the quantum one, not something it contradicts. Where the two genuinely diverge is on the symmetric and degenerate nodes that the classical algorithm cannot handle. Quantum PageRank may distinguish some nodes that score identically classically but differ in higher-order connectivity structure or dynamical response; however, nodes protected by a strict graph automorphism symmetry should not receive different scores from any ranking method that does not break that symmetry. Where such symmetry is only approximate, the phase interference of the quantum walk is sensitive to the wider connectivity pattern a node sits in, so it can break near-ties and produce differentiated rankings.

An honest look at its usefulness

• This is a continuous-time simulation problem, not an algorithm with a known speedup. Today's quantum PageRank is implemented mainly by simulating open-system dynamics; for graphs at real network scale there is no proven asymptotic speedup over classical sparse-matrix power iteration.
• Encoding the graph is itself a cost. Loading an N-node graph into a quantum state and reading out N occupation probabilities can eat up any gain the evolution phase might offer — the same "data in, data out" bottleneck that haunts many quantum algorithms.
• Its value lies in ranking semantics, not speed. What is truly unique is its ability to break degeneracy, not to compute the ranking faster. It is better understood as a semantically enriched variant of classical PageRank than as an accelerated version of it.
• The choice of α still matters. As in the classical version, the teleportation probability 1−α tunes how sensitive the ranking is to graph structure; it is a modelling choice that does not disappear just because the walk became quantum.

The algorithm, step by step

1. Build the Google matrix G from the graph (the link matrix plus a teleportation term, weighted by α).
2. Encode G into a Lindblad generator so the coherent quantum walk carries a little dissipation.
3. Starting from a uniform initial state, integrate the open-system dynamics over time.
4. Read out the steady-state occupation probability of each node and sort by it as the importance score.

Seeing it in code

Read the snippet below against the theory above: from_google_matrix(G, alpha=0.85) is exactly what turns the Google matrix with its teleportation term into a Lindblad generator L; Schedule supplies the time steps for the integration; evolve propagates the open-system dynamics starting from uniform_state; and final_occupations() reads out the steady-state occupation probabilities — the node importance scores.

import qalgora
from qalgora import operators
import numpy as np

# build the Lindblad generator from the graph's Google matrix G
L = operators.from_google_matrix(G, alpha=0.85)

schedule = qalgora.Schedule(steps=np.linspace(0, 10, 100), parameters=["t"])
result = qalgora.evolve(L, dimensions=dims, schedule=schedule,
                        initial_state=uniform_state)
ranking = result.final_occupations()      # node importance scores