\documentclass[11pt,leqno]{article}
\usepackage{amssymb, amsmath} 
\usepackage{latexsym} 
%\usepackage{graphics} 
\usepackage{graphicx} 
\usepackage[hyphens]{url}
%\def\UrlBreaks{\do\/\do-}
\expandafter\def\expandafter\UrlBreaks\expandafter{\UrlBreaks% save the current one
  \do\a\do\b\do\c\do\d\do\e\do\f\do\g\do\h\do\i\do\j%
  \do\k\do\l\do\m\do\n\do\o\do\p\do\q\do\r\do\s\do\t%
  \do\u\do\v\do\w\do\x\do\y\do\z\do\A\do\B\do\C\do\D%
  \do\E\do\F\do\G\do\H\do\I\do\J\do\K\do\L\do\M\do\N%
  \do\O\do\P\do\Q\do\R\do\S\do\T\do\U\do\V\do\W\do\X%
  \do\Y\do\Z\do\*\do\-\do\~\do\'\do\"\do\-}%

\usepackage{xcolor}
\usepackage{hyperref} 

\usepackage{lmodern}

\usepackage[braket,qm]{qcircuit}


%\usepackage[notcite,notref,color]{showkeys}


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	SPANISH
%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[spanish]{babel}
\usepackage[T1]{fontenc} 
\usepackage[latin1]{inputenc}
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	FORMAT
%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setlength{\textheight}{23.0cm}
\setlength{\textwidth}{15.75cm}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	COUNTERS
%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcounter{ejeno}
\setcounter{ejeno}{1}


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	MACROS
%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\R}{{\mathbb R}} 
\newcommand{\C}{{\mathbb C}} 
\newcommand{\N}{{\mathbb N}} 
\newcommand{\Z}{{\mathbb Z}} 
\newcommand{\Q}{{\mathbb Q}} 

\newcommand{\ccero}{|0\rangle} 
\newcommand{\uuno}{|1\rangle} 


\newcommand{\ejer}{\ \par\vspace{-7pt}{\bf\number\value{ejeno})\ }\addtocounter{ejeno}{1}}



\begin{document}
\pagestyle{myheadings}
\markboth{}{\rm\textsf{\jobname}\qquad\hfill}

Esta última hoja está dedicada al algoritmo cuántico más famoso. Su fama radica en que, en caso de implementarse, lograría romper el criptosistema RSA que es la base de muchos sistemas de seguridad.
Es muy posible que te hayan hablado de este criptosistema en uno o más cursos del grado. 
En cualquier caso, es fácil encontrar buenas referencias (como \cite{rosen}) y deberías incluir una pequeña descripción en tu trabajo para dar un contexto al algoritmo. 

\ejer
Escribe unas líneas explicando el criptosistema
RSA y su relación con la factorización.
\medskip

La criptografía se basa en gran medida en ``funciones trampa'', operaciones que son fáciles de hacer y difíciles de deshacer sin información adicional. En relación con RSA, en cualquiera de nuestros ordenadores sería sencillo multiplicar dos primos $p$ y $q$ de miles de cifras  (incluso de más) para obtener $N=pq$. sin embargo, fuera de elecciones especiales, ningún superordenador es capaz de recuperar $p$ y $q$ a partir de $N$. Ya para cientos de cifras se considera que el sistema es seguro. 

El \emph{algoritmo de Shor} que trataremos en esta hoja es un algoritmo introducido en 1997 por P.W.~Shor \cite{shor} para encontrar factores no triviales de un número impar $N\in\Z_{>2}$. En un ordenador clásico sería extremadamente lento e inútil, mientras que, teóricamente, en un ordenador cuántico sería mucho más rápido que los algoritmos conocidos para números grandes. 
Por otro lado, su implementación práctica es a día de hoy un problema no resuelto. Hasta 2001 el mayor número factorizado con el algoritmo de Shor en un ordenador cuántico era $N=15$ y creo que todavía no se ha llegado a ninguno de tres cifras. La dificultad no es un obstáculo teórico (en este caso, no hay ``oráculos'' no descritos), sino práctica, porque se necesitan muchos qubits entrelazados y puertas cuánticas que funcionen libres de errores durante cierto tiempo\footnote{Posiblemente, el mayor impedimento actual para que la computación cuántica se vuelva cotidiana es que no hay buenos sistemas para impedir ruido y errores, lo que limita mucho los algoritmos que se pueden usar.}.
\medskip

Comencemos con la descripción matemática del algoritmo de Shor para después adentrarnos en la realización cuántica de uno de sus pasos. Debes tener en mente que calcular el máximo común divisor de números grandes, el cual indicaremos con $\gcd$, y calcular potencias módulo un número grande, admite algoritmos eficientes en un ordenador clásico (en el primer caso, es el algoritmo de Euclides). 

El algoritmo de Shor es probabilista en el sentido de que a veces no funciona y hay que probar de nuevo. Además la parte cuántica añade otra componente probabilista. Los pasos son los siguientes:
\begin{enumerate}\setlength{\itemsep}{0pt}
\renewcommand{\labelenumi}{\Alph{enumi}.}
\item 
Se elige un entero al azar $a\in [2,N)$. Si $\gcd(a,N)\ne 1$, es un factor no trivial de $N$ y el algoritmo termina. 
\item
Se calcula el orden $r$ de $a$ en $(\Z/NZ)^*$. Es decir, el menor $r\in\Z^+$ tal que $a^r\equiv 1\pmod{N}$. 
\item
Si $r$ es impar o si $r$ es par con $a^{r/2}\equiv -1\pmod{N}$, el algoritmo no funciona y hay que probar con otro $a$. En otro caso, 
$\gcd\big(N,a^{r/2}+1\big)$ es un factor no trivial de $N$. 
\end{enumerate}

\ejer
Explica por qué si $r$ es par y $a^{r/2}\not\equiv -1\pmod{N}$, realmente $\gcd\big(N,a^{r/2}+1\big)$ es un factor no trivial de $N$. 

\ejer
Aplica el algoritmo anterior para $N=15$ con $a=7$. ¿Qué factor de $N$ se obtiene?
\medskip

Al ser probabilista, es crucial preguntarse si es muy improbable que para un $a$ elegido al azar se cumpla que su orden $r$ sea par y, a la vez, que $a^{r/2}\not\equiv -1\pmod{N}$. La respuesta es que no, pero una prueba detallada nos obligaría a dar un rodeo y no entraremos en ello. Está basada el isomorfismo $(\Z/pq\Z)^*\cong C_{p-1}\oplus C_{q-1}$
con ${-\bar{1}}\mapsto \big(\frac{p-1}{2},\frac{q-1}{2}\big)$
donde $p,q>2$ son primos y $C_k$ es el grupo cíclico de $k$ elementos. 

\ejer
Usando el isomorfismo anterior, comprueba que para $N=15$ todo $\bar{a}\in (\Z/N\Z)^*$ distinto de $\bar{1}$ tiene orden $r$ par y halla cuántas clases cumplen $a^{r/2}\equiv -1\pmod{N}$.

\medskip

En un ordenador clásico, A y C son fáciles de implementar, sin embargo no se conocen algoritmos eficientes para calcular el orden que se pide en~B. Algunos criptosistemas se basan en este hecho. Por otro lado, lo que mostró Shor es que hay un algoritmo cuántico teórico eficiente para resolver este problema. Está estrechamente relacionado con otro  algoritmo llamado \emph{estimación de fase cuántica} y con la \emph{transformada de Fourier cuántica}. Por brevedad, no aparecerán explícitamente. Si tienes curiosidad mira \cite{NiCh}. 
\medskip

Antes de nada, recordaremos una variante del \emph{núcleo de Dirchlet} de cursos de análisis y un resultado de aproximación diofántica del curso de teoría de números. No hace falta que repases nada. 

\ejer
Para $M\in\Z^+$ y $x\in \R$ sea $D_M(x)=\frac 1M\sum_{k=0}^{M-1}e^{2\pi i kx}$. 
Prueba 
$|D_M(x)|^2=\frac{\sen^2(\pi Mx)}{M^2\sen^2(\pi x)}$ para $x\not\in\Z$. 
En particular, $D_M(a/q)=0$ para $a\in\Z$, $q\in\Z^+$ si $q\mid M$ y $q\nmid a$. 
\medskip

Esto asegura que  $|D_M(x)|^2$, para $x\in[-1/2,1/2]$ y $M$ grande, es prácticamente $1$ cuando $|x|$ es bastante menor que $M^{-1}$ y es pequeño si $|x|$ es bastante mayor que $M^{-1}$. Si quieres, haz un dibujo con $M=40$, para que veas el aspecto. 
\medskip

Lo que tienes que recordar de teoría de números es más profundo. Si tenemos un número real $\alpha$ y una fracción irreducible $a/q$ que lo aproxima bien en el sentido de que $\big|\alpha-\frac aq\big|<\frac{1}{2q^2}$, entonces necesariamente $a/q$ es una convergente de la fracción continua de $\alpha$ (si quieres ver una prueba, mira \cite[Prop.\, 2.2.6]{ch_nt}, \cite{MiTa} o  \cite{rose}). Las convergentes son fáciles de determinar algorítmicamente y tienen denominadores que crecen exponencialmente, por tanto 
hay del orden de $\log N$ que cumplen $q<N$, lo cual hace que sea fácil hallar y almacenar todas las que verifican esta condición incluso si $N$ tiene cientos de cifras.
No hace falta que recuerdes cómo se hallaban las fracciones continuas. Solo que sepas que hay un algoritmo sencillo y eficiente para determinar todas las fracciones irreducibles que cumplen $\big|\alpha-\frac aq\big|<\frac{1}{2q^2}$ con $q<N$ aunque $N$ sea gigantesco. Es eso lo que debes reflejar en tu trabajo, acompañado de referencias adecuadas. 

\

Pasamos por fin a la realización cuántica del cálculo del orden de $a$ módulo $N$. Responde a un circuito de la forma:

\[
 \Qcircuit @C=.65em @R=.5em {
  &\lstick{\ket{0}}   & \gate{H} & \qw & \qw               & \qw               & \qw &  &\cdots{\ }& & \ctrl{5}             & \multigate{3}{F} & \qw  & \meter  
    \inputgroupv{1}{4}{25pt}{24pt}{m\ \ }\gategroup{1}{2}{9}{11}{11pt}{--}
  \\
  &\lstick{\vdots\ \ } & \vdots   &     &                   &                   &     &        & &                        &    \pureghost{F} &      & &\vdots &     
  \\
  &\lstick{\ket{0}}    & \gate{H} & \qw & \qw               & \ctrl{3}          & \qw & &\cdots{\ } & & \qw                    &        \ghost{F} & \qw  & \meter  
  \\
  &\lstick{\ket{0}}    & \gate{H} & \qw & \ctrl{2}          & \qw               & \qw & &\cdots{\ } & & \qw                    &        \ghost{F} & \qw  & \meter  
  \\
  & && &&&  & & & &  & &  &   
  \\
  &\lstick{\ket{0}}    &  \qw  & \qw & \multigate{3}{U_0} & \multigate{3}{U_1} & \qw & &\cdots{\ } & & \multigate{3}{U_{m-1}} & \qw  &\qw &\qw 
  \inputgroupv{6}{9}{25pt}{20pt}{n\ \ }
  \\ 
  &\lstick{\vdots\ \ }  &  \vdots  &  & \pureghost{U_0}  & \pureghost{U_1} &  & &\vdots{\ \ } & & \pureghost{U_{m-1}} & &\vdots 
  \\ 
  &\lstick{\ket{0}}    &  \qw  & \qw & \ghost{U_0}  & \ghost{U_1} & \qw & &\cdots{\ } & & \ghost{U_{m-1}} & \qw &\qw &\qw 
  \\ 
  &\lstick{\ket{0}}    &  \gate{X}  & \qw & \ghost{U_0}  & \ghost{U_1} & \qw & &\cdots{\ } & & \ghost{U_{m-1}} & \qw &\qw &\qw
 }
\]
La línea de puntos no indica nada, es solo para referencia posterior. En la entrada, como se indica, hay $m+n$ ceros. Tomando $m=2n+1$ ya se tiene un algoritmo aceptable y con $m$ mayor se consigue que el resultado sea menos probabilista. La $n$  hay que escogerla de forma que $2^n$ sea mayor que $N$. Entenderemos 
$\ket{a^k}$ como una abreviatura del registro de $n$ qubits~$\ket{R}$ donde $R$ es el resto al dividir $a^k$ por $N$. Esto es, las potencias las consideraremos siempre módulo $N$. 

Con lo que sabes de hojas anteriores, el paso por las puertas de Hadamard y la puerta $X$ (también llamada NOT) da lugar al estado 
\[
 \ket{\phi}
 =
 \frac{1}{2^{m/2}}
 \sum_{k=0}^{2^m-1}
 \ket{k}\otimes\ket{1}
\]
donde $\ket{k}$ y $\ket{1}$ se entienden, respectivamente, como registros de $m$ y $n$ qubits. 
Si no lo ves claro, piénsalo e incluye unas líneas para explicártelo a ti misma. 

Definimos los estados normalizados 
\[
 \ket{u_j}
 =
 \frac{1}{\sqrt{r}}
 \sum_{\ell =0}^{r-1}
 e^{-2\pi i\ell j/r}\ket{a^\ell},
 \qquad\text{con }j=0,1,\dots, r-1.
\]
Aunque no sepamos construirlos, porque no conocemos $r$, es posible escribir $\ket{\phi}$ en términos de ellos. 

\ejer
Prueba 
\[
 \ket{\phi}= 
 \frac{1}{2^{m/2}\sqrt{r}}
 \sum_{k=0}^{2^m-1}\sum_{j=0}^{r-1}
 \ket{k}\otimes \ket{u_j}.
\]
\medskip

Si $k=b_{m-1}2^{m-1}+\dots +b_12^1+b_0$, consideremos para cada $0\le j<m$ la puerta cuántica $U_j$ que efectúa la multiplicación por $a^{2^j}$ módulo $N$ controlada por $b_j$. Es decir, para $0\le \ell<2^n$ se tiene 
\[
 U_j\ket{\ell}
 =
 \begin{cases}
  \ket{a^{2^j}\ell\ (\textrm{mód}\ N)} 
  &\text{si }
  0\le \ell<N\text{ y }b_j=1,
  \\
  \ket{\ell}&\text{en otro caso.}
 \end{cases}
\]

\ejer 
Muestra que $\ket{u_\ell}$ es un autovector de $U_j$ con autovalor $e^{2\pi i b_j2^j \ell /r}$. Concluye con ello que la parte del circuito encerrada en línea de puntos da lugar al estado
\[
 \ket{\psi}
 =
 \frac{1}{2^{m/2}\sqrt{r}}
 \sum_{k=0}^{2^m-1}\sum_{j=0}^{r-1}
 e^{2\pi i kj/r}
 \ket{k}\otimes \ket{u_j}. 
\]
\medskip

La puerta $F$ del circuito actúa sobre registros de $m$ qubits de la forma siguiente:
\[
 F:\,
 \ket{k}\longmapsto 
 \frac{1}{2^{m/2}}
 \sum_{\ell=0}^{2^m-1}
 e^{-2\pi i k\ell/2^m}\ket{\ell}.
\]
Si conoces la DFT del análisis de Fourier discreto, notarás la analogía. 

\ejer
Prueba que $F$ es realmente una puerta cuántica, esto es, que define una aplicación lineal unitaria. 

\ejer
Establece la identidad
\[
 \big(F\otimes I^{\otimes n}\big)\ket{\psi}
 =
 \frac{1}{\sqrt{r}}
 \sum_{k=0}^{2^m-1}\sum_{j=0}^{r-1}
 D_{2^m}\Big(
 \frac{j}{r}-\frac{k}{2^m}
 \Big)
 \ket{k}\otimes \ket{u_j}. 
\]
\medskip

Supongamos que $\big| D_{2^m}(x)\big|^2$ es exactamente la función característica de $|x|<2^{-m}$ en lugar de una aproximación suya, entonces, después de la medición que indica el circuito, si obtenemos $\ket{k_0}$, el estado $\big(F\otimes I^{\otimes n}\big)\ket{\psi}$  colapsará a un estado proporcional a 
\[
 \ket{k_0}\otimes \sum_{j\in J}\ket{u_j}
 \qquad\text{con}\quad
 J=\Big\{
 j\,:\, \Big|
 \frac jr -\frac{k_0}{2^m}
 \big|<\frac{1}{2^m}
 \Big\}.
\]

\ejer
Explica por qué si $m>2n$ estamos en condiciones de aplicar el resultado de teoría de números con $\alpha={k_0/2^m}$ y, a partir de $k_0$ (lo que hemos obtenido en la medición), calcular todas las posibilidades para $j/r$ con denominador menor que $N$. 
\medskip

Concluimos con unos comentarios acerca de dos cabos sueltos en esta parte final. Realmente, $\big| D_{2^m}(x)\big|^2$ no es la función característica de $|x|<2^{-m}$. Si lo piensas, todo lo que necesitamos es que sean muy pequeño cuando $|x|>1/(2r^2)$, porque esto se traduce en que haya una probabilidad muy pequeña de que obtengamos $j/r$ erróneos. Se puede conseguir con precisión arbitraria tomando $m$ muy por encima de $2n$ para que el decaimiento de $D_{2^m}$ sea mayor.   

El otro cabo suelto es más importante. Consiste en que si $j$ y $r$ tienen factores comunes, entonces $j/r$ no es irreducible y no podemos recuperar $r$ a partir de los posibles valores simplificados para $j/r$, que  es lo que nos dan las convergentes. En vez de $r$ se obtendría un divisor de~$r$. 
En breve, el denominador de $j/r$ como elemento de $\Q$ no es $r$ si la fracción no es irreducible. 
Ahora bien, si repitiendo el algoritmo unas cuantas veces, tenemos suficientes divisores de~$r$, se puede reconstruir $r$ calculando el mínimo común múltiplo. En el apartado 
{\sl Continued fraction algorithm to retrieve the period} 
de \cite{wiki_shor}
está explicado este punto. 
Por supuesto, podríamos tener muy mala suerte y con ejecuciones sucesivas obtener siempre el mismo divisor, pero eso tiene una probabilidad despreciable.
\medskip

El resumen de la parte cuántica del algoritmo de Shor para hallar el orden $r$ de $a$, es que después de aplicar el circuito, en la medición obtendremos un registro $\ket{k_0}$ de $m$ qubits. Considerando los denominadores menores que $N$ de las convergentes de $\alpha =k_0/2^m$ obtendremos candidatos a valores de $r$ o divisores suyos. Con suficientes divisores es posible reconstruir $r$. Es fácil decidir si un candidatos a $r$ es realmente $r$, simplemente hay que comprobar $a^r\equiv1\pmod{N}$. Recordemos que halla restos de potencias es fácil en un ordenador convencional. 


\

\begin{center}
\noindent\rule{0.95\textwidth}{1.1pt}
\end{center}


\paragraph{Tarea a entregar.}
Escribe un documento que combine las soluciones de los ejercicios anteriores. 
Trata de ajustarte a 8 páginas. Debes encontrar un balance entre lo que explicas y lo que citas, sobre todo en relación con temas de teoría de números. 

El documento debe dar lugar a un quinto y último capítulo de tu TFG  llamado {\sl El algoritmo de Shor} o alguna variante que te parezca adecuada.



\begin{center}
\noindent\rule{0.95\textwidth}{1.1pt}
\end{center}

\begin{thebibliography}{1}

\bibitem{ch_nt}
F.~Chamizo.
\newblock Apuntes del curso de teoría combinatoria y analítica de números.
\newblock
  {\small\url{https://matematicas.uam.es/~fernando.chamizo/asignaturas/2223tenum/2223tenum.html}},
  2022.

\bibitem{MiTa}
S.~J. Miller and R.~Takloo-Bighash.
\newblock {\em An invitation to modern number theory}.
\newblock Princeton University Press, Princeton, NJ, 2006.
\newblock With a foreword by P. Sarnak.

\bibitem{NiCh}
M.~A. Nielsen and I.~L. Chuang.
\newblock {\em Quantum computation and quantum information}.
\newblock Cambridge University Press, Cambridge, 2000.

\bibitem{rose}
H.~E. Rose.
\newblock {\em A course in number theory}.
\newblock Oxford Science Publications. The Clarendon Press, Oxford University
  Press, New York, second edition, 1994.

\bibitem{rosen}
K.~H. Rosen.
\newblock {\em Elementary number theory and its applications}.
\newblock Addison-Wesley Publishing Company, Advanced Book Program, Reading,
  MA, third edition, 1993.

\bibitem{shor}
P.~W. Shor.
\newblock Polynomial-time algorithms for prime factorization and discrete
  logarithms on a quantum computer.
\newblock {\em SIAM J. Comput.}, 26(5):1484--1509, 1997.

\bibitem{wiki_shor}
{Wikipedia contributors}.
\newblock Shor's algorithm --- {Wikipedia}{,} the free encyclopedia.
\newblock
  {\small\url{https://en.wikipedia.org/w/index.php?title=Shor%27s_algorithm&oldid=1221004007}},
  2024.
\newblock [Online; accessed 28-April-2024].

\end{thebibliography}


%\bibliography{bibtfg23CM}
%\bibliographystyle{plain}

\end{document}

