Isomorphisme graphique et sous-groupes masqués

23

J'essaie de comprendre la relation entre l'isomorphisme des graphes et le problème des sous-groupes cachés. Y a-t-il une bonne référence pour cela?

cc.complexity-theory reference-request quantum-computing graph-isomorphism Suresh Venkat
la source

2

Tssk, non seulement aurons-nous besoin de guérir votre maladie gastro-intestinale, mais aussi tous les pauvres lecteurs de votre question qui sont également infectés! (C'est une plaisanterie, je suis aussi un peu sujet aux maladies gastro-intestinales.)

András Salamon

1

trop vrai. Je dois rester loin de Dave Bacon maintenant :)

Suresh Venkat

2

Pour info, le document relativement récent suivant, je pense, a mis le clou dans le cercueil sur les «algorithmes de tamis quantique» pour GI, qui couvre de nombreuses tentatives jusqu'à présent (et n'est pas mentionné dans le blog de Dave Bacon): dx.doi.org/ 10.1137 / 080724101 . L'article est lourd sur la théorie de la représentation, mais l'intro ne l'est pas, et c'est une assez bonne lecture.

Joshua Grochow

20

Des références peuvent être trouvées dans la réponse de martinschwarz, mais voici un résumé de quelques réductions.

Le groupe symétrique agit sur les graphes de n sommets en permutant les sommets. Déterminer si deux graphiques sont isomorphes équivaut en temps polynomial à calculer un groupe électrogène de taille polynomiale pour . $S_n$ $Aut(G)$

Réduction au HSP sur le groupe symétrique (où est le nombre de variables dans le graphique). La fonction est , où est une permutation de , et est la version permutée de . Alors est constant sur les cosets de et distinct sur les cosets distincts (notez que l'image de $S_n$ $n$ $f$ $f(p)=p(G)$ $p$ $S_n$ $p(G)$ $G$ $f$ $Aut(G)$ $f$ se compose de tous les graphiques isomorphes à ). Puisque le sous-groupe caché est exactement , si nous pouvions résoudre ce HSP, nous aurions alors le groupe électrogène pour , qui est tout ce dont nous avons besoin pour résoudre GI (voir ci-dessus). $G$ $Aut(G)$ $Aut(G)$

Réduction de la HSP sur . Si nous voulons savoir si deux graphes et sur sommets sont isomorphes, considérons le graphe qui est l'union disjointe de et sur sommets. Soit agissent sur les sommets en échangeant avec pour . Soit $S_n \wr \mathbb{Z}/2\mathbb{Z}$ $G$ $H$ $n$ $K$ $G$ $H$ $2n$ $\mathbb{Z}/2\mathbb{Z}$ $i$ $n+i$ $i=1,...,n$ ou . Comme précédemment, soit $Aut(K) = Aut(G) \times Aut(H)$ $Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$ où est maintenant un élément de qui agit sur comme décrit. Le sous-groupe caché associé à est exactement , comme dans la réduction précédente. Si nous résolvons ce HSP, nous obtenons un groupe électrogène pour . Il est alors facile de vérifier si le groupe électrogène contient un élément qui permute la copie de avec la copie de intérieur $f(x)=x(K)$ $x$ $S_n \wr \mathbb{Z}/2\mathbb{Z}$ $K$ $f$ $Aut(K)$ $Aut(K)$ $G$ $H$ (a unecomposante non triviale). $K$ $\mathbb{Z}/2\mathbb{Z}$

Joshua Grochow
la source

17

Vous voudrez peut-être lire le récent article de blog de Dave Bacon sur l'isomorphisme graphique avec des liens vers la littérature.

Martin Schwarz
la source

14

"Algorithmes quantiques pour les problèmes algébriques" par Andrew Childs et Wim van Dam arXiv: 0812.0380 est un très bon document d'enquête qui contient une bonne introduction au HSP non abélien et sa relation avec l'isomorphisme graphique.

dabacon
la source

Isomorphisme graphique et sous-groupes masqués

Réponses: