RNA folding using quantum computers

The 3-dimensional fold of an RNA molecule is largely determined by patterns of intramolecular hydrogen bonds between bases. Predicting the base pairing network from the sequence, also referred to as RNA secondary structure prediction or RNA folding, is a nondeterministic polynomial-time (NP)-complete computational problem. The structure of the molecule is strongly predictive of its functions and biochemical properties, and therefore the ability to accurately predict the structure is a crucial tool for biochemists. Many methods have been proposed to efficiently sample possible secondary structure patterns. Classic approaches employ dynamic programming, and recent studies have explored approaches inspired by evolutionary and machine learning algorithms. This work demonstrates leveraging quantum computing hardware to predict the secondary structure of RNA. A Hamiltonian written in the form of a Binary Quadratic Model (BQM) is derived to drive the system toward maximizing the number of consecutive base pairs while jointly maximizing the average length of the stems. A Quantum Annealer (QA) is compared to a Replica Exchange Monte Carlo (REMC) algorithm programmed with the same objective function, with the QA being shown to be highly competitive at rapidly identifying low energy solutions. The method proposed in this study was compared to three algorithms from literature and, despite its simplicity, was found to be competitive on a test set containing known structures with pseudoknots.Author summary: The recent FDA approval of mRNA-based vaccines has increased public interest in synthetically designed RNA molecules. RNA molecules fold into complex secondary structures which determine their molecular properties and in part their efficacy. Determining the folded structure of an RNA molecule is a computationally challenging task with exponential scaling that is intractable to solve exactly, and therefore approximate methods are used. Quantum computing technology offers a new approach to finding approximate solutions to problems with exponential scaling. We formulate a simplistic, yet effective, model of RNA folding that can easily be mapped to quantum computers and we show that currently available quantum computing hardware is competitive with classical methods.