Identifying Protein Co-Regulatory Network Logic by Solving B-Sat Problems Through Gate-Based Quantum Computing

Abstract

There is growing awareness that the success of pharmacologic interventions on living organisms is significantly impacted by context and timing of exposure. In turn, this complexity is leading to an increasing focus on regulatory network dynamics in biology and our ability to represent these at a high level of fidelity, in silico. Logic network models continue to show great promise in this domain and their parameter estimation can be formulated as a constraint satisfaction problem (CSP) that is especially well-suited for the often sparse and incomplete data associated with biology. Unfortunately, even in the case of Boolean logic, the combinatorial complexity of these problems grows rapidly, challenging our ability to create such models at physiologically-relevant scales. That said, quantum computing, while still nascent, facilitates novel information-processing paradigms with the potential for transformative impact in problems such as this one. In this work, we take a first step at actualizing this potential by identifying the structure and Boolean decisional logic of a well-studied regulatory network linking five proteins involved in the neural development of the mammalian cortical area of the brain. We identify the protein-protein connectivity and binary decisional logic governing this network by formulating it as a Boolean Satisfiability (B-SAT) problem. We then employ Grover's algorithm to solve the NP-hard problem faster than the exponential time complexity required by deterministic classical algorithms. Using approaches deployed on both quantum simulators and actual noisy intermediate scale quantum (NISQ) hardware, we accurately recover several highlikelihood models from very sparse protein expression data. The results highlight the differential roles of various data types in supporting accurate models; the impact of quantum algorithm design as it pertains to the mutability of quantum hardware, and the opportunities for accelerated discovery enabled by this approach.