Ising machines and quantum computers provide fast and accurate chemical reaction analyses
Points
・Extracting atom mapping (chemical reaction pattern) from chemical reaction formula using Ising computing
・An enumeration algorithm using Ising calculations quickly enumerates all chemically possible patterns
・Expected to aid accurate, fast searches in reaction databases and retrosynthetic analysis.
Abstract
A research group led by Specially Appointed Assistant Professor Seiji Akiyama, Specially Appointed Associate Professor Yuuya Nagata, Assistant Professor Yuta Mizuno, and Professor Tamiki Komatsuzaki from the Institute for Chemical Reaction Design and Discovery (WPI-ICReDD) at Hokkaido University have developed a method for solving the “atom-to-atom mapping” problem, which involves determining the correspondence between atoms in reactants and products in a given chemical reaction with high accuracy and speed. The atom-to-atom mapping problem is fundamental process in cheminformatics as it helps in extracting reaction patterns. However, solving this problem accurately and quickly remains challenging. Computational complexity of solving the problem increases drastically due to combinatorial explosion, and using reaction rules or machine learning techniques based on known data tends to lower accuracy.
In this research, the team demonstrated that atom-to-atom mapping could be accurately and rapidly determined without relying on reaction rules by utilizing a combinatorial optimization method called Ising computing. This approach paves the way for future applications such as the use of Ising machines or quantum computers, and the precise and fast searches as well as retrosynthetic analysis of chemical reaction databases are expected to be promising developments.
This research was published in the Journal of Chemical Information and Modeling on 2025/2/2. More details can be found in the original article (DOI: 10.1021/acs.jcim.4c01871), which is open access and can be viewed by anyone.
Background
The atom-to-atom mapping (AAM) problem refers to the task of determining which atoms in the reactants corresponds to which atoms in the products of a chemical reaction. From AAM, one can identify the reaction center and which bonds are formed or broken, thus revealing the patterns of the reaction (Figure 1). Such information is fundamental in the field of cheminformatics, and it is indispensable for tasks such as querying chemical reaction databases and planning the synthesis of compounds (retrosynthetic analysis). However, as this problem entails considering the combinations of atoms between the reactants and products, the number of possible atom mappings increases combinatorically with the size of the molecules. Therefore, the AAM problem is notably difficult to solve both accurately and rapidly. Conventionally, to address this computational difficulty, rule-based methods have been developed that generate basic patterns of chemical reactions and reference these patterns for mapping, as well as machine learning models trained on vast amount of reaction data. However, both approaches tend to output mappings that closely resemble the reaction patterns embedded in the program or the learned data, posing challenges with respect to accuracy.
Method
In this study, we aimed to determine the AAM with high accuracy and efficiency without reliance on existing chemical reaction datasets. The atom mapping problem was formulated as a combinatorial optimization problem, wherein the objective is to minimize the number of bonds that are broken and formed during the reaction—i.e., to establish the optimal correspondence between the reactant and product atoms.
To efficiently solve this combinatorial optimization problem, we developed an algorithm based on Ising computing. Ising computing is a specialized optimization approach for combinatorial problems, inspired by the Ising model in statistical physics, which describes magnetism. Among the various methods of Ising computing, simulated annealing and quantum annealing are particularly well known, and in recent years, significant advancements have been made in the development of dedicated hardware, known as Ising machines, designed to implement these methods. The Hopfield network, which was recognized in the awarding of the 2024 Nobel Prize in Physics, as well as the quantum approximate optimization algorithm executed on quantum computers, can likewise be regarded as forms of Ising computing. In this study, with a view to the potential applications of diverse Ising computing techniques, we developed an algorithm and employed simulated annealing for numerical demonstrations.
The AAM problem, as formulated above, often provides multiple optimal solutions. In such cases, it is necessary to enumerate all optimal solutions to ensure that no correct reaction pattern is overlooked. However, in conventional Ising computing, a single (quasi-)optimal solution is obtained probabilistically in a single computation.
To address this issue, in the present study, we applied an enumeration algorithm using an Ising machine, recently developed by our research group (arXiv:2412.00284), to the AAM problem. This enumeration algorithm achieves solution enumeration by appropriately repeating the sampling process and is mathematically guaranteed to attain a success probability of over 99% for the complete enumeration of solutions under appropriate conditions.
Results
In this study, we transformed the AAM problem into an energy minimization problem of the Ising model and developed a program that enumerates all chemically plausible atom mappings using an enumeration algorithm based on Ising computing (Figure 1). When applied to an existing benchmark problem set, our enumeration algorithm using Ising computing was found to compute correct solutions faster than conventional algorithms for solving the combinatorial optimization problem corresponding to the AAM problem, especially for reactions involving larger molecules (Figure 2).
Furthermore, an accuracy evaluation revealed that the proposed algorithm successfully identified the atomic mappings considered correct by chemists in all 241 benchmark problems. This performance is equivalent to that of the state-of-the-art machine learning model, RxnMapper, and surpasses other existing atom mapping tools (Figure 3). As this method enables accurate atom mapping without prior data, it is expected to be applicable to the discovery of unknown chemical reaction patterns.
Future Prospects
This method enables accurate and fast atom mapping for chemical reactions involving large molecules, and in the future, it is expected to be applied to accurate and rapid searches in chemical reaction databases, as well as retrosynthetic analysis. In this study, we employed simulated annealing, which can be easily executed on conventional computers, as the Ising computing method. However, by utilizing dedicated hardware for Ising computing, known as Ising machines, or quantum computers, it may be possible to achieve even faster atom mapping. We look forward to further developments in this field.
Acknowledgments
This research was supported by the Japan Science and Technology Agency (JST) under the PRESTO program (JPMJPR2018) and the Support for Pioneering Research Initiated by the Next Generation: SPRING (JPMJSP2119), the Ministry of Education, Culture, Sports, Science and Technology (MEXT) through the Grant-in-Aid for Transformative Research Areas (B) (JP23H03806) and the World Premier International Research Center Initiative (WPI), as well as by the Hitachi Hokkaido University Laboratory.
Paper information
Title: Enumeration Approach to Atom-to-Atom Mapping Accelerated by Ising Computing
Authors: Mohammad Ali,1,2 Yuta Mizuno,1,3,4 Seiji Akiyama,4,5 Yuuya Nagata,4,5 Tamiki Komatsuzaki1,3,4,6 (1Graduate School of Chemical Sciences and Engineering, Hokkaido University, 2Statistics Discipline, Khulna University, 3Graduate School of Chemical Sciences and Engineering, Hokkaido University, 4Institute for Chemical Reaction Design and Discovery, Hokkaido University,5 ERATO Maeda Artificial Intelligence for Chemical Reaction Design and Discovery Project, Hokkaido University, 6SANKEN, Osaka University).
Journal: Journal of Chemical Information and Modeling
DOI: 10.1021/acs.jcim.4c01871
Publication data: 2025/02/01
Contact Information
Seiji Akiyama, specially appointed assistant professor, Institute for Chemical Reaction Design and Discovery (WPI-ICReDD), Hokkaido University,
TEL 011-706-9752
e-mail s.aki@icredd.hokudai.ac.jp
URL https://www.icredd.hokudai.ac.jp/ja
Yuta Mizuno, assistant professor, Electronic Science Research Institute, Hokkaido University
TEL 011-706-9450
e-mail mizuno@es.hokudai.ac.jp
URL https://mlns.es.hokudai.ac.jp/