S4.1_Algoritmo_de_Deutsch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table width=\"100%\"><tr><td style=\"color:#bbbbbb;background-color:#ffffff;font-size:11px;font-style:italic;text-align:right;\"></td></tr></table>\n",
    "$ \\newcommand{\\bra}[1]{\\langle #1|} $\n",
    "$ \\newcommand{\\ket}[1]{|#1\\rangle} $\n",
    "$ \\newcommand{\\braket}[2]{\\langle #1|#2\\rangle} $\n",
    "$ \\newcommand{\\dot}[2]{ #1 \\cdot #2} $\n",
    "$ \\newcommand{\\biginner}[2]{\\left\\langle #1,#2\\right\\rangle} $\n",
    "$ \\newcommand{\\mymatrix}[2]{\\left( \\begin{array}{#1} #2\\end{array} \\right)} $\n",
    "$ \\newcommand{\\myvector}[1]{\\mymatrix{c}{#1}} $\n",
    "$ \\newcommand{\\myrvector}[1]{\\mymatrix{r}{#1}} $\n",
    "$ \\newcommand{\\mypar}[1]{\\left( #1 \\right)} $\n",
    "$ \\newcommand{\\mybigpar}[1]{ \\Big( #1 \\Big)} $\n",
    "$ \\newcommand{\\sqrttwo}{\\frac{1}{\\sqrt{2}}} $\n",
    "$ \\newcommand{\\dsqrttwo}{\\dfrac{1}{\\sqrt{2}}} $\n",
    "$ \\newcommand{\\onehalf}{\\frac{1}{2}} $\n",
    "$ \\newcommand{\\donehalf}{\\dfrac{1}{2}} $\n",
    "$ \\newcommand{\\hadamard}{ \\mymatrix{rr}{ \\sqrttwo & \\sqrttwo \\\\ \\sqrttwo & -\\sqrttwo }} $\n",
    "$ \\newcommand{\\vzero}{\\myvector{1\\\\0}} $\n",
    "$ \\newcommand{\\vone}{\\myvector{0\\\\1}} $\n",
    "$ \\newcommand{\\stateplus}{\\myvector{ \\sqrttwo \\\\  \\sqrttwo } } $\n",
    "$ \\newcommand{\\stateminus}{ \\myrvector{ \\sqrttwo \\\\ -\\sqrttwo } } $\n",
    "$ \\newcommand{\\myarray}[2]{ \\begin{array}{#1}#2\\end{array}} $\n",
    "$ \\newcommand{\\X}{ \\mymatrix{cc}{0 & 1 \\\\ 1 & 0}  } $\n",
    "$ \\newcommand{\\Z}{ \\mymatrix{rr}{1 & 0 \\\\ 0 & -1}  } $\n",
    "$ \\newcommand{\\Htwo}{ \\mymatrix{rrrr}{ \\frac{1}{2} & \\frac{1}{2} & \\frac{1}{2} & \\frac{1}{2} \\\\ \\frac{1}{2} & -\\frac{1}{2} & \\frac{1}{2} & -\\frac{1}{2} \\\\ \\frac{1}{2} & \\frac{1}{2} & -\\frac{1}{2} & -\\frac{1}{2} \\\\ \\frac{1}{2} & -\\frac{1}{2} & -\\frac{1}{2} & \\frac{1}{2} } } $\n",
    "$ \\newcommand{\\CNOT}{ \\mymatrix{cccc}{1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0} } $\n",
    "$ \\newcommand{\\norm}[1]{ \\left\\lVert #1 \\right\\rVert } $\n",
    "$ \\newcommand{\\pstate}[1]{ \\lceil \\mspace{-1mu} #1 \\mspace{-1.5mu} \\rfloor } $\n",
    "\n",
    "<img style=\"float: right;\" src=\"https://avatars.githubusercontent.com/u/141567859?s=200&v=4\">\n",
    "    \n",
    "<br>\n",
    "<br>\n",
    "<br>\n",
    "<font size=\"8\">QuantumQuipu/</font><br>\n",
    "<br>\n",
    "<br>\n",
    "<font size=\"15\"><b>QuantumScholars2023</b></font>\n",
    "<br>\n",
    "<br>\n",
    "<br>\n",
    "<br>\n",
    "<br>\n",
    "\n",
    "<div style=\"border-top: 20px solid #DE781F;\"></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "_uuid": "1752ce061957fd1ce93d2e4db9494b7b29da7935",
    "id": "4skdndoa-7GI"
   },
   "source": [
    "**Autor:** Gustavo Valdivia Mera\\\n",
    "**Institución:** University of Houston\\\n",
    "**Correo:** gvaldiviamera@uh.edu\n",
    "          \n",
    "Este material está sujeto a los términos y condiciones de la licencia\n",
    "[Creative Commons CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/).\\\n",
    " Se permite el uso gratuito para cualquier propósito no comercial.\n",
    "\n",
    "*Puede consultar la última versión de este notebook en nuestro [repositorio](https://github.com/QuantumQuipu/QuantumScholars2023) y los videos de clase en nuestro canal de [Youtube](https://www.youtube.com/channel/UCze8vzQLcplutz0nWDNjFCA).*    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "_uuid": "9b690f2c8129ad9445c544337375b93246c26668",
    "id": "Vm9O4SUd-7GJ"
   },
   "source": [
    "# <center> Sesión 4. Algoritmo de Deutsch\n",
    "    \n",
    "## Outline\n",
    "1. [Problema de Deutsch](#1.-Problema-de-Deutsch)\n",
    "2. [Modelo Computacional con Oráculo](#2.-Modelo-Computacional-con-Oráculo)\n",
    "3. [Algoritmo de Deutsch](#3.-Algoritmo-de-Deutsch)\n",
    "4. [Conclusión](#Conclusión)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El algoritmo de Deustch es uno de los primeros que logró evidenciar la ventaja que adquiere la computación cuántica sobre la clásica."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Problema de Deutsch\n",
    "\n",
    "Dada una función booleana \n",
    "$$f:\\{0,1\\} \\rightarrow \\{0, 1\\}$$\n",
    "donde\n",
    "\n",
    "- $f$ es balanceada si $f(0) \\neq f(1)$\n",
    "- $f$ es constante si $f(0) = f(1)$\n",
    "\n",
    "Diremos que  $f$ es un oráculo: Se puede determinar su comportamiento (si es constante o balanceada), mas no la forma explícita de la regla de correspondencia.\n",
    "\n",
    "Nuestro objetivo será determinar si $f$ es constante o balanceada."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Modelo Computacional con Oráculo\n",
    "\n",
    "\n",
    "### Solución Clásica\n",
    "\n",
    "Dada la función $f$, necesitamos evaluarla *dos veces* para determinar si $f$ es constante o balanceada usando un método computacional clásico.\n",
    "\n",
    "### Solución Cuántica\n",
    "\n",
    "Toda función lógica clásica $f$ puede ser transformada en un operador unitario equivalente $U_f$ a través de la construcción de un circuito cuántico lógico. En este contexto, presentaremos un algoritmo cuántico que determinará si $f$ es constante o balanceada al evaluar el operador $U_f$ en una única iteración."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Algoritmo de Deutsch\n",
    "\n",
    "Construimos un circuito de 2 qubits.\n",
    "\n",
    "- Establecemos el segundo qubit en el estado $\\ket{-}$ aplicando las compuertas $X$ y $H$.\n",
    "\n",
    "- Aplicamos la compuerta $H$ al primer qubit.\n",
    "\n",
    "- Aplicamos $U_f$.\n",
    "\n",
    "- Aplicamos la compuerta $H$ al primer qubit.\n",
    "\n",
    "- Medimos el primer qubit.\n",
    "\n",
    " <img src=\"imagenes/sesion4/ad_1.png\" width=\"50%\" align=\"center\">\n",
    "    </td></tr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Análisis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Operador oráculo $U_f$\n",
    "\n",
    " <img src=\"imagenes/sesion4/f_op.png\" width=\"35%\" align=\"center\">\n",
    "    </td></tr>\n",
    "\n",
    "Definimos\n",
    "$$U_f: \\ket{x}\\ket{y} \\mapsto \\ket{x}\\ket{y \\oplus f(x)}$$\n",
    "\n",
    "$$\\forall x,y\\in\\{0,1\\}$$\n",
    "\n",
    "Donde $\\oplus$ es el operador de disyunción exclusiva: XOR.\n",
    "\n",
    "Entonces, para $\\ket{x}\\ket{-}$ tenemos\n",
    "\\begin{align*}\n",
    "U_f\\ket{x}\\ket{-} &= U_f\\ket{x}\\left(\\frac{1}{\\sqrt{2}}\\ket{0}-\\frac{1}{\\sqrt{2}}\\ket{1}\\right)\\\\\n",
    "&=\\frac{1}{\\sqrt{2}}U_f\\ket{x}\\ket{0}-\\frac{1}{\\sqrt{2}}U_f\\ket{x}\\ket{1}\\\\\n",
    "&=\\frac{1}{\\sqrt{2}}\\ket{x}\\ket{0\\oplus f(x)}-\\frac{1}{\\sqrt{2}}\\ket{x}\\ket{1\\oplus f(x)}\n",
    "\\end{align*}\n",
    "Recordemos\n",
    "\n",
    "<center>\n",
    "$\\begin{array}{cc|c} \n",
    "y& f(x)& y\\oplus f(x)\\\\ \n",
    "\\hline\n",
    "0& 0 & 0 \\\\ \n",
    "0& 1 & 1 \\\\ \n",
    "1& 0 & 1 \\\\ \n",
    "1& 1 & 0 \\\\ \n",
    " \\end{array}\n",
    "$\n",
    "\n",
    "Entonces:\n",
    "\\begin{align*}\n",
    "U_f\\ket{x}\\ket{-}&=(-1)^{f(x)}\\ket{x}\\ket{-}\n",
    "\\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algoritmo\n",
    "\n",
    "Separamos nuestro circuito en diferentes instantes, de tal forma que podremos ver cómo se comporta el estado cuántico del circuito en cada paso."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " <img src=\"imagenes/sesion4/ad_2.png\" width=\"50%\" align=\"center\">\n",
    "    </td></tr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tenemos el estado inicial \n",
    "$$\\ket{\\psi_0} = \\ket{0}\\ket{0}$$\n",
    "\n",
    "Luego aplicamos la compuerta $X$ al segundo qubit\n",
    "\\begin{align}\n",
    "\\ket{\\psi_1} &= \\ket{0}X\\ket{0}\\\\\n",
    "&=\\ket{0}\\ket{1}\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aplicamos la compuerta $H$ a ambos qubits\n",
    "\n",
    "\\begin{align*}\n",
    "\\ket{\\psi_2} &= H^{\\otimes 2}\\ket{\\psi_1}\\\\\n",
    "&= H\\ket{0}H\\ket{1}\\\\\n",
    "&= \\ket{+}\\ket{-}\\\\\n",
    " &= \\left(\\frac{1}{\\sqrt{2}}\\ket{0} +\\frac{1}{\\sqrt{2}}\\ket{1} \\right) \\ket{-} \\\\\n",
    " &= \\frac{1}{\\sqrt{2}}\\ket{0}\\ket{-}  +\\frac{1}{\\sqrt{2}}\\ket{1}\\ket{-}  \\\\ \n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A continuación, aplicamos $U_f$\n",
    "\\begin{align*}\n",
    "\\ket{\\psi_3}&=U_f\\ket{\\psi_2}\\\\\n",
    "\\ket{\\psi_3} &= U_f\\left(\\frac{1}{\\sqrt{2}}\\ket{0}\\ket{-}+\\frac{1}{\\sqrt{2}}\\ket{1}\\ket{-}\\right) \\\\\n",
    "&= \\frac{1}{\\sqrt{2}}U_f\\ket{0}\\ket{-}+\\frac{1}{\\sqrt{2}}U_f\\ket{1}\\ket{-}\\\\\n",
    "&= \\left(\\frac{1}{\\sqrt{2}}(-1)^{f(0)}\\ket{0}+\\frac{1}{\\sqrt{2}}(-1)^{f(1)}\\ket{1}\\right)\\ket{-}\\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Enfoquémonos en el primer qubit\n",
    "$$\n",
    "\\ket{\\psi_{3,0}}=\\frac{1}{\\sqrt{2}}(-1)^{f(0)}\\ket{0}+\\frac{1}{\\sqrt{2}}(-1)^{f(1)}\\ket{1}\n",
    "$$\n",
    "\n",
    "Aplicamos la compuerta $H$ al primer qubit\n",
    "\\begin{align}\n",
    "\\ket{\\psi_{4,0}}&=H\\left(\\frac{1}{\\sqrt{2}}(-1)^{f(0)}\\ket{0}+\\frac{1}{\\sqrt{2}}(-1)^{f(1)}\\ket{1}\\right)\\\\\n",
    "&=\\frac{1}{\\sqrt{2}}(-1)^{f(0)}H\\ket{0}+\\frac{1}{\\sqrt{2}}(-1)^{f(1)}H\\ket{1}\\\\\n",
    "&=\\frac{1}{2}\\left((-1)^{f(0)} + (-1)^{f(1)}\\right)\\ket{0}+\\frac{1}{2}\\left((-1)^{f(0)}-(-1)^{f(1)}\\right)\\ket{1}\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Analicemos los valores obtenidos en la medición del primer qubit:\n",
    "\n",
    "#### 1. $f$ es constante:\n",
    "\n",
    "Tenemos \n",
    "$$\n",
    "f(0) = f(1) = c\n",
    "$$\n",
    "\n",
    "Entonces\n",
    "\\begin{align}\n",
    "\\ket{\\psi_{4,0}}&=\\frac{1}{2}\\left((-1)^{f(0)} + (-1)^{f(1)}\\right)\\ket{0}+\\frac{1}{2}\\left((-1)^{f(0)}-(-1)^{f(1)}\\right)\\ket{1}\\\\\n",
    "&=\\frac{1}{2}\\left((-1)^{c} + (-1)^{c}\\right)\\ket{0}+\\frac{1}{2}\\left((-1)^{c}-(-1)^{c}\\right)\\ket{1}\\\\\n",
    "&=(-1)^{c}\\ket{0}\\\\\n",
    "&=\\pm\\ket{0}\n",
    "\\end{align}\n",
    "\n",
    "Por lo tanto, al realizar la medicón del primer qubit este se encontrará en el estado $\\ket{0}$ con una probabilidad de 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  2. $f$ es balanceada:\n",
    "\n",
    "Tenemos \n",
    "$$\n",
    "f(0) + f(1) = 1\n",
    "$$\n",
    "\n",
    "Entonces\n",
    "\\begin{align}\n",
    "\\ket{\\psi_{4,0}}&=\\frac{1}{2}\\left((-1)^{f(0)} + (-1)^{f(1)}\\right)\\ket{0}+\\frac{1}{2}\\left((-1)^{f(0)}-(-1)^{f(1)}\\right)\\ket{1}\\\\\n",
    "&=\\frac{1}{2}\\left((-1)^{f(0)} + (-1)^{1-f(0)}\\right)\\ket{0}+\\frac{1}{2}\\left((-1)^{f(0)}-(-1)^{1-f(0)}\\right)\\ket{1}\\\\\n",
    "&=(-1)^{f(0)}\\ket{1}\\\\\n",
    "&=\\pm\\ket{1}\n",
    "\\end{align}\n",
    "\n",
    "Por lo tanto, al realizar la medicón del primer qubit este se encontrará en el estado $\\ket{1}$ con una probabilidad de 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusión\n",
    "\n",
    "El algoritmo de Deutsch determina con un 100% de certeza si $f$ es constante o balanceada haciendo una sola consulta en lugar de dos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "6ucKfX5Q-7Ga"
   },
   "source": [
    "---\n",
    "\n",
    "## 5. Recursos útiles\n",
    "\n",
    "[1] David Deutsch and Richard Jozsa (1992). \"Rapid solutions of problems by quantum computation\".\\\n",
    "Proceedings of the Royal Society of London A. 439: 553–558. [doi:10.1098/rspa.1992.0167](https://royalsocietypublishing.org/doi/10.1098/rspa.1992.0167).\n",
    "\n",
    "[2] [Qiksit: Deutsch-Jozsa Algorithm](https://learn.qiskit.org/course/ch-algorithms/deutsch-jozsa-algorithm)\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Donaciones\n",
    "<br>\n",
    "Puedes donar una vez en el siguiente enlace (Ko-Fi)\n",
    "\n",
    "<a href=\"https://ko-fi.com/rcrdphysics\">\n",
    "<img src=\"https://habrastorage.org/webt/8r/ml/xf/8rmlxfpdzukegpxa62cxlfvgkqe.png\" width=20% />\n",
    "\n",
    "</center>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}