QAOA Protein Groups
By Nathan, Grace
Protein–protein interaction (PPI) networks represent proteins as nodes and functional associations as edges, and densely connected groups within them, called communities, often correspond to shared biological function. Community detection is commonly posed as modularity maximization, which is NP-hard, so practical analyses rely on heuristics such as the Louvain algorithm. Modularity maximization can also be written as a quadratic unconstrained binary optimization problem and mapped to an Ising Hamiltonian, the native form for the Quantum Approximate Optimization Algorithm (QAOA). Prior quantum approaches to community detection have mostly used benchmark or synthetic graphs and judged results by modularity alone, so it remains unclear whether the groups they find are biologically meaningful. This project will test one narrow question: how well does QAOA find biologically meaningful protein groups compared to classical methods? We will apply QAOA to a 15–20 protein subnetwork from STRING and compare it against Louvain and an exact brute-force solution on the same network. We will measure modularity, approximation ratio as a function of circuit depth, probability of sampling the optimal partition, agreement between partitions (normalized mutual information and adjusted Rand index), GO/KEGG enrichment of each community, and variation across repeated random initializations. The study is explicitly designed to allow three possible conclusions: QAOA recovers the optimal communities at modest depth, QAOA finds only partially good communities, or QAOA performs worse than classical methods. At this scale we do not expect a computational advantage; the goal is a reproducible baseline.