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.
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.
It is the first step for understanding how RNA structure folds from base sequences that to know how its secondary structure is formed. Traditional energy-based algorithms are short of precision, particularly for non-nested sequences, while learning-based algorithms face challenges in obtaining high-quality training data. Recently, quantum annealer has rapidly predicted the folding of the secondary structure, highlighting that quantum computing is a promising solution to this problem. However, gate model algorithms for universal quantum computing are not available. In this paper, gate-based quantum algorithms will be presented, which are highly flexible and can be applied to various physical devices. Mapped all possible secondary structure to the state of a quadratic Hamiltonian, the whole folding process is described as a quadratic unconstrained binary optimization model. Then the model can be solved through quantum approximation optimization algorithm. We demonstrate the performance with both numerical simulation and experimental realization. Throughout our benchmark dataset, simulation results suggest that our quantum approach is comparable in accuracy to classical methods. For non-nested sequences, our quantum approach outperforms classical energy-based methods. Experimental results also indicate our method is robust in current noisy devices. It is the first instance of universal quantum algorithms being employed to tackle RNA folding problems, and our work provides a valuable model for utilizing universal quantum computers in solving RNA folding problems.
RNAs self-interact through hydrogen-bond base-pairing between nucleotides and fold into specific, stable structures that substantially govern their biochemical behaviour. Experimental characterization of these structures remains difficult, hence the desire to predict them computationally from sequence information. However, correctly predicting even the base pairs involved in the folded structure of an RNA, known as secondary structure, from its sequence using minimum free energy models is understood to be NP-hard. Classical approaches rely on heuristics or avoid considering pseudoknots in order to render this problem more tractable, with the cost of inexactness or excluding an entire class of important RNA structures. Given their prospective and demonstrable advantages in certain domains, including combinatorial optimization, quantum computing approaches by contrast have the potential to compute the full RNA folding problem while remaining more feasible and exact. Herein, we present a physically-motivated QUBO model of the RNA folding problem amenable to both quantum annealers and circuit-model quantum computers and compare the performance of this formulation versus current RNA folding QUBOs after tuning the parameters of all against known RNA structures using an approach we call "variational hybrid quantum annealing".
Abstract The identification of RNA motifs plays a crucial role in understanding biological functions, predicting RNA 3D structures, and designing RNA-based therapeutics. One of the efficient strategies approaches this task by analyzing secondary structure graphs annotated with non-canonical base interactions, effectively reframing the problem as a two-dimensional graph-theoretic challenge. However, both the graph isomorphism problem and the maximum common subgraph problem in this domain are classified as NP-complete. Classical computing architectures struggle to address these problems efficiently due to their substantial computational resource demands. In this work, we propose a quantum algorithm specifically designed for processing RNA secondary structure graphs. By encoding the adjacency matrix into a quantum circuit and incorporating base interaction families as edge weights, our approach achieves a resource efficiency of 𝒪 (log 2 N ) in terms of qubits. Numerical simulations demonstrate the algorithm’s capability to identify 15 distinct motifs across three structural categories: hairpin loops, internal loops, and three-way junction loops. Furthermore, the method successfully detects the common motif between two complete RNA chains. Finally, 29 high conserved RNA motifs were identified in four cell lines of a key lung cancer biomarker gene (MIF), and their potential roles as drug targets were explored. This work presents a highly promising quantum computing framework for addressing the RNA motif identification problem.
Biomolecules and their interactions form the material and processual basis underlying all biological phenomena, from photosynthesis to Alzheimer’s disease. Studying these systems is therefore central to the purview of all biological sciences. Computational biomolecular structure prediction (CBSP) supports this effort by leveraging computers to determine, model, and engineer biomolecular structures, properties, and processes—offering a powerful complement to laboratory-based methods. However, many core CBSP problems—such as finding minimum free energy or conformationally-stable structures given sequence information—are computationally challenging. These problems are typically NP-hard in their general form, while their corresponding decision variants are NP-complete. As a result, both formulations are resistant to efficient exact solution at large scales. Quantum computing, a developing computational paradigm leveraging quantum mechanics, offers a potential path forward, given recent evidence suggesting that certain quantum approaches may reduce resource demands for certain NP-hard problem families. Approaches include fully quantum algorithms, quantum-inspired classical heuristics, and hybrid quantum-classical frameworks, all of which may help address long-standing computational bottlenecks in CBSP. This dissertation offers a preliminary investigation of the practical potential of quantum computing for three core CBSP challenges—RNA folding, multi-body molecular docking, and protein design—that, despite their diverse applications, share structural features well suited to exploration by quantum optimization methods. Specifically, we cast each problem as a cost function network (CFN), and develop transformations of these CFNs to quadratic unconstrained binary optimization (QUBO) models in order to render them compatible with current quantum and quantum-inspired hardware. We argue that these transformations not only broaden the range of solvable CFNs across quantum platforms, but in some cases possess intrinsic features which may offer optimization advantages over native CFN formulations. Using a current‑generation superconducting flux‑qubit quantum annealer, we: (a) demonstrate its use for tuning free QUBO parameters against biomolecular structure data, and (b) benchmark solution quality and resource usage against optimized classical Monte Carlo methods, finding comparable performance. Finally, we package these methods into the Masala Quantum Computing Plugins library, an open‑source, modular CBSP platform that supports CFN construction, multiple QUBO encodings (one‑hot, domain‑wall, approximate‑binary, hybrid), and execution on both classical and quantum backends. Our contribution lays the groundwork for extensible, state‑of‑the‑art, quantum-compatible CBSP workflows.
Recent advancements in quantum computing have created new opportunities for tackling long-standing, complex combinatorial optimization problems that are intractable for classical computers. Predicting the secondary structure of mRNA is one such notoriously difficult problem that can benefit from the rapid advancements in quantum computing technology. Accurate prediction of mRNA secondary structure is crucial for designing RNA-based therapeutics, as it dictates various stages of the mRNA life cycle, including transcription, translation, and decay. The current generation of quantum computers has reached a utility scale, enabling us to explore relatively large problem sizes. In this paper, we examine the feasibility of solving mRNA secondary structures on a quantum computer for sequence lengths up to 60 nucleotides, representing problems in the qubit range of 10 to 80. We use the Conditional Value at Risk (CVaR)-based VQE algorithm to solve optimization problems derived from mRNA secondary structure prediction on the IBM Eagle and Heron quantum processors. Encouragingly, even with minimal error mitigation and fixed-depth circuits, our hardware runs yield accurate predictions of minimum free energy (MFE) structures that match the results of the classical solver CPLEX. Our results provide substantial evidence for the viability of solving mRNA structure prediction problems on a quantum computer and motivate continued research in this direction.
Sequence matching in genomics can be approached by quantum computing through Grover’s algorithm offering a quadratic speed-up versus the fastest classical algorithms. Previous research using quantum computing focused on long DNA sequences, but application to complex RNA secondary structures with hairpin, bulge, ring, and stem forms has not been possible. This paper developed new formulations for RNA structures using quantum pattern recognition and quantum Hamming distance on Grover’s framework by extracting linear regions from the complex forms. To best leverage the quantum speedup, methods are developed to create long sequences by concatenating different linearized parts of the complex RNA structures. The mechanism is simulated on IBM’s Qiskit quantum simulator using RNA examples from GenBank and mirBase. Comparisons of the iteration complexity indeed shows the potential for quadratic speedups from quantum computing versus classical. Simulation results also show that search accuracy is very good when using the quantum pattern recognition method.