Quantum Annealing, Digital Annealing, and Classical Solvers Benchmark QUBO for Complex Reaction Network and mRNA Codon Selection

Optimisation problems frequently challenge classical computing, with solution times increasing dramatically as complexity grows, and Milind Upadhyay and Mark Nicholas Jones from Molecular Quantum Solutions ApS investigate whether alternative approaches offer advantages. Their work benchmarks quantum and digital annealing techniques against established classical solvers for two industrially relevant challenges: reaction network pathway analysis and mRNA codon selection. The researchers systematically compare problem mapping, interconnectivity, and solution cost across different solvers, including the Fujitsu digital annealer, various quantum annealing methods, and classical tools like HiGHS, Gurobi, and CP-SAT. Results demonstrate that while classical solvers effectively address reaction pathway analysis, quantum and digital annealing methods show promise for larger-scale mRNA codon selection, with hybrid quantum annealing achieving comparable, and sometimes superior, performance to leading classical algorithms on particularly complex protein datasets. This research highlights the potential of annealing-based approaches to tackle computationally demanding optimisation problems in fields like biotechnology and systems biology.

Scientists identify near-optimal solutions for complex optimisation problems using a mathematical formulation called Quadratic Unconstrained Binary Optimisation (QUBO). This work benchmarks two important applications, chemical reaction network analysis and mRNA codon selection, to evaluate if QUBO solvers, including quantum annealers, offer advantages over traditional classical methods like mixed-integer programming and constraint programming. Researchers applied various metrics to assess solver performance, including problem mapping, interconnectivity, penalty structure, and the time taken to find optimal solutions.

Quantum and Classical Optimisation Performance Comparison

This document details a series of experiments and analyses comparing the performance of various optimisation methods on challenging problems. The primary goal is to assess the potential of quantum and quantum-inspired techniques to outperform classical methods in real-world applications, including chemical reaction network optimisation, mRNA codon optimisation, and complex protein folding simulations. For chemical reaction networks, classical solvers consistently found optimal pathways efficiently, while the digital annealer struggled to achieve the same results. Turning to mRNA codon optimisation, a notoriously difficult task, researchers explored the interplay between codon usage, mRNA structure, and protein expression, investigating quantum and quantum-inspired methods with some indications of potential benefits, particularly when considering mRNA folding and tRNA availability.

Performance on general QUBO problems varied, with quantum annealers sometimes showing speedups but often falling behind classical solvers depending on the problem structure. Finally, for protein folding, quantum-inspired algorithms showed some promise, offering potential advantages in certain cases. The research employed technologies including quantum annealing using D-Wave systems and their Leap service, digital annealing as a classical analogue of quantum annealing, and classical optimisation algorithms like simulated annealing and constraint programming. Many problems were formulated as QUBO problems, and hybrid algorithms combining quantum and classical techniques were also explored, utilising software frameworks like dwave-hybrid and algorithms to predict mRNA secondary structure.

Several challenges were identified, including the difficulty of converting real-world problems into the QUBO format, the limitations of quantum annealers in terms of problem size and complexity, and the impact of qubit connectivity on performance. Access to large datasets of chemical reactions, mRNA sequences, and protein structures is crucial for training and evaluating optimisation algorithms, as is accurately predicting mRNA secondary structure and considering tRNA abundance. The research suggests that quantum and quantum-inspired techniques have the potential to outperform classical methods in certain optimisation problems, but more research is needed to demonstrate a clear quantum advantage. Hybrid algorithms, combining the strengths of both quantum and classical computation, appear particularly promising. Careful problem formulation and encoding are crucial for achieving good performance with quantum annealers, and developing more realistic and challenging benchmarks is essential for evaluating the performance of optimisation algorithms. Further research is needed to understand the complex interplay between codon usage, mRNA structure, and protein expression, and exploring quantum machine learning techniques could lead to further improvements.

QUBO Solvers Benchmark for Pathway and Codon Problems

This work benchmarks the application of Quadratic Unconstrained Binary Optimisation (QUBO) solvers to two complex combinatorial problems: chemical reaction network pathway analysis and mRNA codon selection. Researchers rigorously evaluated the performance of digital and quantum annealers, comparing them against classical mixed-integer programming and constraint programming solvers. For reaction pathway analysis, classical solvers successfully identified optimal solutions within reasonable timeframes, while the digital annealer failed to do so, even when initialized with near-optimal solutions from classical methods. For mRNA codon selection, a notoriously difficult problem, researchers formulated the optimisation as a QUBO and assessed solver performance across datasets ranging from standard proteins to extra-large proteins.

Constraint programming consistently outperformed all other solvers for standard and large protein datasets. However, for the largest datasets, a hybrid quantum annealing solver achieved comparable performance to constraint programming and even surpassed it in finding the lowest cost solution for some instances. The mRNA codon selection QUBO formulation incorporates biological preferences through a cost function that considers codon usage bias, GC content control, and repeated nucleotide minimization. Researchers demonstrated that the GC content control terms, while adding complexity to the QUBO, can be solved efficiently by classical solvers. These detailed measurements and analyses provide valuable insights into the feasibility of utilizing quantum and quantum-inspired solvers for tackling complex biological optimisation problems.

Classical Solvers Excel, Quantum Approaches Lag

This research comprehensively benchmarks the performance of various annealing-based solvers, including quantum annealers and quantum-inspired algorithms, against established classical methods for tackling complex combinatorial optimisation problems. Investigations focused on two industrially relevant use cases, reaction network pathway analysis and mRNA codon selection, alongside a review of existing literature comparing these solvers across a range of problem types. Results demonstrate that classical mixed-integer programming solvers currently outperform quantum and quantum-inspired approaches for reaction pathway analysis, achieving optimality in reasonable timeframes where annealing methods struggled. For the more demanding task of mRNA codon optimisation, hybrid quantum annealing solvers showed promise, particularly with larger datasets, achieving comparable performance to classical constraint programming solvers and even exceeding them in finding the lowest cost solution for some instances.

Across the broader range of problems examined, the study reveals a nuanced landscape where no single solver consistently dominates. The performance of each method is heavily dependent on the specific problem structure and size, with classical algorithms remaining competitive and, in some cases, superior to quantum approaches. The authors acknowledge that the current generation of quantum annealers faces limitations in scalability and connectivity, impacting their ability to efficiently solve large and complex problems. Future research directions include exploring improved problem embedding techniques, developing more sophisticated hybrid algorithms that leverage the strengths of both quantum and classical computation, and investigating novel quantum hardware architectures to overcome existing limitations. This work provides a valuable benchmark for assessing the progress of annealing-based solvers and guides future development efforts in the field of quantum optimisation.