Algoritmi quantistici per un insieme generatore di cardinalità minima

Abstract degli autori

In questo articolo presentiamo un algoritmo quantistico polinomiale per calcolare un insieme generatore di cardinalità minima di gruppi black-box risolubili. Consideriamo poi la classe $Γ_d$ dei gruppi black-box in cui ogni fattore di composizione non abeliano è isomorfo a un sottogruppo del gruppo simmetrico $S_d$, per un valore fissato di $d$. Progettiamo algoritmi quantistici polinomiali per calcolare la decomposizione in prodotto diretto dei gruppi fattore abeliani e risolvere il problema di appartenenza costruttiva per i gruppi fattore dei gruppi appartenenti a $Γ_d$. Con l’aiuto di questi algoritmi, progettiamo un algoritmo quantistico per calcolare una serie principale di gruppi black-box appartenenti a $Γ_d$. Usando la serie principale, costruiamo un algoritmo quantistico polinomiale per calcolare insiemi generatori di cardinalità minima dei gruppi black-box appartenenti a $Γ_d$. Infine, mostriamo che il problema dell’insieme generatore di cardinalità minima per gruppi black-box generali appartiene a $\textrm{NP} \cap \textrm{coAM}$.