Skrytý problém podskupiny - Hidden subgroup problem
The skrytý problém s podskupinou (HSP) je tématem výzkumu v matematika a teoretická informatika. Rámec zachycuje problémy jako factoring, diskrétní logaritmus, izomorfismus grafu a nejkratší vektorový problém. Díky tomu je to v teorii kvantového výpočtu obzvláště důležité, protože Shorův kvantový algoritmus pro factoring je v podstatě ekvivalentní problému skryté podskupiny pro konečné abelianské skupiny, zatímco ostatní problémy odpovídají konečným skupinám, které nejsou Abelianské.
Problémové prohlášení
Vzhledem k skupina G, a podskupina H ≤ Ga sada X, říkáme funkci F : G → X schovává podskupina H pokud pro všechny G1, G2 ∈ G, F(G1) = F(G2) právě tehdy G1H = G2H. Ekvivalentně funkce F je konstantní na kosety z H, i když je to mezi různými kosety z H.
Skrytý problém podskupiny: Nechte G být skupina, X konečná množina a F : G → X funkce, která skrývá podskupinu H ≤ G. Funkce F je poskytována prostřednictvím věštec, který používá Ó(log |G| + přihlásit |X|) bity. Využití informací získaných z hodnocení F prostřednictvím svého věštce určit generující sadu pro H.
Zvláštní případ je kdy X je skupina a F je skupinový homomorfismus v jakém případě H odpovídá jádro z F.
Motivace
Problém skryté podskupiny je obzvláště důležitý v teorii kvantové výpočty z následujících důvodů.
- Shorův kvantový algoritmus pro factoring a diskrétní logaritmus (stejně jako několik jeho rozšíření) spoléhá na schopnost kvantových počítačů vyřešit HSP pro konečné abelianské skupiny.
- Existence efektivní kvantové algoritmy pro HSP jistě neabelovské skupiny by znamenalo efektivní kvantové algoritmy pro dva hlavní problémy: problém grafového izomorfismu a jisté nejkratší vektorové problémy (SVP) v mřížích. Přesněji řečeno, efektivní kvantový algoritmus pro HSP pro symetrická skupina dá kvantový algoritmus pro izomorfismus grafu.[1] Efektivní kvantový algoritmus pro HSP pro dihedrální skupina dá kvantový algoritmus pro poly (n) jedinečný SVP.[2]
Algoritmy
Tady je polynomiální čas kvantový algoritmus pro řešení HSP přes konečný Abelianské skupiny. (V případě skrytého problému podskupiny znamená „polynomiální časový algoritmus“ algoritmus, jehož doba běhu je polynomem logaritmu velikosti skupiny.) Shorův algoritmus aplikuje konkrétní případ tohoto kvantového algoritmu.
U libovolných skupin je známo, že problém skryté podskupiny je řešitelný pomocí polynomiálního počtu vyhodnocení věštce.[3] Tento výsledek však umožňuje kvantovému algoritmu dobu běhu, která je v log | exponenciálníG|. Chcete-li navrhnout efektivní algoritmy pro izomorfismus grafu a SVP, potřebujete algoritmus, pro který je počet hodnocení Oracle i doba běhu polynomický.
Existence takového algoritmu pro libovolné skupiny je otevřená. Kvantové polynomiální časové algoritmy existují pro určité podtřídy skupin, jako jsou polopřímé produkty některých Abelianské skupiny.
„Standardní“ přístup k tomuto problému zahrnuje: vytvoření kvantového stavu , následný kvantová Fourierova transformace do levého registru, po kterém se tento registr vzorkuje. Ukázalo se, že tento přístup není dostatečný pro skrytý problém podskupiny pro symetrickou skupinu.[4][5]
Viz také
Reference
- ^ Mark Ettinger; Peter Høyer. "Kvantum pozorovatelné pro problém izomorfismu grafu". arXiv:quant-ph / 9901029.
- ^ Oded Regev. "Kvantové výpočty a mřížkové problémy". arXiv:cs / 0304005.
- ^ Mark Ettinger; Peter Hoyer; Emanuel Knill. Msgstr "Složitost kvantového dotazu skrytého problému podskupiny je polynomiální". Dopisy o zpracování informací. 91: 43–48. arXiv:quant-ph / 0401083. doi:10.1016 / j.ipl.2004.01.024.
- ^ Sean Hallgren; Martin Roetteler; Pranab Sen. „Omezení stavů kvantové kosety pro izomorfismus grafů“. arXiv:quant-ph / 0511148.
- ^ Cristopher Moore, Alexander Russell, Leonard J. Schulman. „Symetrická skupina vzdoruje silnému Fourierovu vzorkování: část I“. arXiv:quant-ph / 0501056.CS1 maint: více jmen: seznam autorů (odkaz)