\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{color}
\usepackage{hyperref} 

\usepackage[braket,qm]{qcircuit}


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


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	SPANISH
%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[spanish]{babel}
\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}


La primera parte de esta hoja está dedicada a un algoritmo cuántico de búsqueda. A diferencia de lo que ocurría con el algoritmo de Deutsch-Jozsa, el problema de partida es significativo desde el punto de vista práctico. Sin embargo, de nuevo depende de un oráculo, que representa la base de datos, cuya implementación no se especifica. De hecho, como veremos, equivale a la matriz $U$ del algoritmo de Deutsch-Jozsa.
Por lo que leo en 
\cite{elkaderi} y \cite{zhang}, parece que el algoritmo cuántico de búsqueda solo se ha llegado a implementar con 4 qubits, lo que corresponde a una base de datos con solo~16 ítems.

\

Suponemos una lista de datos distintos que tiene cardinal dado por una potencia de~$2$ (esto no es una restricción significativa porque siempre se podría completar con datos artificiales). Queremos encontrar un dato en la lista determinando la posición que ocupa. Considerando la función $f:\{0,1,2,\dots,2^{n}-1\}\longrightarrow \{0,1\}$ que se anula excepto en el valor que indica la posición del dato buscado (comenzando por cero), el problema consiste en determinar $f^{-1}(\{1\})$. 
En computación cuántica el \emph{algoritmo de Grover} ofrece una solución probabilista. Por razones obvias, los siguientes ejercicios los orientaré hacia una presentación de este algoritmo más cercana a temas de álgebra lineal que lo habitual en las referencias (cf. \cite[\S7]{NaOh}, \cite[\S6.1]{NiCh}, \cite[\S5]{RuXa}). 

Identificamos, como hemos hecho otras veces, $\{0,1,2,\dots,2^{n}-1\}$ con $\mathcal{B}_n$. Tenemos entonces $f:\mathcal{B}_n\longrightarrow \{0,1\}$ y sabemos que $\#f^{-1}(\{1\})=1$. Nuestro objetivo es hallar el $b_0\in \mathcal{B}_n$ que realice esta imagen inversa, es decir, que cumpla $f(b_0)=1$. Llamaremos $\ket{\phi_0}$ a $\ket{b_0}$. 

\ejer
Escribe unas líneas para tu trabajo reflejando el modelo matemático con la $f$  para el problema de búsqueda añadiendo las explicaciones que consideres necesarias si alguno de los puntos anteriores te resulta oscuro. 
\medskip

El circuito que corresponde al algoritmo de Grover es:
\[
 \begin{array}{c}
	\Qcircuit @C=1em @R=1em {
	\lstick{\ket{0}}&\gate{H}&\multigate{3}{U_0} &\multigate{3}{D}&\qw &\cdots &&\multigate{3}{U_0} &\multigate{3}{D} &\meter
	\\
	\lstick{\ket{0}}&\gate{H}&\ghost{U_0} &\ghost{D}&\qw &\cdots&&\ghost{U_0} &\ghost{D} &\meter
	\\
	\cdots&\cdots & &&&\cdots&&&&\cdots
	\inputgroupv{2}{3}{4em}{0.6em}{\ket{0}^{\otimes n}\hspace{4em}}\\
	\lstick{\ket{0}}&\gate{H}&\ghost{U_0} &\ghost{D}&\qw &\cdots&&\ghost{U_0} &\ghost{D} &\meter
	}
	\\[-0.5em]
	\hspace{2.8em}\underbrace{\hspace{14em}}_{\text{$k$ veces}}
 \end{array}
\]
La salida es $\ket{\phi_0}$ con cierta probabilidad $p$ cercana a $1$. El hecho de que sea un algoritmo probabilista no es tan importante en términos prácticos porque si hacemos funcionar el algoritmo~$m$ veces, la probabilidad de que ninguna de ellas obtengamos la solución $b_0$ es $(1-p)^m$ que decae exponencialmente.

Ya sabemos por la hoja anterior que el efecto sobre $\ket{0}^{\otimes n}$ de la columna de puertas de Hadamard es $\ket{\phi_1}=2^{-n/2}\sum_{b\in \mathcal{B}_n}\ket{b}$. Por tanto, el algoritmo de Grover consiste en medir los~$n$ qubits de 
$(DU_0)^k\ket{\phi_1}$. 
Aquí y en lo sucesivo considero $U_0$ y $D$, definidos a continuación, como operadores en vez de como matrices. 
\medskip 

Para entender las definiciones de $U_0$ y $D$ te conviene recordar unas matrices de la asignatura de Cálculo Numérico~I. Dado un vector unitario
$\vec{v}\in\R^N$ la \emph{matriz de Householder} asociada a él es 
$H_{\vec{v}}=I-2\hspace{1pt}\vec{v}\hspace{1pt}\vec{v}^{\,t}$
donde se identifica $\vec{v}$ con la matriz $N\times 1$ dada por sus coordenadas. Es una matriz ortogonal que representa una simetría. La definición se extiende al caso complejo. 

\ejer 
Dado $\vec{v}\in\C^N$ con $\|\vec{v}\|=1$, muestra que $H_{\vec{v}}=I-2\hspace{1pt}\vec{v}\hspace{1pt}\vec{v}^{\,*}$
es una matriz unitaria, donde~$*$ indica la traspuesta conjugada. Comprueba además que representa una simetría por el plano perpendicular a $\vec{v}$ en el sentido de que 
$H_{\vec{v}}\,\vec{v}=-\vec{v}$
y
$H_{\vec{v}}\,\vec{w}=\vec{w}$
si $\vec{v}\perp \vec{w}$. 
Nota que, en general, 
para $\vec{u}\in\C^N$ se cumple
$H_{\vec{v}}\,\vec{u}=\vec{u}-2\langle\vec{v},\vec{u}\rangle\vec{v}$.
\medskip

Se define $U_0$ como el operador que en la base canónica $\{\ket{b}\}_{b\in\mathcal{B}_n}$ tiene como matriz $H_{\ket{\phi_0}}$ y~$D$, llamado \emph{operador de difusión de Grover}, se define análogamente con matriz $-H_{\ket{\phi_1}}$.
En particular, $U_0\ket{\phi_0}=-\ket{\phi_0}$ y $U_0\ket{b}=\ket{b}$ para todo $b\in\mathcal{B}_n-\{b_0\}$.

La puerta cuántica asociada a $U_0$ depende de $b_0$ y por tanto de la propia $f$. Es un oráculo para consultar la base de datos sin que se especifique su implementación, al igual que la~$U$ en el algoritmo de Deutsch-Jozsa. De hecho, cambiando la función en la definición de $U$ por nuestra~$f$, es posible obtener $U_0$ a partir de $U$ gracias al circuito
\[
 \left.
 \begin{array}{c}
	\Qcircuit @C=1em @R=0.6em {
	\lstick{\ket{b}}&\qw&\multigate{1}{\ U\ }&\qw&\qw
	\\
	\lstick{\ket{1}}&\gate{H}&\ghost{\ U\ }&\gate{H}&\qw
	}
 \end{array}
 \right\}
 \big(U_0\ket{b}\big)\otimes \ket{1}
\]

\ejer {\sf [Opcional]}
Si quieres, 
puedes incluir este circuito  en tu trabajo y también explicarlo si  el espacio lo permite. 



\ejer
Obviamente $\mathfrak{B}_2=\big\{\ket{\phi_0},\ket{\phi_1}\big\}$ es base de un subespacio de dimensión 2. Extendámosla con vectores ortogonales a ellos a una base $\mathfrak{B}=\big\{\ket{\phi_0},\ket{\phi_1},\ket{\phi_2},\dots, \ket{\phi_{2^n-1}}\big\}$ de todo el espacio. Muestra que la matriz del operador $DU_0$ en $\mathfrak{B}$ es
% @{} suprime el espacio entre columnas
\[
  \left(\begin{array}{@{}c|c@{}}
    G & O_{2,\, 2^n-2} \\\hline
    O_{2^n-2,\, 2} & -I_{2^n-2,\, 2^n-2}
  \end{array}\right)
  \qquad\text{con }\quad
  G
  =
  \begin{pmatrix}
   1&2^{1-n/2} \\ -2^{1-n/2}&1-2^{2-n}
  \end{pmatrix}
\]
donde $I$ y $O$ denotan la matriz identidad y la matriz nula de las dimensiones señaladas. 
{\sf Indicación:} Lo fundamental es hallar $DU_0\ket{\phi_0}$ y $DU_0\ket{\phi_1}$. 
\medskip

Ortonormalizamos $\mathfrak{B}$
con el proceso de Gram-Schmidt a $\mathfrak{B}'=\big\{\ket{\psi_0},\dots,\ket{\psi_{2^{n}-1}}\big\}$.
Nota que por la estructura del proceso, $\mathfrak{B}_2$
y $\mathfrak{B}_2'=\big\{\ket{\psi_0},\ket{\psi_1}\big\}$ son bases del mismo subespacio. 

\ejer
Comprueba que $\ket{\psi_0}=\ket{\phi_0}$ y $\ket{\psi_1}=\big(2^{n/2}\ket{\phi_1}-\ket{\phi_0}\big)/\sqrt{2^n-1}$ y 
explica por qué la matriz de $DU_0$ en la base $\mathfrak{B}'$ es igual que la anterior salvo cambiar $G$ de la base $\mathfrak{B}_2$ a la base~$\mathfrak{B}_2'$.
Halla la matriz $G$ en la base $\mathfrak{B}_2'$ y prueba que es un giro de ángulo $\alpha=-2\arcsen\big(2^{-n/2}\big)$. 

\ejer
Deduce 
$
 (DU_0)^k\ket{\psi_0}
 =
 \cos(k\alpha)\ket{\psi_0}
 +\sen(k\alpha)\ket{\psi_1}$
y
$ (DU_0)^k\ket{\psi_1}
 =
 -\sen(k\alpha)\ket{\psi_0}
 +\cos(k\alpha)\ket{\psi_1}
$.


\ejer
Demuestra que la probabilidad $p$ de que al medir $(DU_0)^k\ket{\phi_1}$ obtengamos $\ket{\phi_0}$ viene dada por  $p=\sen^2\big((k+\frac 12)\alpha\big)$. 
{\sf Indicación:} ¿Ves claro que 
$p=|\melem{\phi_0}{(DU_0)^k}{\phi_1}|^2$ por la teoría general?
Comprueba que $\ket{\phi_1}
 =
 \cos\frac{\alpha}{2}\ket{\psi_1}
-\sen\frac{\alpha}{2}\ket{\psi_0}$
y aplica el ejercicio anterior.

\ejer
Escogiendo $k= \big\lfloor -\frac{\pi}{2\alpha}\big\rfloor$, con $\lfloor x\rfloor$ la función parte entera, obtén $p \ge 1- 2^{-n}$. 
{\sf Indicación:} 
Sea $\delta = -k-\frac{\pi}{2\alpha}$. Justifica $p=\cos^2\big((\delta-1/2)\alpha\big)\ge \cos^2(\alpha/2)$. 
\medskip 

Piensa que sin computación cuántica, hallar el $b_0$ que cumple $f(b_0)=1$ requiere examinar los valores $f(0),f(1),f(2),\dots$ hasta encontrar $f(b_0)=1$ y en media haremos $\frac 12 \cdot 2^n=2^{n-1}$ llamadas a la función (a la base de datos). Mediante el algoritmo de Grover hay $k$ llamadas al oráculo y como $k$ es comparable a $2^{n/2}$, se gana una raíz cuadrada. De nuevo el truco está en el paralelismo cuántico, la posibilidad de trabajar con la superposición de muchos estados. 




\bigskip

\


La parte final de esta hoja está dedicada a un par de aspectos que pertenecen a la teoría de la llamada \emph{información cuántica} \cite{wiki_qinformation}. 

En nuestros ordenadores estamos acostumbrados a copiar información, borrarla y enviarla a otros usuarios. En computación cuántica siempre está el problema subyacente de que al medir un qubit colapsa y no está claro que estas manipulaciones de la información en las cuales se basa en gran medida la computación clásica tengan análogos cuánticos. De hecho, hay varios resultados con nombres ilustrativos como 
\emph{no-cloning theorem}, \emph{no-deleting theorem}, \emph{\mbox{no-broadcasting} theorem} y otros (mira el segundo apartado de \cite{wiki_qinformation}), que imponen limitaciones muy severas en este sentido. Se dice que son \emph{no-go theorems}, imposibilidades teóricas. Aquí nos ocuparemos del primero de ellos y después estudiaremos un resultado positivo más complicado del que seguro que has oído hablar. 

El \emph{teorema de no clonación} (\textsl{no-cloning theorem}, en inglés) dice que no podemos introducir un estado genérico y acabar con él por duplicado. Como las puertas cuánticas tienen el mismo tamaño de entrada y de salida, en la entrada debemos completar el estado a copiar con  un ``espacio'' del mismo número de qubits (por ejemplo $\ket{0}^{\otimes n}$). 
En términos matemáticos precisos, el teorema de no-clonación afirma que fijado un estado (normalizado) $\ket{\phi_0}\in\big(\C^{2}\big)^{\otimes n}$ no existe un operador unitario $U$ tal que $U\big(\ket{\phi}\otimes \ket{\phi_0}\big)=\ket{\phi}\otimes\ket{\phi}$ se verifique para todo $\ket{\phi}\in\big(\C^{2}\big)^{\otimes n}$. 

\ejer
Demuestra el teorema de no clonación. 
{\sf Indicación:} Los operador unitarios conservan el producto escalar. Halla el producto escalar de $U\big(\ket{\phi}\otimes \ket{\phi_0}\big)$ y $U\big(\ket{\psi}\otimes \ket{\phi_0}\big)$ de dos formas distintas para $\ket{\phi}$ y $\ket{\psi}$ estados (normalizados) distintos no ortogonales.
\medskip 

La siguiente extensión es relevante porque $\ket{\phi}\otimes\ket{\phi}$ y $u\ket{\phi}\otimes\ket{\phi}$ son físicamente indistinguibles si no interactúan con otros estados: 

\ejer
Adapta la demostración para obtener que $U\big(\ket{\phi}\otimes \ket{\phi_0}\big)=u\ket{\phi}\otimes\ket{\phi}$ es también imposible con $u\in\C$ de módulo~$1$, incluso permitiendo que $u$ dependa de $\ket{\phi}$ y $\ket{\phi_0}$. 
\medskip




El fenómeno de la \emph{teleportación cuántica} (o \emph{teletransporte cuántico}, ninguno de los dos sustantivos aparece en el diccionario) es una especie de complemento o vía de escape del teorema de no clonación. Sobre todo en la literatura de divulgación se suele explicar bastante mal. No podemos duplicar estados y tampoco podemos medir estados sin alterarlos, sin que colapsen. La teleportación cuántica consiste en que, sorprendentemente, partiendo de un estado puedo destruirlo de una manera especial haciendo mediciones y con los resultados darle a una segunda persona suficientes pistas para que cree un estado como el inicial. Esas pistas se las enviaré por un canal convencional (llamando por teléfono, escribiendo una carta,\dots) y por tanto tardarán en llegar si el receptor está lejos. De todas formas, sorprende que alguien lejano sea capaz de reconstruir exactamente algo que estaba aquí y sobre lo que yo solo pude extraer información probabilista (y lo mismo le ocurrirá al destinatario). 
Es, en definitiva, una copia remota destruyendo el original. 
Ha habido bastantes experimentos, algunos con distancias gigantescas, ratificando que esto es posible. 

\ejer
Da un vistazo a \cite[\S2.6]{ch_qf} sin meterte en los detalles si te resultan farragosos. 
Simplemente es una recomendación de lectura introductoria para que entiendas mejor algunos aspectos del fenómeno. 
Dejo a tu albedrío reflejar o no en tu trabajo algo de lo que leas ahí. 

\ejer
Lee \cite[\S1.3.7]{NiCh} y escribe con tus propias palabras su contenido para tu trabajo complementándolo con las explicaciones que consideres adecuadas. 
Tiende a algo sintético. Lo más importante es reflejar en qué consiste el fenómeno lo cual, como he dicho, suele explicarse mal.
Incluye el circuito correspondiente (cópialo de la fuente de este documento):
\[
\Qcircuit @C=0.8em @R=0.6em {
\lstick{\ket{\psi}}&  \qw& \qw& \ctrl{1}& \gate{H}&\meter  & \cctrl{2}
\\
\lstick{\ket{0}}& \qw&  \targ&  \targ& \qw&\meter\cwx[1]
\\
\lstick{\ket{0}}& \gate{H}& \ctrl{-1}&\qw& \qw &\gate{X}&\gate{Z}&\rstick{\ket{\psi}}\qw
}
\]
Nota que en la figura 1.12 se definen los estados de Bell de una forma ligeramente distinta la nuestra en la hoja 2. 


\



\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.   
Te recomiendo evitar detalles de los cálculos (por ejemplo del cambio de base de $G$ o de la acción de los operadores en el último ejercicio).
Mi idea original era incluir la teleportación en la segunda hoja. No lo hice porque habría quedado muy larga y ahora la parte de información cuántica pega poco con el algoritmo de Grover. Dos opciones son que dividas el material en dos capítulos breves llamados algo así como  {\sl Información cuántica} y {\sl El algoritmo de búsqueda de Grover} o que los juntes en uno solo yuxtaponiendo ambos títulos. 



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

\begin{thebibliography}{1}

\bibitem{ch_qf}
F.~Chamizo.
\newblock Un poco de física cuántica para chicos listos de primero (del grado
  de física o matemáticas).
\newblock
  {\small\url{http://matematicas.uam.es/~fernando.chamizo/physics/files/qf.pdf}},
  2015.

\bibitem{elkaderi}
Y.~El~Kaderi, A.~Honecker, and I.~Andriyanova.
\newblock Performance of uncoded implementation of {G}rover's algorithm on
  today's quantum processors.
\newblock In {\em 2023 IEEE Information Theory Workshop (ITW)}, pages 209--214,
  2023.

\bibitem{NaOh}
M.~Nakahara and T.~Ohmi.
\newblock {\em Quantum computing}.
\newblock CRC Press, Boca Raton, FL, 2008.
\newblock From linear algebra to physical realizations.

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

\bibitem{RuXa}
J.~Ru\'{e} and S.~Xamb\'{o}.
\newblock Mathematical introduction to quantum computing.
\newblock {\em Butl. Soc. Catalana Mat.}, 28(2):183--231, 234, 2013.
\newblock {\small\url{https://web.mat.upc.edu/sebastia.xambo/QC/qc.pdf}}.

\bibitem{wiki_qinformation}
{Wikipedia contributors}.
\newblock Quantum information -- {Wikipedia}{,} the free encyclopedia.
\newblock
  \small\url{https://en.wikipedia.org/w/index.php?title=Quantum_information&oldid=1189111171},
  2023.
\newblock [Online; accessed 6-January-2024].

\bibitem{zhang}
K.~Zhang, P.~Rao, K.~Yu, H.~Lim, and V.~Korepin.
\newblock Implementation of efficient quantum search algorithms on {NISQ}
  computers.
\newblock {\em Quantum Inf. Process.}, 20(7):Paper No. 233, 27, 2021.

\end{thebibliography}


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

\end{document}

