Discrete-time quantum walk algorithm for ranking nodes on a network
arXiv:1905.06575 · doi:10.1007/s11128-020-02650-4
Abstract
We present a quantum algorithm for ranking the nodes on a network in their order of importance. The algorithm is based on a directed discrete-time quantum walk, and works on all directed networks. This algorithm can theoretically be applied to the entire internet, and thus can function as a quantum PageRank algorithm. Our analysis shows that the hierarchy of quantum rank matches well with the hierarchy of classical rank for directed tree network and for non-trivial cyclic networks, the hierarchy of quantum ranks do not exactly match to the hierarchy of the classical rank. This highlights the role of quantum interference and fluctuations in networks and the importance of using quantum algorithms to rank nodes in quantum networks. Another application this algorithm can envision is to model the dynamics on networks mimicking the chemical complexes and rank active centers in order of reactivities. Since discrete-time quantum walks are implementable on current quantum processing systems, this algorithm will also be of practical relevance in analysis of quantum architecture.
10 Pages, 11 figures
References in corpus (52)
- The Quantum Internet
- A variational eigenvalue solver on a quantum processor
- Hierarchical organization of modularity in metabolic networks
- Classification of topological insulators and superconductors in three spatial dimensions
- Quantum random walks - an introductory overview
- Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
- Field test of quantum key distribution in the Tokyo QKD Network
- Universal computation by quantum walk
- Quantum walks of correlated particles
- Quantum walks: a comprehensive review
- Quantum repeaters based on entanglement purification
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Photons Walking the Line: A quantum walk with adjustable coin operations
- Exploring Topological Phases With Quantum Walks
- From quantum cellular automata to quantum lattice gases
- Realization of a quantum walk with one and two trapped ions
- Universal quantum computation using the discrete time quantum walk
- Quantum Memories. A Review based on the European Integrated Project "Qubit Applications (QAP)"
- Quantum walk of a trapped ion in phase space
- Universal computation by multi-particle quantum walk
- Discrete single-photon quantum walks with tunable decoherence
- Diverging Entanglement Length in Gapped Quantum Spin Systems
- Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
- Bulk--Boundary Correspondence for Chiral Symmetric Quantum Walks
- Localizable Entanglement
- Telecommunication-wavelength solid-state memory at the single photon level
- Dirac and Weyl Equations on a Lattice as Quantum Cellular Automata
- One-Dimensional Three-State Quantum Walk
- Log-Networks
- Outline of the SECOQC Quantum-Key-Distribution Network in Vienna
- Google in a Quantum Network
- Relativistic quantum walks
- Relationship Between Quantum Walk and Relativistic Quantum Mechanics
- Quantum Navigation and Ranking in Complex Networks
- Classical approach to the graph isomorphism problem using quantum walks
- Derivation of the Dirac Equation from Principles of Information Processing
- Quantum Google in a Complex Network
- Quantum Walks in artificial electric and gravitational Fields
- The topological classification of one-dimensional symmetric quantum walks
- Two-component Dirac-like Hamiltonian for generating quantum walk on one-, two- and three-dimensional lattices
- Approaches for a quantum memory at telecommunication wavelengths
- Free Dirac evolution as a quantum random walk
- QKD in Standard Optical Telecommunications Networks
- Spectral properties of the Google matrix of the World Wide Web and other directed networks
- Dirac Quantum Cellular Automaton from Split-step Quantum Walk
- Faster transport with a directed quantum walk
- Supersymmetric polarization anomaly in photonic discrete-time quantum walks
- Bounds on the dynamics of periodic quantum walks and emergence of the gapless and gapped Dirac equation
- Entanglement in Valence-Bond-Solid States
- Asymptotic properties of the Dirac quantum cellular automaton
- Continuous limits of linear and nonlinear quantum walks
- The Witten Index for 1D Supersymmetric Quantum Walks with Anisotropic Coins
Cited by in corpus (18)
- Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer
- Universal quantum computing using single-particle discrete-time quantum walk
- Efficient implementation of discrete-time quantum walks on quantum computers
- Quantum direct communication protocol using recurrence in k-cycle quantum walk
- Quantum circuits for the realization of equivalent forms of one-dimensional discrete-time quantum walks on near-term quantum hardware
- Quantum walks on random lattices: Diffusion, localization and the absence of parametric quantum speed-up
- Multi-qubit quantum computing using discrete-time quantum walks on closed graphs
- Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations
- Circuit Implementation of Discrete-Time Quantum Walks via the Shunt Decomposition Method
- Quantum walks in polycyclic aromatic hydrocarbons
- Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
- Quantum walk-based protocol for secure communication between any two directly connected nodes on a network
- Logarithmic expansion of many-body wave packets in random potentials
- Randomized SearchRank: A Semiclassical Approach to a Quantum Search Engine
- Quantum walk with coherent multiple translations induces fast quantum gate operations
- Quantum walks under superposition of causal order
- Controlling quantum chaos via Parrondo strategies on noisy intermediate-scale quantum hardware
- Quantum state transfer and periodicity in discrete-time quantum walks under non--Markovian dephasing noise