Problema de Simon

En àlgebra abstracta i computació quàntica, el problema plantejat per Daniel R. Simon (conegut com a problema de Simon) és un cas particular del problema del subgrup amagat (Hidden Subgroup Problem, HSP), el qual ha segut útil per al plantejament d'algoritmes quàntics que són eficients, a diferència dels seus homòlecs clàssics, permetent resoldre problemes teòrics proposts en les últimes décades les solucions de les quals són de vital importància en el camp de la computació quàntica.

Per a resoldre el problema de Simon s'han desenrollat algoritmes clàssics que utilisen força bruta, dels quals se sap que la seua complexitat és exponencial. Per a trobar una  solució eficient s'ha recorregut a algoritmes quàntics, com el propost pel mateix Simon, que la seua complexitat és polinomial, reduint aixina el temps de còmput de forma significativa.

S'han desenrollat algoritmes quàntics per a atres casos particulars del problema del subgrup amagat, pero solament són eficients aquells que treballen sobre grups abelianos (com el de Simon). Per als grups no abelianos encara no s'han trobat algoritmes quàntics eficients, de fet estos no apleguen a tindre millor eixercite que les solucions clàssiques.

Conceptes previs

Relació d'equivalència

Una relació d'equivalència sobre un grup $G$ és una relació $E\subseteq G\times G$ que complix les propietats:

1. Reflexiva: $gEg$ per a cada $g$ que pertany a $G$.
2. Simètrica: Si $gEt$ llavors $tEg$.
3. Transitiva: Si $gEt$ i $tEu$ llavors $gEu$.

Els elements $g,t$ i $u$ són elements de $G$; note que cada element de $G$ està envolt en un requeriment 1,2 o 3.

Congruència entre conjunts

Congruència per esquerra

Siga $H$ un subgrup de $G$, llavors dos elements $g_i$ i $g_j$ de $G$ són congruents mòdul $H$ si hi ha un element $h_k$ per al qual $g_i=g_j{h}_k.$

Congruència per dreta

Siga $H$ un subgrup de $G$, llavors dos elements $g_i$i $g_j$ de $G$ són congruents mòdul $H$ si hi ha un element $h_k$ per al qual $g_i=h_k{g}_j.$

Suponent que $H$ és un subgrup de $G$, la congruència mòdul $H$ és una relació d'equivalència en $G$. La congruència mòdul $H$ particiona a $G$ en una colecció de classes d'equivalència que són disyuntas 2 a 2. Cada classe està formada per elements que són congruents entre sí.

Cosets

Siga $H$ un subgrup de $G$, i siga $g\in G$. El coset per esquerra de $g$ respecte a $H$ és el conjunt $gH=\{g{h}_1,g{h}_2,\mathrm{...},g{h}_k,\mathrm{...}\}$ sent $H=\{h_1,h_2,\mathrm{...},h_k,\mathrm{...}\}$. Aixina mateix es definix el coset per dreta com el conjunt $Hg=\{h_{1}g,h_{2}g,\mathrm{...},h_{k}g,\mathrm{...}\}$ sent $H=\{h_1,h_2,\mathrm{...},h_k,\mathrm{...}\}$.

Note que $g_i\equiv$$g_j$(mod $H$), si i només si, les seues respectives classes d'equivalència o cosets són iguals, és dir, $g_{i}H=g_{j}H$. Per a obtindre distints cosets, s'usaran elements $g_i$i $g_j$que siguen incongruents mòdul $H$.

Periodicitat de funcions que actuen sobre grups

Definició

Una funció f es diu periòdica si, per a alguna constant P diferent de zero, es té que:

$f(x+P)=f(x)$

Per a tots els valors de x en el domini de f. Una constant P distinta de zero per a la qual es complixca la propietat anterior es denomina periodo de la funció. La menor constant positiva P en esta propietat, es denomina periodo fonamental (també periodo primitiu, periodo bàsic o periodo primer). A sovint, el "periodo" d'una funció s'utilisa per a indicar el seu periodo fonamental. Una funció en periodo P es repetirà en intervals de llongitut P, i estos intervals a voltes també es coneixen com a periodos de la funció.

Importància

Encara que en principi puga no semblar-ho, lo cert és que les funcions periòdiques es relacionen de manera directa en un dels problemes més difícils de resoldre fins al moment: la descomposició d'un número entero en factors primers.

Aun cuando qualsevol número entero té una descomposició única en un producte d'número primo, trobar dits factors primers és un problema difícil. De fet, la seguritat de les transaccions en llínea es basa en el criptosistema de clau pública RSA, la força de la qual residix en la dificultat de factorizar números grans. En la pràctica factorizar sancers en centenars de dígits és pràcticament impossible, el número més gran factorizado fins a la data és RSA-768, un número de 232 sifres decimals, el qual va ser factorizado en 2009. En l'actualitat RSA usa número primo de l'orde de $10^{300}$ i $10^{600}$.

Des de la década dels 70 és conegut pels matemàtics que factorizar es fa més fàcil si es pot resoldre un atre problema difícil: trobar el periodo de la funció exponencial modular. El problema de Simon està estretament relacionat en este problema, ya que l'algoritme de Simon, un algoritme quàntic provabilístic en una complexitat polinomial, resol el problema de la determinació del periodo d'una funció periòdica $f:\{0,1{\}}^n\to \{0,1{\}}^n$ (el problema de la factorización es pot reduir a este últim). En contrast, l'algoritme clàssic té una complexitat exponencial. L'implicació de l'us d'estes tècniques teòriques és la vulnerabilitat de l'informació protegida en l'actualitat per métodos tipo RSA.

Problema del subgrup amagat

Història

El problema del subgrup amagat sorgix en 1994, quan Peter Shor Williston, professor nortamericà de matemàtiques aplicades, basant-se en el treball de David Elieser Deutsch, professor israelita i pioner de la computació quàntica, i Daniel R. Simon, master en ciències de la computació de l'Universitat de Toronto, va trobar un algoritme quàntic que podia factorizar sancers exponencialment més ràpit que els métodos clàssics coneguts. Alexei Kitaev, un professor de física rus-nortamericana, va concloure que estos algoritmes encaixen en un marc per a trobar generadors de subgrups que són ocultats per mig d'una funció.

Definició

La definició formal del problema del subgrup amagat (HSP) és:

Input: Siga $(G,f)$, a on $G$ és un grup i $f$ una funció. $f:G\to X$, llavors existix $H\subseteq G$ tal que $f$ és constant sobre els cosets de $H$.

Problema: Trobar $H$.

Eficiència quàntica

Si $G$ és un grup Abeliano finito, la determinació del problema del subgrup amagat pot ser teòricament resolta per mig d'un algoritme quàntic de manera eficient, és dir en un orde de complexitat $O[poly(\log \mid G\mid )]$. No obstant, no es té coneiximent d'una solució quàntica eficient que es puga implementar quan es tracta en grups finitos no-Abelianos.

Eixemple

Definint el tamany d'un circuit quàntic com el número mínim d'operacions elementals que deuen compondre's per a obtindre el circuit, i definint un Qubit com un vector de mòdul unitat en un espai vectorial complex bidimensional; suponga que es vol determinar l'orde d'un grup finito Abeliano donat un conjunt generador. Donat un grup $G$ és possible representar cada element del grup utilisant aproximadament $\log \mid G\mid$ Qubits.

Per a resoldre de manera eficient este problema per mig d'un algoritme quàntic és necessari que el tamany del circuit quàntic que va a computar l'orde de $G$ siga de tamany polinomial en $\log \mid G\mid$, ya que $G$ varia en tota la família de grups Abelianos finitos. Finalment es requerix una “Classe uniforme d'algoritmes”, la qual afirma que per a un problema de tamany $n$, existix una màquina de Turing que dau $n$, pot produir la descripció del circuit en un número de passos igual a un polinomi en $n$. Açò permet assegurar que (en teoria)  és possible construir una màquina explícita per a resoldre cada problema en un temps polinomial en el tamany del problema.