Comparing and investigation into different protein-protein interaction networks (PPI networks) is significant for discovering new biological function and comprehending the evolution of the protein-protein interactions. Because general PPI networks are large in scale, existing classical computation algorithms of solving alignment and search in PPI networks possess too high time complexity. The time complexity is so high that it is impossible for the algorithm to align the whole network simultaneously. An effective quantum algorithm, Quantum-walks Algorithm for PPI-network Similar Subnets Searching (QPSS), is introduced to improve the situation mentioned above based on the continuous-time quantum-walks model in quantum computation. The process in detail of the QPSS algorithm is demonstrated. Moreover, we discuss the performance evaluation of this algorithm. After the time complexity of QPSS algorithm compares with its classical counterpart, it has been proved that the QMSM obtains a nearly quadratic speed-up.
Comparing and investigation into different protein-protein interaction networks (PPI networks) is significant for discovering new biological function and comprehending the evolution of the protein-protein interactions. Because general PPI networks are large in scale, existing classical computation algorithms of solving alignment and search in PPI networks possess too high time complexity. The time complexity is so high that it is impossible for the algorithm to align the whole network simultaneously. An effective quantum algorithm, Quantum-walks Algorithm for PPI-network Similar Subnets Searching (QPSS), is introduced to improve the situation mentioned above based on the continuous-time quantum-walks model in quantum computation. The process in detail of the QPSS algorithm is demonstrated. Moreover, we discuss the performance evaluation of this algorithm. After the time complexity of QPSS algorithm compares with its classical counterpart, it has been proved that the QMSM obtains a nearly quadratic speed-up.
The study of protein-protein interactions (PPIs) and predicting the protein structure plays a critical role in understanding cellular processes and designing therapeutic interventions. In this research, we explore the application of quantum algorithms, specifically Grover’s algorithm, in improving the accuracy and efficiency of PPI prediction. By harnessing the inherent parallelism and quantum search capabilities of Grover’s algorithm, we aim to enhance the identification of interacting protein pairs from large-scale datasets. We demonstrate the effectiveness of using this algorithm through an extensive approach, comparing the performance of Grover’s algorithm with classical machine learning algorithms. Our results reveal that the quantum algorithm offers significant improvements in prediction accuracy, enabling the identification of previously undetected PPIs. Moreover, we discuss the advantages and limitations of using Grover’s algorithm in PPI prediction and provide insights into its potential for accelerating research in protein interaction networks. This research highlights the potential of quantum algorithms in advancing the field of bioinformatics and protein interaction analysis.
Protein-protein interaction (PPI) network alignment combines topological and sequence information to identify conserved modules across species, but global alignment remains challenging: heuristics sacrifice optimality, while exact methods lack scalability. We model the alignment as a weighted maximum common induced subgraph problem and reformulate it through the modular product graph to a minimum-weight vertex cover on the complement, with node weights carrying sequence similarity. To solve this problem, we develop a hybrid framework combining kernelisation, branch-and-bound, and seven Quantum Approximate Optimisation Algorithm (QAOA) formulations. These formulations differ in how the cover constraints are enforced, from penalty terms in the cost Hamiltonian to mixers confined to the feasible subspace. For single round QAOA, we derive closed-form expressions for the expected cost of four circulant mixer variants, enabling performance characterisation without circuit simulation. Applied to synthetic and real-world networks reduced to KEGG pathways, the QAOA formulations achieve high topological conservation on the aligned core while at least maintaining biological conservation comparable to leading classical aligners, at the cost of reduced node coverage. Across selected KEGG pathways, the aligned subnetworks retain disease-associated proteins, preserving biologically relevant information. Cheaper formulations leave more edges uncovered, while enforcing feasibility in the mixer raises circuit depth by one to two orders of magnitude. Together, these results highlight the potential of quantum optimisation for PPI network alignment and the resource trade-offs that will shape its scalability as quantum hardware matures.
Comparative analyses of protein-protein interaction networks play important roles in the understanding of biological processes. However, the growing enormity of available data on the networks becomes a computational challenge for the conventional alignment algorithms. Quantum algorithms generally provide greater efficiency over their classical counterparts in solving various problems. One of such algorithms is the quantum phase estimation algorithm which generates the principal eigenvector of a stochastic matrix with probability one. Using the quantum phase estimation algorithm, we introduce a quantum computing approach for the alignment of protein-protein interaction networks by following the classical algorithm IsoRank which uses the principal eigenvector of the stochastic matrix representing the Kronecker product of the normalized adjacency matrices of networks for the pairwise alignment. We also present a greedy quantum measurement scheme to efficiently procure the alignment from the output state of the phase estimation algorithm where the eigenvector is encoded as the amplitudes of this state. The complexity of the quantum approach outperforms the classical running time.
This paper explores the application of quantum walk algorithms to graph traversal and search problems. Classical algorithms often struggle with the computational complexity of traversing and searching large graphs, leading to significant time and resource limitations. Quantum walks, utilizing superposition and interference, offer a potential pathway to achieve exponential speedups. This work details the theoretical framework for applying quantum walks to graph problems, specifically focusing on traversal and search tasks. We present a generalized approach for mapping graph structures onto quantum walk systems and discuss the key mathematical formulations involved. The core of our investigation revolves around the construction of quantum walk operators that mimic the movement and interaction rules inherent in graph traversal. We analyze the evolution of the quantum walk state and derive expressions for the probability of reaching a specific node in the graph. Furthermore, we examine the impact of graph topology on the performance of the quantum walk, highlighting the potential for tailored algorithms to exploit specific graph structures. The results demonstrate the theoretical feasibility of quantum walk algorithms for significantly accelerating graph traversal and search operations, contributing to advancements in areas such as network analysis, database management, and artificial intelligence.
We present a quantum-dynamical framework for identifying structurally important residues in proteins based on continuous time quantum walks (CTQWs) on weighted residue interaction networks constructed from experimentally resolved structures. By mapping the weighted adjacency matrix to a Hamiltonian, residue importance emerges from the long-time averaged occupation probability, confirmed analytically through its spectral decomposition. Across a dataset of approximately 150 proteins spanning diverse structural and functional classes, CTQW centrality exhibits consistently strong agreement with classical eigenvector centrality in identifying central residues, while extending beyond it through incorporating signatures of quantum interference. Analyzing the time-averaged quantum transition matrix reveals consistently larger spectral gaps than the classical random-walk operator. Furthermore, biological relevance is confirmed through recovery of experimentally established functional residues in proteins kinase A and oxytocin. CTQW-derived centrality rankings are accessible on near-term intermediate-scale quantum hardware, as we demonstrate through a proof-of-principle implementation on IBM superconducting quantum hardware. These results establish continuous-time quantum walks as a computationally tractable framework for protein network analysis, that connects network theoretical treatments of protein structural biology to continuous-time quantum walk dynamics.
We present a quantum-dynamical framework for identifying structurally and functionally important residues in proteins based on continuous-time quantum walks (CTQWs) on weighted residue-interaction networks constructed from experimentally resolved structures. By mapping the weighted adjacency matrix to a Hamiltonian, residue importance emerges from the long-time averaged occupation probability, confirmed analytically through its spectral decomposition. Across a data set of 150 proteins spanning diverse structural and functional classes, CTQW centrality exhibits consistently strong agreement with classical eigenvector centrality in identifying central residues, while extending beyond it through incorporating signatures of quantum interference. Analyzing the time-averaged quantum transition matrix reveals consistently larger spectral gaps than the classical random-walk operator. Furthermore, biological relevance is confirmed through recovery of experimentally established functional residues in proteins kinase A and oxytocin. CTQW-derived centrality rankings are accessible on near-term intermediate-scale quantum hardware, as we demonstrate through a proof-of-principle implementation on IBM superconducting quantum hardware. These results establish continuous-time quantum walks as a computationally tractable framework for protein network analysis, that connects network theoretical treatments of protein structural biology to continuous-time quantum walk dynamics.