Oracles.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Oracles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Grover's algorithm, we want to build an oracle that will flip the sign of the phase that is our answer. \n",
    "\n",
    "For example, if $\\ket{01}$ is the answer and it's in a superposition with other potential answers, we want the following result:\n",
    "\n",
    "$$\n",
    "\\ket{00} - \\ket{01} + \\ket{10} + \\ket{11}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall in learning the Deustch-Jozsa algorithm that we had an oracle we could query that had the following behavior:\n",
    "\n",
    "$$\n",
    "O \\ket{x}\\ket{y} = \\ket{x}\\ket{y \\oplus f(x)} \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We found out that if you set $\\ket{y} = \\ket{-}$ we got the following behavior:\n",
    "    \n",
    "$$\n",
    "O \\ket{x}\\ket{-} = (-1)^{f(x)} \\ket{x}\\ket{-} \n",
    "$$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Where $\\ket{-}$ remains unchanged but there is a negative phase that gets \"kicked\" to the input $\\ket{x}$ qubit whenever $f(x) = 1$, giving us the property of *phase kickback*. This is a property we need to use to make Grover's Algorithm work. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an arbitrary $f(x)$ that has the property defined before that it equals 1 if x is the solution and 0 otherwise, we can convert it (from a high level understanding) into a suitable oracle like so (taken from IBM Qiskit Textbook, section 3.8, Grover's Algorithm): \n",
    "\n",
    "![](img/classical-to-quantum.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you look closely you'll note that the circle with the plus implies some kind of control gate\n",
    "like the ones you saw before (specifically the ones that apply the X gate to a target qubit). The oracle therefore, has the behavior that if $\\ket{x}$ is the solution then we apply X onto the target qubit, otherwise nothing happens.\n",
    "\n",
    "Furthermore, if that target qubit is $\\ket{-}$ we will still experience the effects of phase kickback!\n",
    "\n",
    "You can see a more thorough (and generalized) treatment of phase kickback here: [https://qiskit.org/textbook/ch-gates/phase-kickback.html](https://qiskit.org/textbook/ch-gates/phase-kickback.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ancilla Qubits\n",
    "\n",
    "As oracles get larger in size it may be necessary to introduce *ancilla* qubits that are not meant to contribute to the answer but are used to store intermediate results (as well as ensure the reversibility and therefore, unitary nature) of the oracle.\n",
    "\n",
    "A nice example is provided by [Ryan LaRose's QuIC Seminar notes on Grover's Search Algorithm, p. 41](https://www.ryanlarose.com/uploads/1/1/5/8/115879647/grover.pdf) where we have an oracle that represents the action of performing the AND of all its inputs:\n",
    "\n",
    "![](img/oracle-with-ancilla.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With our earlier knowledge we can see that we have two CCX gates chained together such that the only time the qubit at the very bottom (the real target qubit) is affected is when all the input qubits ($\\ket{a}$, $\\ket{b}$, $\\ket{c}$) are $\\ket{1}$.\n",
    "\n",
    "There is a second qubit from the bottom that is considered an ancilla as its input is not meant to be changed and just serves as a way of storing the intermediate AND result between $\\ket{a}$ and $\\ket{b}$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The introduction of ancilla qubits does add an additional issue we have to look out for: if the ancilla is not \"reset\" to its original state of $\\ket{0}$, the next time we invoke the oracle it could apply the change to the target qubit with the wrong conditions! \n",
    "\n",
    "In the example above note that $\\ket{ab}$ is $\\ket{1}$ if $\\ket{a}$ and $\\ket{b}$ are $\\ket{1}$ as well. The NEXT time we query the oracle, that $\\ket{1}$ is STILL there so come the next time around when all the input qubits are $\\ket{1}$ and we expect the target qubit to be changed, nothing happens because the ancilla $\\ket{1}$ becomes a $\\ket{0}$, which feeds into the second CCX gate and 0 AND 1 (from $\\ket{c}$) just equals 0, so nothing happens. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need a way to systematically RESET ancilla qubits after the oracle has performed its operation on them, which leads us to the topic of **uncomputation**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Uncomputation\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that all operations on a quantum computer (with the exception of measurement) follow the property of being unitary:\n",
    "\n",
    "$$AA^{\\dagger} = A^{\\dagger}A = I$$\n",
    "\n",
    "This unitary nature gives rise to reversible computation. If I have some quantum operation A, and then I apply its adjoint (technically the hermitian adjoint is the proper terminology) right after, then I get the Identity and I've undone whatever it was that A did."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's say that $A$ constitutes a sequence of other quantum operations like $XYZ$\n",
    "\n",
    "Thus, applying A looks like $XYZ\\ket{\\psi}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's say I want to undo what I just did. Taking the adjoint has the following property:\n",
    "\n",
    "$$(XYZ)^{\\dagger} = (Z^{\\dagger}Y^{\\dagger}X^{\\dagger})$$\n",
    "\n",
    "Notice that I can distribute the application of the adjoint out to the constituent operations and furthermore, they are REVERSED in order."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus, we get that: $Z^{\\dagger}Y^{\\dagger}X^{\\dagger} XYZ \\ket{\\psi} = \\ket{\\psi}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import npquantum as npq\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1.+0.j, 0.+0.j],\n",
       "       [0.+0.j, 1.+0.j]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# lets confirm that (XYZ)^dagger really IS (Z dagger Y dagger X dagger)\n",
    "XYZ = npq.X @ npq.Y @ npq.Z\n",
    "XYZ_dagger = XYZ.conjugate().T\n",
    "\n",
    "ZYX_individual_dagger = npq.Z.conjugate().T @ npq.Y.conjugate().T @ npq.X.conjugate().T\n",
    "\n",
    "# should be TRUE\n",
    "np.array_equal(XYZ_dagger, ZYX_individual_dagger)\n",
    "\n",
    "# Now, lets confirm that Z dagger Y dagger X dagger X Y Z really gives us the identity \n",
    "ZYX_individual_dagger @ XYZ\n",
    "\n",
    "# The output should be the 2x2 identity matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Furthermore, note that some gates like the Hadamard are their OWN adjoint, so $H = H^{\\dagger}$, meaning if you apply it TWICE it will automatically undo what it did before"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The CX and CCX gates obey this behavior as well. \n",
    "\n",
    "Thus, if we want to reset the ancilla qubits in the problem mentioned before we just look at the gates leading up to the ancilla application and put them IN REVERSE ORDER."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This gives us the following oracle (also taking from [Ryan LaRose's QuIC Seminar notes on Grover's Search Algorithm, p. 43](https://www.ryanlarose.com/uploads/1/1/5/8/115879647/grover.pdf))\n",
    "\n",
    "![](img/oracle-with-uncompute.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that this oracle has an ADDITIONAL CX gate that allows us to copy the result we got last time into another a SEPARATE qubit. The reason being is that the ancilla qubit is inherently \"tied\" to the output qubit by a CCX gate and when we perform the uncomputaiton, we ONLY WANT TO UNCOMPUTE ancilla qubits. NOT OUR ANSWER. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Besides that quirk however, notice that all the gates leading up to the copying of the answer are now applied again but in reverse order, allowing us to uncompute whatever happened to the ancilla qubits and resetting them."
   ]
  }
 ],
 "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}