Multiple network alignment on quantum computers

DOI10.1007/S11128-014-0818-7zbMATH Open1305.81050arXiv1307.7220OpenAlexW3098336268MaRDI QIDQ485371FDOQ485371

Authors: Anmer Daskin, Ananth Grama, Sabre Kais 

Publication date: 9 January 2015

Published in: Quantum Information Processing (Search for Journal in Brave)

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 $k$ graphs as input, alignment algorithms use topological information to assign a similarity score to each $k$-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.

Full work available at URL: https://arxiv.org/abs/1307.7220

Recommendations

• Scalable algorithms for multiple network alignment
• Quantum walk inspired algorithm for graph similarity and isomorphism
• Efficient quantum algorithm for similarity measures for molecules
• Discrete-time quantum walk algorithm for ranking nodes on a network
• Graph comparison via nonlinear quantum search

zbMATH Keywords

quantum algorithmsnetwork alignmentNP problemsphase estimation algorithmsquantum bioinformatics

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Social networks; opinion dynamics (91D30) Systems biology, networks (92C42) Quantum computation (81P68) Applications of graph theory to circuits and networks (94C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Adiabatic quantum state generation and statistical zero knowledge
• Title not available (Why is that?)
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Authoritative sources in a hyperlinked environment
• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithms for algebraic problems
• A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching
• A universal quantum circuit scheme for finding complex eigenvalues
• Simulating Sparse Hamiltonians with Star Decompositions
• The PageRank Vector: Properties, Computation, Approximation, and Acceleration
• On the efficiency of quantum algorithms for Hamiltonian simulation
• Authority Rankings from HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of Initialization
• A regularized integral equation method for the inverse geometry heat conduction problem
• Algorithm for quantum simulation
• Quantum-circuit design for efficient simulations of many-body quantum dynamics
• Using quantum computers for quantum simulation

Cited In (4)

• Scalable algorithms for multiple network alignment
• Obtaining a linear combination of the principal components of a matrix on quantum computers
• Quantum walk inspired algorithm for graph similarity and isomorphism
• Efficient quantum algorithm for similarity measures for molecules

Uses Software

• IsoRankN

This page was built for publication: Multiple network alignment on quantum computers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q485371)