PaperlayerView exact revision on arXiv

Source-linked AI summary

Google in a Quantum Network

G. D. Paparo, M. A. Martin-Delgado

arXiv:1112.2079v2quant-phcond-mat.stat-mechcs.NI

TL;DR

Quantum PageRank must preserve directed web structure, although quantizing directed graphs can raise unitarity problems. The paper defines an admissible class and constructs a Markov-chain-based protocol; simulations report that quantum fluctuations can change classical page rankings.

  • Problem

    Quantizing directed graphs for quantum PageRank can produce unitarity problems, while the directed structure must be preserved.

    Source: §I · p. 1, §VI · p. 11

  • Method

    The authors define a broad class and construct an explicit directed-graph protocol by quantizing Markov chains, with the studied multilevel-system instance attaching quantum states to network links.

    Source: §I · p. 2, §VI · p. 11

  • Results

    Quantum fluctuations make page importance time-dependent and can change the classical hierarchy both instantaneously and in mean values.

    Source: §I · p. 2

  • Takeaways & Limitations

    For the directed binary tree, quantum fluctuations can enhance the root page’s importance without changing the network topology.

    Source: §VI · p. 11

Abstract

from arXiv · show

We introduce the characterization of a class of quantum PageRank algorithms in a scenario in which some kind of quantum network is realizable out of the current classical internet web, but no quantum computer is yet available. This class represents a quantization of the PageRank protocol currently employed to list web pages according to their importance. We have found an instance of this class of quantum protocols that outperforms its classical counterpart and may break the classical hierarchy of web pages depending on the topology of the web.

I. INTRODUCTION

The introduction defines an admissible class of quantum PageRanks for quantum-network settings and presents a valid, nontrivial instance. Its time-dependent importance values can alter the classical page hierarchy, motivating temporal averages for a fixed ranking.

I. INTRODUCTION

  • PageRank is presented as a key tool for searching the changing web, while practical quantum networks are an active research goal with early realizations and proposals.The introduction cites multiple approaches, including entanglement connections requiring quantum repeaters and quantum percolation protocols.Source: §I · p. 1
  • The proposed quantum webpages are quantum-network nodes such as quantum memories, and need only store and read quantum states rather than use a fully fledged quantum computer.The paper motivates this setting by the prospect of quantum networks before a scalable quantum computer is available.Source: §I · pp. 1–2
  • The class requires preservation of directed graph structure, quantum PageRanks summing to 1, a quantized Markov chain, and polynomial-time classical computation.The classical-computation requirement is more demanding than quantum polynomial-time feasibility because it requires classical simulation.Source: §I · pp. 1–2
  • The authors construct a valid class member, while noting that the broad class includes diverse network realizations and their studied instance uses a multilevel system with quantum states attached to links.They describe this instance as a first nontrivial case in which sharp deviations from classical PageRank can be found.Source: §I · p. 2
  • The paper distinguishes strong hierarchy preservation, weak preservation of the top-ranked node, and outperforming the highest classical PageRank.Outperforming can be instantaneous or based on average values.Source: §I · p. 2
  • Quantum fluctuations can change the classical page hierarchy instantaneously and in mean values.In the described dynamics, a pair of pages can reverse relative importance over time; temporal averages and standard mean deviations provide a fixed output list.Source: §I · p. 2

II. CLASSICAL PAGERANK

Classical PageRank ranks pages returned by web searches, distinguishing it from earlier approaches based on subjective judgments of page content. The section describes ranking as necessary when searches yield many matching pages.

II. CLASSICAL PAGERANK

  • PageRank is described as objective and dynamic, unlike earlier approaches based on subjective page-content criteria that were static.The section attributes Google’s introduction to Brin and Page in 1998.Source: §II · p. 2
  • Search engines retrieve and index web pages, then return pages containing or semantically related to a user's search phrase.Source: §II · pp. 2–3
  • The section says Google claims to index 50 billion pages, making ranking important when many pages match common search terms.It states that roughly 95% of page text comes from 10,000 words and links PageRank’s success to ranking page importance.Source: §II · p. 3

A. Google PageRank

PageRank ranks pages through link structure and computes importance as a stationary vector. The section patches the classical procedure to address dangling pages, reducible graphs, and failure of power-method convergence.

A. Google PageRank

  • PageRank treats a page’s importance as the sum of contributions from pages linking to it, weighted by their outgoing links.The method recasts the ranking problem as finding an eigenvector of the hyperlink matrix.Source: A. Google PageRank · p. 3
  • The power method iterates a candidate vector to find the stationary PageRank vector, but dangling nodes can make its output the null vector.A dangling node is a page with no outlinks.Source: A. Google PageRank · p. 3, B. Patching the Algorithm · p. 3

B. Patching the Algorithm

  • Replacing each dangling-node column with entries of 1/n prevents the null-vector failure by making the dangling page link virtually to every page.The added links give the disconnected graph very low-weight artificial connections.Source: B. Patching the Algorithm · p. 3
  • For stochastic E, power-method convergence depends on λ2: when |λ2|<1 it converges, and smaller |λ2| makes convergence faster; with |λ2|=1, the cited example fails from I0=(1,0,0,0)^T.Source: B. Patching the Algorithm · pp. 3–4
  • A reducible hyperlink matrix can drain importance from one subgraph, leaving linked pages with zero importance; strong connectivity is required for irreducibility.In the example, the iteration yields I = (0, 0, 3/5, 2/5)^t.Source: B. Patching the Algorithm · p. 4

1. The Patched Algorithm

The patched PageRank process models a surfer who follows web links with probability α and jumps randomly otherwise. Its Google Matrix is irreducible and primitive, yielding a unique stationary vector computable by the power method.

1. The Patched Algorithm

  • The surfer follows the web’s stochastic matrix E with probability α and jumps to any page at random with probability 1 − α.The resulting transition matrix is G = αE + (1 − α)N1.Source: §1 · p. 4
  • The Google Matrix G is irreducible and primitive, so it has a unique stationary vector that can be calculated with the power method.The result does not depend on the initial vector I0.Source: §1 · p. 4
  • The parameter α is free and must be tuned; because |λ2| ≤ α, choosing α close to zero would ignore the web structure described by E, while Brin and Page chose α = 0.85 to optimize the calculation.Source: §1 · p. 4

2. Formulation as a Random Walk

The paper interprets classical PageRank as a random walk and uses that transition-process view to motivate quantum versions. A direct site-based quantization is not viable, while several enlarged-space approaches are available, including the chosen Szegedy construction.

2. Formulation as a Random Walk

  • PageRank can be interpreted as the fraction of time a diffusing walker spends on each page, or equivalently the probability of finding the walker there.The Google Matrix describes the transition between successive time steps.Source: §2 · pp. 4–5
  • The Markov-chain interpretation of the Google Matrix provides the basis for the paper’s subsequent quantization methods.The matrix links one time step to the next as a conditional probability.Source: §2 · p. 5

III. QUANTUM PAGERANKS

  • Discrete-time quantum walks have been studied in several contexts, and the paper first illustrates possible quantizations on a line before generalizing to graphs.The text notes earlier work by Feynman and later rediscoveries.Source: §III · p. 5, Figure 3 · p. 5
  • The naive line-walk proposal maps integer-indexed sites to Hilbert-space states and defines page importance using the diffused quantum state.The nodes are represented by basis states |i⟩.Source: §III · p. 5
  • Directly quantizing the time-step evolution operator is not viable because the resulting operator is not unitary.The paper identifies nonzero overlap after applying U†U to initially orthogonal states as the issue.Source: §III · p. 5
  • Three ways to enlarge the Hilbert space are adding a coin space, using oriented edges with scattering centers, or applying Szegedy’s Markov-chain procedure.A coin space encodes left and right motion.Source: §III · p. 5
  • The paper pursues Szegedy’s procedure because it yields a valid quantization of Google PageRank satisfying the stated properties.The approach quantizes the Markov-chain interpretation of the Google Matrix.Source: §III · p. 5, §2 · p. 5

3. Szegedy’s Quantization of Markov Chains

Szegedy’s construction represents a Markov chain on directed edges and builds a quantum-walk step from a reflection and a swap. The stochastic transition probabilities determine the edge-state amplitudes, and the resulting step is unitary.

3. Szegedy’s Quantization of Markov Chains

  • For an N-vertex Markov chain, the quantum walk uses a Hilbert space spanned by directed-edge states in CN ⊗ CN.The order of the two spaces matters because the graph is directed.Source: §3 · p. 5
  • Each |ψj⟩ is a superposition of edges leaving vertex j, with amplitudes given by the square roots of the stochastic-matrix weights.Stochasticity ensures the vectors |ψj⟩ are normalized.Source: §3 · p. 5
  • The operator built from the |ψj⟩ vectors projects onto their span, and the quantum-walk step combines that projection with the swap operator.The swap exchanges the two registers.Source: §3 · p. 6
  • The step operator is unitary because the swap is unitary and the projector squares to itself; it acts as a coin flip followed by a swap.The walk’s spectrum can be analyzed in relation to the original stochastic matrix’s spectrum.Source: §3 · p. 6

4. Solving the Eigenvalue Problem for the Walk Operator

The walk spectrum is related to the classical stochastic matrix through an invariant subspace, where the two-step operator contains the nontrivial dynamics. This structure also reduces the spectral work needed for Quantum PageRank.

4. Solving the Eigenvalue Problem for the Walk Operator

  • The walk’s spectrum is related to the original stochastic matrix’s spectrum, which also shapes the associated classical random walk.The analysis proceeds by defining the symmetric matrix D and mapping its eigenvectors into the quantized walk space.Source: §4 · p. 6
  • The span of the vectors |ψj⟩ and S|ψj⟩ is invariant under U and forms the subspace where the walk acts nontrivially.The orthogonal complement has U acting as −S, with eigenvalues ±1.Source: §4 · pp. 6–7
  • Under U^2, the Hilbert space splits into the dynamical subspace and its orthogonal complement, where the operator acts trivially.The dynamical subspace is spanned by |ψj⟩ and S|ψj⟩.Source: §4 · p. 7
  • The two-step walk’s dynamical subspace has dimension at most 2N, while the full edge-space Hilbert space has dimension N^2.The orthogonal complement has at least N^2 − 2N eigenvalues equal to 1 under U^2, allowing computational resources to be saved when calculating Quantum PageRank.Source: §4 · p. 7

IV. A QUANTIZATION OF GOOGLE PAGERANK

The paper defines Quantum PageRank as a time-dependent page importance derived from a quantum walk on the directed network. It gives a spectral calculation protocol and uses time averages and fluctuations to summarize the evolving scores.

IV. A QUANTIZATION OF GOOGLE PAGERANK

  • Quantum PageRank assigns a page an instantaneous importance from the probability of finding the quantum walker at that node after m time steps.The coherent walk evolves over directed links, and projection onto the destination-node space yields the page’s instantaneous score.Source: §IV · p. 7
  • The instantaneous scores sum to one at every time, so each can be interpreted as a page’s relative importance.This preserves the normalization condition and reproduces the classical sum rule.Source: §IV · pp. 7–8
  • Time averages and standard deviations summarize each page’s importance and the fluctuations caused by coherent evolution.The paper introduces the average importance to integrate out those fluctuations.Source: §IV · pp. 7–8
  • The protocol forms the Google matrix and D, finds their relevant spectra, then extracts instantaneous, mean, and standard-deviation PageRank values.It uses eigenvectors of the two-step walk operator U^2 in the dynamical subspace.Source: §IV · p. 8

V. RESULTS: SIMULATIONS FOR QUANTUM PAGERANKS

The paper tests its quantum PageRank against the classical algorithm using simulations on two directed network structures. These are a three-level binary tree and a small general graph without special properties.

V. RESULTS: SIMULATIONS FOR QUANTUM PAGERANKS

  • The simulations assess how Quantum PageRank behaves on specific networks by comparing it with classical PageRank.Source: §V · p. 8
  • The simulations test Quantum PageRank against the classical algorithm on a three-level binary tree and a small general directed graph.The tree and general graph are treated in separate subsections.Source: §V · p. 8
  • The tree represents an intranet, while the general graph has no particular symmetry or special property.Each case is used to examine how the quantum algorithm behaves compared with classical PageRank.Source: §V · p. 8

A. Case Study 1: A Tree Graph

In the three-level directed tree, the quantum score of the home page exceeds its classical counterpart at some times, while quantum fluctuations remain bounded and include the classical value. Time-averaged scores preserve the classical hierarchy, and coarse-grained evolution shows a visible envelope for each node.

A. Case Study 1: A Tree Graph

B. Case Study 2: A General Graph

On a general directed graph, the quantum PageRank can temporarily exceed the classical score of the classically highest-ranked page, while instantaneous and averaged rankings need not preserve the classical hierarchy. Coarse-grained results still distinguish pages with the highest and lowest classical importance.

B. Case Study 2: A General Graph

VI. CONCLUSIONS

The paper proposes a class of quantum PageRank protocols and constructs an explicit directed-graph protocol by quantizing Markov chains, addressing unitarity difficulties. Simulations find topology-dependent ranking behavior, including instantaneous outperformance and changes to the classical hierarchy.

VI. CONCLUSIONS

  • The paper proposes a class of quantum versions of classical PageRank and constructs an explicit protocol by quantizing Markov chains for directed graphs.The construction addresses unitarity problems that can arise when handling quantum versions of directed graphs.Source: §VI · p. 11
  • The protocol is tested on two networks: a directed binary tree representing an intranet and a general directed graph without a specific structure.Source: §VI · p. 11
  • For the directed binary tree, the root's quantum PageRank instantaneously exceeds its classical value through quantum fluctuations, without changing network topology.Instantaneous node rankings violate the classical hierarchy, but mean values with standard deviation preserve it.Source: §VI · p. 11
  • For the general directed graph, the page with the highest classical PageRank sometimes has a higher quantum value, constituting instantaneous outperformance.Source: §VI · p. 11

Related papers

Loading 1112.2079v2…