La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Mapping Induced Subgraph Isomorphism Problems to Ising Models and Its Evaluations by an Ising Machine Cartographie des problèmes d'isomorphisme de sous-graphe induit par des modèles d'Ising et leurs évaluations par une machine d'Ising

Natsuhito YOSHIMURA, Masashi TAWADA, Shu TANAKA, Junya ARAI, Satoshi YAGI, Hiroyuki UCHIYAMA, Nozomu TOGAWA

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Information Vol.E104-D No.4 pp.481-489
Date de publication
2021/04/01
Publicisé
2021/01/07
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2020EDP7026
Type de manuscrit
PAPER
Catégories
Fondamentaux des Systèmes d'Information

Auteurs

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

Mots-clés

Table des matières