Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum algorithm for identifying RNA 3D motifs by processing RNA secondary structure graphs

Jing-Kai Fang, Fengmin Guo, Teng Ma, Yong Zhang, Ou Wang, Jun-Han Huang, Yuxiang Li

Published Apr 28, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1101/2025.04.25.650554

Related papers

RNA folding using quantum computers

Dillion M. Fox, Christopher M. MacDermaid, Andrea M. A. Schreij +2 more

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.

PLoS Computational Biology•Apr 11, 2022•33 citations

Predicting RNA Secondary Structure on Universal Quantum Computer

Ji Jiang, Qipeng Yan, Ye Li +6 more

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.

arXiv:2305.09561•May 16, 2023•1 citation

A QUBO model of the RNA folding problem optimized by variational hybrid quantum annealing

Tristan Zaborniak, Juan Giraldo, Hausi A. Müller +2 more

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".

arXiv:2208.04367•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•10 citations

Quantum embedding of graphs for subgraph counting

Bibhas Adhikari

We develop a unified quantum framework for subgraph counting in graphs. We encode a graph on $N$ vertices into a quantum state on $2\lceil \log_2 N \rceil$ working qubits and $2$ ancilla qubits using its adjacency list, with worst-case gate complexity $O(N^2)$, which we refer to as the graph adjacency state. We design quantum measurement operators that capture the edge structure of a target subgraph, enabling estimation of its count via measurements on the $m$-fold tensor product of the adjacency state, where $m$ is the number of edges in the subgraph. We illustrate the framework for triangles, cycles, and cliques. This approach yields quantum logspace algorithms for motif counting, with no known classical counterpart.

quant-pharXiv:2604.18754•Apr 22, 2026•0 citations

Co-Optimization of Codon Usage and mRNA Secondary Structure Using Quantum Computing

Dimitris Alevras, Mihir Metkar, Triet Friedhoff +5 more

Co-optimizing mRNA sequences for both codon optimality and secondary structure is crucial for producing stable and efficacious mRNA therapeutics. Codon optimization, which adjusts nucleotide sequences to enhance translational efficiency, inherently influences mRNA secondary structure - a key determinant of molecular stability both in-vial and in-cell. Because both properties are governed by the same underlying sequence, optimizing one directly impacts the other. To address this interdependence, we introduce a novel variational framework that simultaneously optimizes codon usage and secondary structure. Our method employs a dual-objective function that balances the codon adaptation index (CAI) and minimum free energy (MFE), incorporating variational parameters for codon selection. Leveraging a hybrid quantum-classical computational strategy and building on prior advancements in quantum algorithms for secondary structure prediction, we effectively navigate this complex optimization space. We demonstrate the feasibility of executing this end-to-end workflow on real quantum hardware, using IBM's 127-qubit Eagle processor. We validate our approach through both simulations and quantum hardware experiments on sequences of up to 30 nucleotides. These results highlight the potential of our framework to accelerate the design of optimal mRNA constructs for therapeutic and research applications.

arXiv:2507.18817•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

mRNA Secondary Structure Prediction Using Utility-Scale Quantum Computers

Dimitris Alevras, Mihir Metkar, Takahiro Yamamoto +7 more

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.

arXiv:2405.20328•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•14 citations
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.
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".
We develop a unified quantum framework for subgraph counting in graphs. We encode a graph on NNN vertices into a quantum state on 2⌈log⁡2N⌉2\lceil \log_2 N \rceil2⌈log2​N⌉ working qubits and 222 ancilla qubits using its adjacency list, with worst-case gate complexity O(N2)O(N^2)O(N2), which we refer to as the graph adjacency state. We design quantum measurement operators that capture the edge structure of a target subgraph, enabling estimation of its count via measurements on the mmm-fold tensor product of the adjacency state, where mmm is the number of edges in the subgraph. We illustrate the framework for triangles, cycles, and cliques. This approach yields quantum logspace algorithms for motif counting, with no known classical counterpart.
Co-optimizing mRNA sequences for both codon optimality and secondary structure is crucial for producing stable and efficacious mRNA therapeutics. Codon optimization, which adjusts nucleotide sequences to enhance translational efficiency, inherently influences mRNA secondary structure - a key determinant of molecular stability both in-vial and in-cell. Because both properties are governed by the same underlying sequence, optimizing one directly impacts the other. To address this interdependence, we introduce a novel variational framework that simultaneously optimizes codon usage and secondary structure. Our method employs a dual-objective function that balances the codon adaptation index (CAI) and minimum free energy (MFE), incorporating variational parameters for codon selection. Leveraging a hybrid quantum-classical computational strategy and building on prior advancements in quantum algorithms for secondary structure prediction, we effectively navigate this complex optimization space. We demonstrate the feasibility of executing this end-to-end workflow on real quantum hardware, using IBM's 127-qubit Eagle processor. We validate our approach through both simulations and quantum hardware experiments on sequences of up to 30 nucleotides. These results highlight the potential of our framework to accelerate the design of optimal mRNA constructs for therapeutic and research applications.
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.