Multiple network alignment on quantum computers

DOI10.1007/S11128-014-0818-7MaRDI QIDQ485371zbMATH OpenOpenAlexFDO

Authors Anmer Daskin, Ananth Grama, Sabre Kais

Publication date 9 January 2015

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

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

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)

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.

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

Cites work

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

Describes a project that uses

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)