2-Quantum_Algorithms/1-Quantum_Oracles.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Phase 2 Quantum Algorithms\n",
    "\n",
    "## Pavan Kumar, Kitty Yeung\n",
    "\n",
    "In phase 1, we learned about the components of quantum computing – qubits, gates and\n",
    "measurements, which can be put together to form algorithms. An algorithm takes in information from\n",
    "qubit inputs, conducts a manipulation on the qubits, and then outputs desired results. We will be learning\n",
    "about a few algorithms that were developed as foundations to quantum computing logics in a historical\n",
    "order: Deutsch's algorithm, Deutsch-Jozsa algorithm, Grover's algorithm, Simon's algorithm and Shor's\n",
    "algorithm. These algorithms solve certain problems more efficiently than classical algorithms. (There are\n",
    "many other quantum algorithms. For the interested and curious readers, take a look at\n",
    "[http://quantumalgorithmzoo.org/](http://quantumalgorithmzoo.org/) ) Before going deeper into the algorithms, we need to start with a\n",
    "concept called \"Quantum Oracle\" which is an operation that is used as an input to another algorithm. In\n",
    "each session, we will practice our understanding with a Q# exercise.\n",
    "\n",
    "## 2.1 Quantum Oracles PHASE 2 Quantum Algorithms\n",
    "\n",
    "* [Q# exercise: Oracles](./2-Quantum_Algorithms/1-Quantum_Oracles.ipynb#qexercise)\n",
    "\n",
    "An oracle can be thought of as a black box that takes some inputs and gives some outputs. It can be\n",
    "represented using a circuit diagram below.\n",
    "\n",
    "![Figure 2.1.1](img/Figure211.png)\n",
    "\n",
    "_Figure 2.1.1 A generic oracle represented by a circuit diagram._\n",
    "\n",
    "As an example, this diagram can be an oracle that takes a three-bit integer and returns the reminder when\n",
    "it is divided by 4 with these possible outputs:\n",
    "\n",
    "<table>\n",
    "  <tr>\n",
    "    <th>x &nbsp; &nbsp; &nbsp; </th>\n",
    "    <th>y = f(x) = x % 4 &nbsp; &nbsp; </th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 0 </td>\n",
    "    <td> 0 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 1 </td>\n",
    "    <td> 1 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 2 </td>\n",
    "    <td> 2 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 3 </td>\n",
    "    <td> 3 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 4 </td>\n",
    "    <td> 0 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 5 </td>\n",
    "    <td> 1 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 6 </td>\n",
    "    <td> 2 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 7 </td>\n",
    "    <td> 3 </td>\n",
    "  </tr>\n",
    "</table>\n",
    "\n",
    "_Table 2.1.1 Input and output table for a particular oracle as an example._\n",
    "\n",
    "We could build such a circuit using classical computing gates. But there are quantum algorithms\n",
    "proven to be more efficient than classical ones. We need a quantum oracle that can do the above function\n",
    "to build quantum algorithms, with a limitation that all the quantum gates need to be unitary (session 1.2).\n",
    "\n",
    "Let's say that the initial number is encoded in a 3-qubit quantum state, x. And the function f(x)\n",
    "is implemented as a unitary quantum gate A so that\n",
    "\n",
    "y = f(x) = Ax.\n",
    "\n",
    "Since A is unitary, A$^{−1}$ exists and it should be the same as A${^\\dagger}$. This implies\n",
    "\n",
    "A${^\\dagger}$(y) = A$^{−1}$(y) = A$^{−1}$(Ax) = x.\n",
    "\n",
    "This means that given any output, applying A${^\\dagger}$ should revert to the corresponding input. However, as seen\n",
    "in Table 2.1.1, both f(3) and f(7) equal to 3. Applying a unitary gate A${^\\dagger}$ on f(3) and f(7) would not\n",
    "return distinguishable results. Our assumption that such a matrix A can exist is wrong. This is a common\n",
    "problem for designing quantum oracles. Yet, there is a work-around if we use some extra qubits.\n",
    "\n",
    "For the same function, consider the following quantum circuit:\n",
    "\n",
    "![Figure 2.1.2](img/Figure212.png)\n",
    "\n",
    "_Figure 2.1.2 Quantum Oracle._\n",
    "\n",
    "Inputs x and y can contain multiple numbers of qubits. As one can see, this circuit leaves the input x intact,\n",
    "but it does an XOR on y with f(x) (in this example y = f(x) = x % 4). Here we are assuming that x and y are\n",
    "encoded using three qubits each. The size of the input state will therefore be 64 ( $2^6$ ). The dimension of\n",
    "the unitary matrix U will be 64 x 64. Don't worry about the exact contents of U right now. We are\n",
    "assuming that such a unitary matrix exists and test if we arrive at any contradictions.\n",
    "\n",
    "Let's evaluate this circuit for x= 3 = |011⟩, with y initialized to 0 = |000⟩ and refer to Table 2.1.1 for results of f(x):\n",
    "\n",
    "U( |011⟩, |000⟩ ) = ( |011⟩, |000⟩ $\\oplus$ F( |011⟩ ) ) = ( |011⟩, |000⟩ $\\oplus$ |011⟩ ) = ( |011⟩, |011⟩ ),\n",
    "\n",
    "It has the following circuit representation:\n",
    "\n",
    "![Figure oracle 011](img/oracle011.png)\n",
    "\n",
    "Since we have initialized y to 0, the output we need will be in the bottom 3 qubits (because y $\\oplus$ f(x) = f(x), if y = 0). \n",
    "Take the outputs of the above circuit and apply the same circuit again on them:\n",
    "\n",
    "U( |011⟩, |011⟩ ) = ( |011⟩, |011⟩ $\\oplus$ f( |011⟩ ) ) = ( |011⟩, |011⟩ $\\oplus$ |011⟩ ) = ( |011⟩, |000⟩ ).\n",
    "\n",
    "It has a circuit representation:\n",
    "\n",
    "![Figure oracle 011 again](img/oracle011again.png)\n",
    "\n",
    "This demonstrates that applying the same gate U on the outputs of the first circuit recovers the original inputs.\n",
    "\n",
    "Now, let's evaluate the quantum oracle for x = 7 = |111⟩, with y initialized to 0 = |000⟩ :\n",
    "\n",
    "U( |111⟩, |000⟩ ) = ( |111⟩, |000⟩ $\\oplus$ f( |111⟩ ) ) = ( |111⟩, |000⟩ $\\oplus$ |011⟩ ) = ( |111⟩, |011⟩ ).\n",
    "\n",
    "It has the following circuit representation:\n",
    "\n",
    "![Figure oracle 111](img/oracle111.png)\n",
    "\n",
    "Take the output of the circuit and apply the same circuit again,\n",
    "\n",
    "\n",
    "U ( |111⟩, |011⟩ ) = ( |111⟩, |011⟩ $\\oplus$ f( |111⟩ ) ) = ( |111⟩, |011⟩ $\\oplus$ |011⟩ ) = ( |111⟩, |000⟩ ),\n",
    "\n",
    "with this circuit representation:\n",
    "\n",
    "![Figure oracle 111 again](img/oracle111again.png)\n",
    "\n",
    "The original inputs are again recovered. And we can distinguish input results between f(3) and f(7).\n",
    "\n",
    "\n",
    "In fact, the circuit is designed in such a way that U is not only unitary but also its own inverse.\n",
    "\n",
    "U = U$^{−1}$.\n",
    "\n",
    "Applying the circuit back to back:\n",
    "\n",
    "\n",
    "U( U( |x⟩, |y⟩ ) ) = U( ( |x⟩, |y $\\oplus$ f(x)⟩ ) )\n",
    "\n",
    "\n",
    "= ( |x⟩, | (y $\\oplus$ f(x) ) $\\oplus$ f(x) ⟩ )\n",
    "\n",
    "\n",
    "= ( |x⟩, | y $\\oplus$ ( f(x) $\\oplus$ f(x) ) ⟩\n",
    "\n",
    "\n",
    "= ( |x⟩, | y $\\oplus$ 0 ⟩ ) = ( |x⟩, |y⟩ )\n",
    "\n",
    "![Figure oracles unitary](img/oracles_unitary.png)\n",
    "\n",
    "This proof is self-consistent. We can now create quantum oracles that are implemented using unitary\n",
    "gates that are self-inverse. We will be using these quantum oracles in many algorithms like Deutsch,\n",
    "Deutsch-Jozsa, Grover's algorithms, etc.\n",
    "\n",
    "### Q# exercise: Oracles\n <a id='#qexercise'></a>",
    "\n",
    "1. Go to the Quantum Katas: https://github.com/Microsoft/QuantumKatas.\n",
    "2. In Visual Studio (Code) open folder \"DeutschJoszaAlgorithm\" and Task.qs. Or use the Jupyter\n",
    "    Notebook. Part 1 tasks focus on familiarize ourselves with oracles.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.3-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python38332bit225b1603132a4a1f9abff16033481403",
   "display_name": "Python 3.8.3 32-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}