Multiple Network Alignment on Quantum Computers
arXiv:1307.7220 · doi:10.1007/s11128-014-0818-7
Abstract
Comparative analyses of graph structured datasets underly diverse problems. Examples of these problems include identification of conserved functional components (biochemical interactions) across species, structural similarity of large biomolecules, and recurring patterns of interactions in social networks. A large class of such analyses methods quantify the topological similarity of nodes across networks. The resulting correspondence of nodes across networks, also called node alignment, can be used to identify invariant subgraphs across the input graphs. Given graphs as input, alignment algorithms use topological information to assign a similarity score to each -tuple of nodes, with elements (nodes) drawn from each of the input graphs. Nodes are considered similar if their neighbors are also similar. An alternate, equivalent view of these network alignment algorithms is to consider the Kronecker product of the input graphs, and to identify high-ranked nodes in the Kronecker product graph. Conventional methods such as PageRank and HITS (Hypertext Induced Topic Selection) can be used for this purpose. These methods typically require computation of the principal eigenvector of a suitably modified Kronecker product matrix of the input graphs. We adopt this alternate view of the problem to address the problem of multiple network alignment. Using the phase estimation algorithm, we show that the multiple network alignment problem can be efficiently solved on quantum computers. We characterize the accuracy and performance of our method, and show that it can deliver exponential speedups over conventional (non-quantum) methods.
References in corpus (16)
- Simulated Quantum Computation of Molecular Energies
- Quantum random walks - an introductory overview
- A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- Simulating chemistry using quantum computers
- Quantum algorithms for algebraic problems
- Using Quantum Computers for Quantum Simulation
- Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
- Quantum Algorithm for Obtaining the Energy Spectrum of Molecular Systems
- Simulating sparse Hamiltonians with star decompositions
- Quantum-circuit design for efficient simulations of many-body quantum dynamics
- Quantum computing applied to calculations of molecular energies: CH2 benchmark
- Decomposition of Unitary Matrices for Finding Quantum Circuits: Application to Molecular Hamiltonians
- A Universal Quantum Circuit Scheme For Finding Complex Eigenvalues
- Finite temperature quantum simulation of stabilizer Hamiltonians