The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Les machines d'Ising ont attiré l'attention car elles sont censées résoudre des problèmes d'optimisation combinatoire à grande vitesse avec des modèles d'Ising correspondant à ces problèmes. Un problème d'isomorphisme de sous-graphe induit est l'un des problèmes de décision qui détermine si une structure de graphe spécifique est incluse ou non dans un graphe entier. Le problème peut être représenté par des contraintes d’égalité dans les termes du problème d’optimisation combinatoire. En utilisant les fonctions de pénalité correspondant aux contraintes d'égalité, nous pouvons utiliser une machine d'Ising pour résoudre le problème d'isomorphisme de sous-graphe induit. Le problème de l'isomorphisme de sous-graphe induit peut être observé dans de nombreux problèmes pratiques, par exemple la découverte d'un circuit malveillant particulier dans un dispositif ou d'une structure de réseau particulière de liaisons chimiques dans un composé. Cependant, en raison du nombre limité de variables de spin dans les machines d’Ising actuelles, la réduction du nombre de variables de spin constitue une préoccupation majeure. Nous proposons ici une méthode de cartographie de modèle d'Ising efficace pour résoudre le problème d'isomorphisme de sous-graphe induit par les machines d'Ising. Notre méthode proposée résout théoriquement le problème de l’isomorphisme des sous-graphes induits. De plus, le nombre de variables de spin dans le modèle d'Ising généré par notre méthode proposée est théoriquement inférieur à celui de la méthode conventionnelle. Les résultats expérimentaux démontrent que notre méthode proposée peut résoudre avec succès le problème d'isomorphisme de sous-graphe induit en utilisant le recuit simulé basé sur le modèle d'Ising et une véritable machine d'Ising.
Natsuhito YOSHIMURA
Waseda University
Masashi TAWADA
Waseda University
Shu TANAKA
Waseda University,Japan Science and Technology Agency
Junya ARAI
NTT Corporation
Satoshi YAGI
NTT Corporation
Hiroyuki UCHIYAMA
NTT Corporation
Nozomu TOGAWA
Waseda University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Natsuhito YOSHIMURA, Masashi TAWADA, Shu TANAKA, Junya ARAI, Satoshi YAGI, Hiroyuki UCHIYAMA, Nozomu TOGAWA, "Mapping Induced Subgraph Isomorphism Problems to Ising Models and Its Evaluations by an Ising Machine" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 4, pp. 481-489, April 2021, doi: 10.1587/transinf.2020EDP7026.
Abstract: Ising machines have attracted attention as they are expected to solve combinatorial optimization problems at high speed with Ising models corresponding to those problems. An induced subgraph isomorphism problem is one of the decision problems, which determines whether a specific graph structure is included in a whole graph or not. The problem can be represented by equality constraints in the words of combinatorial optimization problem. By using the penalty functions corresponding to the equality constraints, we can utilize an Ising machine to the induced subgraph isomorphism problem. The induced subgraph isomorphism problem can be seen in many practical problems, for example, finding out a particular malicious circuit in a device or particular network structure of chemical bonds in a compound. However, due to the limitation of the number of spin variables in the current Ising machines, reducing the number of spin variables is a major concern. Here, we propose an efficient Ising model mapping method to solve the induced subgraph isomorphism problem by Ising machines. Our proposed method theoretically solves the induced subgraph isomorphism problem. Furthermore, the number of spin variables in the Ising model generated by our proposed method is theoretically smaller than that of the conventional method. Experimental results demonstrate that our proposed method can successfully solve the induced subgraph isomorphism problem by using the Ising-model based simulated annealing and a real Ising machine.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020EDP7026/_p
Copier
@ARTICLE{e104-d_4_481,
author={Natsuhito YOSHIMURA, Masashi TAWADA, Shu TANAKA, Junya ARAI, Satoshi YAGI, Hiroyuki UCHIYAMA, Nozomu TOGAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Mapping Induced Subgraph Isomorphism Problems to Ising Models and Its Evaluations by an Ising Machine},
year={2021},
volume={E104-D},
number={4},
pages={481-489},
abstract={Ising machines have attracted attention as they are expected to solve combinatorial optimization problems at high speed with Ising models corresponding to those problems. An induced subgraph isomorphism problem is one of the decision problems, which determines whether a specific graph structure is included in a whole graph or not. The problem can be represented by equality constraints in the words of combinatorial optimization problem. By using the penalty functions corresponding to the equality constraints, we can utilize an Ising machine to the induced subgraph isomorphism problem. The induced subgraph isomorphism problem can be seen in many practical problems, for example, finding out a particular malicious circuit in a device or particular network structure of chemical bonds in a compound. However, due to the limitation of the number of spin variables in the current Ising machines, reducing the number of spin variables is a major concern. Here, we propose an efficient Ising model mapping method to solve the induced subgraph isomorphism problem by Ising machines. Our proposed method theoretically solves the induced subgraph isomorphism problem. Furthermore, the number of spin variables in the Ising model generated by our proposed method is theoretically smaller than that of the conventional method. Experimental results demonstrate that our proposed method can successfully solve the induced subgraph isomorphism problem by using the Ising-model based simulated annealing and a real Ising machine.},
keywords={},
doi={10.1587/transinf.2020EDP7026},
ISSN={1745-1361},
month={April},}
Copier
TY - JOUR
TI - Mapping Induced Subgraph Isomorphism Problems to Ising Models and Its Evaluations by an Ising Machine
T2 - IEICE TRANSACTIONS on Information
SP - 481
EP - 489
AU - Natsuhito YOSHIMURA
AU - Masashi TAWADA
AU - Shu TANAKA
AU - Junya ARAI
AU - Satoshi YAGI
AU - Hiroyuki UCHIYAMA
AU - Nozomu TOGAWA
PY - 2021
DO - 10.1587/transinf.2020EDP7026
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2021
AB - Ising machines have attracted attention as they are expected to solve combinatorial optimization problems at high speed with Ising models corresponding to those problems. An induced subgraph isomorphism problem is one of the decision problems, which determines whether a specific graph structure is included in a whole graph or not. The problem can be represented by equality constraints in the words of combinatorial optimization problem. By using the penalty functions corresponding to the equality constraints, we can utilize an Ising machine to the induced subgraph isomorphism problem. The induced subgraph isomorphism problem can be seen in many practical problems, for example, finding out a particular malicious circuit in a device or particular network structure of chemical bonds in a compound. However, due to the limitation of the number of spin variables in the current Ising machines, reducing the number of spin variables is a major concern. Here, we propose an efficient Ising model mapping method to solve the induced subgraph isomorphism problem by Ising machines. Our proposed method theoretically solves the induced subgraph isomorphism problem. Furthermore, the number of spin variables in the Ising model generated by our proposed method is theoretically smaller than that of the conventional method. Experimental results demonstrate that our proposed method can successfully solve the induced subgraph isomorphism problem by using the Ising-model based simulated annealing and a real Ising machine.
ER -