theory.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "59358cde-e49a-4f3d-b073-09f4cf98ddb0",
   "metadata": {},
   "source": [
    "# Deutsch's Algorithm Theory\n",
    "\n",
    "https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html\n",
    "\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0adb3cb-b219-4c46-974a-afbf13803d08",
   "metadata": {},
   "source": [
    "### Qubits\n",
    "\n",
    "<br>\n",
    "\n",
    "$|0 \\rangle = \\begin{bmatrix} 1 \\\\ 0 \\end{bmatrix}$\n",
    "\n",
    "$|1 \\rangle = \\begin{bmatrix} 0 \\\\ 1 \\end{bmatrix}$\n",
    "\n",
    "$|\\psi \\rangle = \\begin{bmatrix} \\alpha \\\\ \\beta \\end{bmatrix} =  \\alpha |0 \\rangle + \\beta |1 \\rangle $\n",
    "\n",
    "$\\alpha = a + bi \\qquad \\beta = c + di \\qquad a,b,c,d \\in \\mathbb{R}$\n",
    "\n",
    "$ \\alpha^2 + \\beta^2 = 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb982b12-316a-4a87-a205-a1d6cd732724",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "### Gates\n",
    "\n",
    "<br>\n",
    "\n",
    "$ H = \\begin{bmatrix} \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}} \\end{bmatrix} = \\frac{1}{\\sqrt{2}} \\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix} $\n",
    "\n",
    "$ H | 0 \\rangle = \\frac{1}{\\sqrt{2}} \\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix} \\begin{bmatrix} 1 \\\\ 0 \\end{bmatrix} = \\frac{1}{\\sqrt{2}} \\begin{bmatrix} 1 \\\\ 1 \\end{bmatrix} = \\begin{bmatrix} \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} \\end{bmatrix} = |+\\rangle$ \n",
    "\n",
    "$ H | 1 \\rangle = \\frac{1}{\\sqrt{2}} \\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix} \\begin{bmatrix} 0 \\\\ 1 \\end{bmatrix} = \\frac{1}{\\sqrt{2}} \\begin{bmatrix} 1 \\\\ -1 \\end{bmatrix} = \\begin{bmatrix} \\frac{1}{\\sqrt{2}} \\\\ -\\frac{1}{\\sqrt{2}} \\end{bmatrix}  = |-\\rangle$\n",
    "\n",
    "$H^* = H^{-1}$\n",
    "\n",
    "$(a+bi)^* = a - bi$\n",
    "\n",
    "$ I = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} $"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3747d13f-892c-40b5-afc8-1ee34f7b5faf",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "### Measurement\n",
    "\n",
    "<br>\n",
    "\n",
    "$ |\\psi\\rangle = \\begin{bmatrix} \\alpha \\\\ \\beta \\end{bmatrix} \\Leftrightarrow \\langle \\psi | = \\begin{bmatrix} \\alpha^* & \\beta^* \\end{bmatrix} $\n",
    "\n",
    "##### Probability of measuring $|0\\rangle$ when in $|+\\rangle$:\n",
    "\n",
    "$|\\langle 0 | + \\rangle |^2 = |\\langle 0 || + \\rangle |^2 = | \\begin{bmatrix} 1 & 0 \\end{bmatrix} \\begin{bmatrix} \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} \\end{bmatrix} |^2 = |(1)(\\frac{1}{\\sqrt{2}}) + (0)(\\frac{1}{\\sqrt{2}})|^2 = (\\frac{1}{\\sqrt{2}})^2 = \\frac{1}{2}$\n",
    "\n",
    "$|a+bi| = \\sqrt{(a+bi)(a-bi)} = \\sqrt{a^2 + b^2}$\n",
    "\n",
    "##### Probability of measuring $|1\\rangle$ when in $|-\\rangle$:\n",
    "\n",
    "$|\\langle 1 | - \\rangle |^2 = |\\langle 1 || - \\rangle |^2 = | \\begin{bmatrix} 0 & 1 \\end{bmatrix} \\begin{bmatrix} \\frac{1}{\\sqrt{2}} \\\\ -\\frac{1}{\\sqrt{2}} \\end{bmatrix} |^2 = |(0)(\\frac{1}{\\sqrt{2}}) + (1)(-\\frac{1}{\\sqrt{2}})|^2 = (-\\frac{1}{\\sqrt{2}})^2 = \\frac{1}{2}$\n",
    "\n",
    "\n",
    "##### Probability of measuring $|1\\rangle$ when in $|0\\rangle$:\n",
    "\n",
    "$|\\langle 1 | 0 \\rangle |^2 = = | \\begin{bmatrix} 0 & 1 \\end{bmatrix} \\begin{bmatrix} 1 \\\\ 0 \\end{bmatrix} |^2 = |(0)(1) + (1)(0)|^2 = 0$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94befa17-c8c3-4db1-b9f9-bff6d7034ce6",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "### Multiple qubits\n",
    "\n",
    "<br>\n",
    "\n",
    "First qubit: $|0\\rangle = \\begin{bmatrix} 1 \\\\ 0 \\end{bmatrix}$\n",
    "\n",
    "Second qubit: $|1\\rangle = \\begin{bmatrix} 0 \\\\ 1 \\end{bmatrix}$\n",
    "\n",
    "Together: $|01\\rangle = |0\\rangle \\bigotimes |1\\rangle = \\begin{bmatrix} 1 \\begin{bmatrix} 0 \\\\ 1 \\end{bmatrix} \\\\ 0 \\begin{bmatrix} 0 \\\\ 1 \\end{bmatrix} \\end{bmatrix} = \\begin{bmatrix} (1)(0) \\\\ (1)(1) \\\\ (0)(1) \\\\ (0)(0) \\end{bmatrix} = \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix}$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bcaa61b-f1a0-4521-8d7f-720bcef88173",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "### $CNOT$ gate\n",
    "\n",
    "<br>\n",
    "\n",
    "$CNOT = \\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix} $\n",
    "\n",
    "$CNOT \\times |01\\rangle = \\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix} \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} = \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} = |01\\rangle$\n",
    "\n",
    "$CNOT \\times |10\\rangle = \\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix} \\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} = \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix} = |11\\rangle$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2feabcb1-975a-4742-834c-5d8b361e8537",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "## $H$ followed by $CNOT$\n",
    "\n",
    "<br>\n",
    "\n",
    "$H \\bigotimes H = \\begin{bmatrix} \\frac{1}{\\sqrt{2}} \\begin{bmatrix} \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}} \\end{bmatrix} &\\frac{1}{\\sqrt{2}} \\begin{bmatrix} \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}} \\end{bmatrix} \\\\ \\frac{1}{\\sqrt{2}} \\begin{bmatrix} \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}} \\end{bmatrix} & -\\frac{1}{\\sqrt{2}} \\begin{bmatrix} \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\ \\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}} \\end{bmatrix} \\end{bmatrix} = \\begin{bmatrix} (\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & (\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & (\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & (\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} \\\\ (\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & -(\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & (\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & -(\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} \\\\ (\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & (\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & -(\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & -(\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} \\\\ (\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & -(\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & -(\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} & (\\frac{1}{\\sqrt{2}})\\frac{1}{\\sqrt{2}} \\end{bmatrix} = \\frac{1}{2} \\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & -1 & 1 & -1 \\\\ 1 & 1 & -1 & -1 \\\\ 1 & -1 & -1 & 1 \\end{bmatrix}$\n",
    "\n",
    "$CNOT \\times (H \\bigotimes H) \\times |01\\rangle = \\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix} \\frac{1}{2} \\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & -1 & 1 & -1 \\\\ 1 & 1 & -1 & -1 \\\\ 1 & -1 & -1 & 1 \\end{bmatrix} \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} = \\begin{bmatrix} \\frac{1}{2} \\\\ -\\frac{1}{2} \\\\ -\\frac{1}{2} \\\\ \\frac{1}{2} \\end{bmatrix} $\n",
    "\n",
    "$CNOT \\times (H \\bigotimes H) \\times |10\\rangle = \\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix} \\frac{1}{2} \\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & -1 & 1 & -1 \\\\ 1 & 1 & -1 & -1 \\\\ 1 & -1 & -1 & 1 \\end{bmatrix} \\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} = \\begin{bmatrix} \\frac{1}{2} \\\\ \\frac{1}{2} \\\\ -\\frac{1}{2} \\\\ -\\frac{1}{2} \\end{bmatrix} $\n",
    "\n",
    "$ (\\frac{1}{2})^2 + (\\frac{1}{2})^2 + (-\\frac{1}{2})^2 + (-\\frac{1}{2})^2 = \\frac{1}{4} + \\frac{1}{4} + \\frac{1}{4} + \\frac{1}{4} = 1 $"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bffdefe-d1f9-4fe8-8ab8-b96f73736aca",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "## Function Oracles\n",
    "\n",
    "<br>\n",
    "\n",
    "$|01\\rangle = \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} \\begin{matrix} |00\\rangle \\\\ |01\\rangle \\\\ |10\\rangle \\\\ |11\\rangle \\end{matrix} $\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9057133c-8455-43a8-b29b-1d20b5875303",
   "metadata": {},
   "source": [
    "##### Balanced: $f(0) = 0$ and $f(1) = 1$\n",
    "\n",
    "$ |x,y\\rangle \\rightarrow |x, y \\oplus f(x) \\rangle $\n",
    "\n",
    "$ \\begin{matrix} |00\\rangle \\\\ |01\\rangle \\\\ |10\\rangle \\\\ |11\\rangle \\end{matrix} \\rightarrow \\begin{matrix} |00\\rangle \\\\ |01\\rangle \\\\ |11\\rangle \\\\ |10\\rangle \\end{matrix}$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f46d1b0-7a29-4c30-8d9e-0a1336e8b1de",
   "metadata": {},
   "source": [
    "##### Constant: $f(0) = 1$ and $f(1) = 1$\n",
    "\n",
    "$|01\\rangle = \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} \\begin{matrix} |00\\rangle \\\\ |01\\rangle \\\\ |10\\rangle \\\\ |11\\rangle \\end{matrix} $\n",
    "\n",
    "$ |x,y\\rangle \\rightarrow |x, y \\oplus f(x) \\rangle $\n",
    "\n",
    "$ \\begin{matrix} |00\\rangle \\\\ |01\\rangle \\\\ |10\\rangle \\\\ |11\\rangle \\end{matrix} \\rightarrow \\begin{matrix} |01\\rangle \\\\ |00\\rangle \\\\ |11\\rangle \\\\ |10\\rangle \\end{matrix}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2c079a6-12d7-4268-83f9-1970a4161f83",
   "metadata": {},
   "source": [
    "***\n",
    "## End"
   ]
  }
 ],
 "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.8.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}