Exploring the Boundaries of Modern Quantum Annealers with RNA Structure Prediction

Quadratic unconstrained binary optimization (QUBO) has gained popularity over the past ten years both for the wide range of problems that can be expressed in this form and for its compatibility with many quantum computing architectures. More recently, quantum annealers have advanced to the point where the scaling of qubits makes real-world applications increasingly feasible; however, current architectures remain restricted to solving quadratic unconstrained binary optimization problems, which can represent at most two-body interactions. Here we systematically examine the shortcomings of the QUBO framework and modern quantum annealers through the lens of the high-dimensional, exponentially scaling problem of RNA structure prediction, and find results that are generalizable to QUBO formalisms writ large. We find that using the QUBO framework to predict RNA structures results in poor accuracy, which becomes worse as system size scales. We determine that the fundamental constraint of two-body interactions prevents emergent correlations in the system, which are crucial to accurate structure prediction. Furthermore, we highlight that explicit, higher-order, empirical terms that are needed to improve structure prediction are incompatible with a QUBO framework. Finally, we show that our energy landscape has many deep local minima, which lead to local minima trapping and prevent permutation invariance. The relevance of these findings to other applications of QUBO, and therefore to modern quantum annealers more broadly, are discussed, with our work providing the first explicit explanation of why these formalisms have failed and will continue to fail in high-dimensional systems with similar constraints.