Adiabatic quantum algorithm for search engine ranking
arXiv:1109.6546 · doi:10.1103/PhysRevLett.108.230506
Abstract
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 webpages. 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 entries of the quantum PageRank state can then be estimated with a polynomial quantum speedup. 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.
7 pages, 5 figures; closer to published version
References in corpus (13)
- Quantum algorithm for solving linear systems of equations
- Bounds for the adiabatic approximation with applications to quantum computation
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Controllable coupling of superconducting flux qubits
- Quantum Adiabatic Brachistochrone
- Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
- Accuracy vs run time in adiabatic quantum search
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- Spectral properties of the Google matrix of the World Wide Web and other directed networks
- Delocalization transition for the Google matrix
- On the adiabatic condition and the quantum hitting time of Markov chains
Cited by in corpus (48)
- A variational eigenvalue solver on a quantum processor
- Adiabatic Quantum Computing
- Perspectives of quantum annealing: Methods and implementations
- Quantum generalisation of feedforward neural networks
- Adiabatic Quantum Simulation of Quantum Chemistry
- Complex Networks from Classical to Quantum
- Quantum Navigation and Ranking in Complex Networks
- Interdisciplinary and physics challenges of Network Theory
- Quantum Perceptron Models
- Unitary quantum perceptron as efficient universal approximator
- Quantum Google in a Complex Network
- Quantum algorithm for association rules mining
- Quantum algorithm for association rules mining
- Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
- Complex Quantum Network Geometries: Evolution and Phase Transitions
- Coherent controlization using superconducting qubits
- Ground State Spin Logic
- Universally Optimal Noisy Quantum Walks on Complex Networks
- Degree Distribution in Quantum Walks on Complex Networks
- Complex Quantum Networks: a Topical Review
- Supersymmetric multiplex networks described by coupled Bose and Fermi statistics
- Complex Quantum Networks: From Universal Breakdown to Optimal Transport
- Universality at Breakdown of Quantum Transport on Complex Networks
- Phase transition of light on complex quantum networks
- Thermodynamic formalism for dissipative quantum walks
- An adiabatic Leakage Elimination Operator in experimental framework
- Information sharing in Quantum Complex Networks
- Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
- Spatial Search Algorithms on Hanoi Networks
- Error measurements for a quantum annealer using the one-dimensional Ising model with twisted boundaries
- Quantum adiabatic brachistochrone for open systems
- Toward a quantum computing algorithm to quantify classical and quantum correlation of system states
- Discrete-Time Open Quantum Walks for Vertex Ranking in Graphs
- Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
- Quantum annealing with pairs of molecules as qubits
- Learning Simon's quantum algorithm
- Power law scaling for the adiabatic algorithm for search engine ranking
- Unifying framework for quantum simulation algorithms for time-dependent Hamiltonian dynamics
- Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine
- Adiabatic quantum computing with parameterized quantum circuits
- Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
- Quantum algorithm for PageRank computation through multistep quantum resonant transitions
- Large-scale Sustainable Search on Unconventional Computing Hardware
- Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers
- Renormalization and small-world model of fractal quantum repeater networks
- Two-Hop Walks Indicate PageRank Order
- Quantum Google Algorithm: Construction and Application to Complex Networks
- Improving adiabatic quantum factorization via chopped random-basis optimization