Posterior: Bibliography Arriba: Algoritmo cuántico para el Anterior: Elementos con orden potencia

Elementos con orden arbitrario

Dejemos de suponer que el orden $r$ de $m$ sea una potencia de 2 en $\Phi(n)$. Siguiendo la misma línea que en el caso anterior, sea $V_m$ definido como en la ec. (11). Sea $\mbox{\bf s}_1=(H^{\otimes \kappa}\otimes I^{\otimes \nu})(\mbox{\bf e}_{\mbox{\scriptsize\bf0}}\otimes \mbox{\bf e}_{\mbox{\scriptsize\bf0}})$ y $\mbox{\bf s}_2=V_m(\mbox{\bf s}_1)$. Reagrupando los términos según se hizo en la ec. (12) se puede escribir

$$\mbox{\bf s}_2= \frac{1}{\sqrt{2}^{\kappa}}\sum_{j=0}^{r-1}\... ...\mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}_{m^j}}.$$ (16)

donde los conjuntos $J_j$ son clases de equivalencia, congruentes con $j$, módulo $r$, pero ahora no son de la misma cardinalidad. Si $u=2^{\kappa}\mbox{ mod }r$ y $s=(2^{\kappa}-u)/r$ entonces $u$ clases tendrán $s+1$ elementos y las restantes tendrán $s$ elementos. Definamos $s_j=s+1$ para $j=1,\ldots,u$ y $s_j=s$ para $j=u+1,\ldots,r-1,0$. Entonces el estado que representa el tomar una medición, como en la ec. (13), es, para algún $j_0\in[\![0,r-1]\!]$:

$$\mbox{\bf s}_3= \sum_{i=0}^{2^{\kappa}-1} g(i)\mbox{\bf e}_{... ...x{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}_{m^{j_0}}}.$$ (17)

donde $g:i \mapsto \left\{\begin{array}{cl} \frac{1}{\sqrt{s_{j_0}}} & \mbox{ si }i \in J_{j_0} \\ 0 & \mbox{ si }i\not\in J_{j_0} %%\\ \end{array}\right.$

Calculando la transformada inversa discreta de Fourier y reagrupando términos, como en la ec. (14), se obtiene

$$\mbox{\bf s}_4 = \check{\mbox{\bf s}_3} = \frac{1}{\sqrt{2^{... ...x{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}_{m^{j_0}}}.$$ (18)

pero en este caso el coeficiente que involucra a la suma interior nunca se anula (como $r$ no necesariamente divide a $2^{\kappa}$, aquí no se está sumando un ``juego completo'' de raices $s_{j_0}$-ésimas de la unidad). Al tomar una medición del primer qubit, la probabilidad de que se elija a $\mbox{\bf e}_{\ell}\otimes \mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}_{m^{j_0}}}$ es entonces

$$P(\ell)=\frac{1}{\sqrt{2^{\kappa}s_{j_0}}}\left\vert\sum_{k=0... ...p}\left(-\frac{2\pi i \ell k r}{2^{\kappa}}\right)\right\vert^2$$

y los máximos de esos valores corresponden a enteros $\ell = \mbox{\tt EnteroM\'asPr\'oximo}\left(\frac{k 2^{\kappa}}{r}\right)$, $k=0,\ldots,r-1$. Supongamos que tras una medición se haya elegido $\mbox{\bf e}_{\ell_k}\otimes \mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}_{m^{j_0}}}$, con $\ell_k=\mbox{\tt EnteroM\'asPr\'oximo}\left(\frac{k 2^{\kappa}}{r}\right)$. Entonces, al dividir ese índice entre $2^{\kappa}$ se obtiene $\frac{\ell_k}{2^{\kappa}} \sim \frac{k}{r}$, y de aquí se quiere conocer $r$. Para esto hay que recordar la noción de fracciones continuadas.

Si $\frac{p}{q}$ es un número racional no-negativo, su fracción continuada es

$$\frac{p}{q} = a_0 + \frac{1}{a_1 + \frac{1}{\cdots + \frac{1}{a_v}}} = \left[a_0,a_1,\ldots,a_v\right]$$ (19)

donde $a_0,a_1,\ldots,a_v$ son enteros no-negativos. Para cada $w\leq v$, la fracción continuada $\left[a_0,a_1,\ldots,a_w\right]$ se dice ser el $w$-ésimo convergente de $\frac{p}{q}$, y, en efecto, cada convergente es una aproximación racional a $\frac{p}{q}$. El algoritmo para calcular fracciones continuadas es directo:

Entrada.

$\frac{p}{q}\in\mathbb{Q}$.

Salida.

$\left[a_0,a_1,\ldots,a_v\right]$: fracción continuada que representa a $\frac{p}{q}\in\mathbb{Q}$.

Procedimiento

FracciónContinuada$(\frac{p}{q})$

1. Sean inicialmente $\mbox{\it lst}:=[]$ (la lista vacía) y $\mbox{\it xact}:=\frac{p}{q}$.
2. Mientras el denominador de $\mbox{\it xact}$ sea mayor que 1 hágase
   1. sea $i:=\mbox{\tt ParteEntera}(\mbox{\it xact})$;
   2. escríbase $\frac{p_1}{q_1}=\mbox{\it xact}$;
   3. actualícese $\mbox{\it xact}:= \frac{q_1}{p_1 - i q_1}$;
   4. actualícese $\mbox{\it lst}:=\mbox{\it lst}*[i]$.
3. Actualícese $\mbox{\it lst}:=\mbox{\it lst}*[\mbox{\it xact}]$.
4. Dése como resultado $\mbox{\it lst}$.

Así pues, luego de haber realizado una medición y haber obtenido el valor $\frac{\ell_k}{2^{\kappa}}<1$, se calcula su fracción continuada $\left[a_0,a_1,\ldots,a_v\right]$ ($a_0=0$) y los correspondientes convergentes $\left[c_0,c_1,\ldots,c_v\right]$ (también $c_0=0$), y entre éstos se selecciona a aquellos cuyos denominadores $r_j$ sean menores que $n$, los cuales han de ser divisores del orden $r$ de $m$.

En resumen, esta vez el algoritmo para localizar divisores de órdenes de elementos es el siguiente:

Entrada.

$n\in\mathbb{N}$, $m\in\Phi(n)$.

Salida.

$r$ tal que $r\vert o(m)$.

Procedimiento

DivisorOrden$(n,m)$

1. Sea $\nu:=\lceil \log_2 n\rceil$, $\kappa=\lceil 2 \log_2 n\rceil$.
2. Defínase $V_m:\mathbb{H}_{\kappa+\nu}\to \mathbb{H}_{\kappa+\nu}$ como en la ec. (11).
3. Sea $\mbox{\bf s}_1:=(H^{\otimes \kappa}\otimes I^{\otimes \nu})(\mbox{\bf e}_{\mbox{\scriptsize\bf0}}\otimes \mbox{\bf e}_{\mbox{\scriptsize\bf0}})$.
4. Sea $\mbox{\bf s}_2 := V_m(\mbox{\bf s}_1)$.
5. Sea $\mbox{\bf s}_3 := \sum_{i=0}^{2^{\kappa}-1} g(i)\mbox{\bf e}_{\mbox{\scriptsize... ...}_{i}}\otimes \mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}_{m^{j_0}}}$ el estado equivalente a ``tomar una medición'' en $\mbox{\bf s}_2$. Entonces $g$ queda determinada como en la ec. (17).
6. Sea $\mbox{\bf s}_4 := \mbox{\tt TIDF}(2^{\kappa},\mbox{\bf s}_3)$ la transformada inversa discreta de Fourier de $\mbox{\bf s}_3$.
7. Sea $\mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}_{\ell_k}}\otimes \mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}_{m^{j_0}}}$ una medición de $\mbox{\bf s}_4$.
8. Si $\ell_k==0$ repítase desde el paso 3. En otro caso
   1. sea $\left[a_0,a_1,\ldots,a_v\right]:=\mbox{\tt Fracci\'onContinuada}\left(\frac{\ell_k}{2^{\kappa}}\right)$;
   2. sea $\left[c_0,c_1,\ldots,c_v\right]$ la lista de convergentes; y
   3. dése como resultado la lista de denominadores, de los convergentes, que sean menores que $n$.

Habiendo obtenido divisores de órdenes, se puede proceder a obtener los órdenes de manera similar a como se bosquejó en el procedimiento OrdenPotencia2, mas en este caso hay que llevar un recuento de las varias posibilidades de divisores que arroja el procedimiento DivisorOrden descrito arriba.

Posterior: Bibliography Arriba: Algoritmo cuántico para el Anterior: Elementos con orden potencia