Exploring the Boundaries of Modern Quantum Annealers with RNA Structure Prediction

Area of Science:

• Computational Biology
• Quantum Computing
• Bioinformatics

Background:

• Quadratic unconstrained binary optimization (QUBO) is popular for its broad applicability and compatibility with quantum computing.
• Quantum annealers are advancing, but current architectures are limited to QUBO problems, restricting them to two-body interactions.
• RNA structure prediction is a high-dimensional, exponentially scaling problem crucial for understanding biological function.

Purpose of the Study:

• To systematically examine the limitations of the QUBO framework and quantum annealers for RNA structure prediction.
• To generalize findings regarding QUBO's shortcomings to broader applications involving high-dimensional systems.

Main Methods:

• Analysis of the QUBO framework's suitability for RNA structure prediction.
• Investigation of how the two-body interaction constraint impacts accuracy and emergent correlations.
• Evaluation of the compatibility of higher-order empirical terms with the QUBO framework.

Main Results:

• QUBO-based RNA structure prediction shows poor accuracy, which degrades with increasing system size.
• The two-body interaction constraint in QUBO prevents the emergence of crucial correlations needed for accurate prediction.
• Higher-order terms necessary for improved prediction are incompatible with the QUBO formalism, and the energy landscape exhibits local minima trapping.

Conclusions:

• The QUBO framework's inherent limitations, particularly the restriction to two-body interactions, make it unsuitable for complex, high-dimensional problems like RNA structure prediction.
• These findings explain the failure of QUBO and current quantum annealers in such systems and have broad implications for other QUBO applications.
• Future quantum computing approaches for complex problems may require formalisms beyond standard QUBO to overcome these limitations.