tutorials/ExploringDeutschJozsaAlgorithm/DeutschJozsaAlgorithmTutorial_P2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Deutsch–Jozsa Algorithm Tutorial (Part II)\n",
    "\n",
    "The **Deutsch–Jozsa algorithm** is one of the most famous algorithms in quantum computing. The problem it solves has little practical value, but the algorithm itself is one of the earliest examples of a quantum algorithm that is exponentially faster than any possible deterministic algorithm for the same problem. It is also relatively simple to explain and illustrates several very important concepts (such as quantum oracles). As such, Deutsch–Jozsa algorithm is part of almost every introductory course on quantum computing.\n",
    "\n",
    "This tutorial consists of several notebooks:\n",
    "1. [Part I](./DeutschJozsaAlgorithmTutorial_P1.ipynb) covers the problem statement and the classical algorithm for solving it.\n",
    "2. Part II introduces single-qubit quantum oracles and the Deutsch algorithm for solving the problem for one-bit input functions.\n",
    "3. [Part III](./DeutschJozsaAlgorithmTutorial_P3.ipynb) introduces multi-qubit quantum oracles and the Deutsch-Jozsa algorithm for solving the general case of the problem.\n",
    "4. [Part IV](./AQ/DeutschJozsaAlgorithmTutorial_P4.ipynb) shows how to run the algorithms in the cloud using Azure Quantum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part II. Single-qubit quantum oracles and Deutsch algorithm\n",
    "\n",
    "## Single-qubit oracles: the definition\n",
    "A quantum oracle is a \"black box\" operation which is used as input to another algorithm. This operation is implemented in a way which allows to perform calculations not only on individual inputs, but also on superpositions of inputs. \n",
    "\n",
    "> This is *not* the same as being able to evaluate the function on all inputs at once, since you will not be able to extract the evaluation results!\n",
    "\n",
    "Oracles are often defined using a classical function.\n",
    "Single-qubit oracles implement single-bit classical functions of the form $f : \\{0, 1\\} \\to \\{0, 1\\}$.\n",
    "\n",
    "The oracle has to act on quantum states instead of classical values. \n",
    "To enable this, integer input $x$ is represented as a qubit state $|x\\rangle$.\n",
    "\n",
    "The type of oracles used in this tutorial are called *phase oracles*. A phase oracle $U_f$ encodes the value of the classical function $f$ it implements in the phase of the qubit state as follows:\n",
    "\n",
    "$$U_f |x \\rangle = (-1)^{f(x)} |x \\rangle$$\n",
    "\n",
    "In our case $f$ can return only two values, 0 or 1, which result in no phase change or adding a relative phase $-1$, respectively.\n",
    "\n",
    "The effect of such an oracle on any single basis state is not particularly interesting: it just adds a global phase which is not something you can observe. However, if you apply this oracle to a *superposition* of basis states, its effect becomes noticeable. \n",
    "Remember that quantum operations are linear: if you define the effect of an operation on the basis states, you'll be able to deduce its effect on superposition states (which are just linear combinations of the basis states) using its linearity. \n",
    "\n",
    "## Implementing single-bit oracles in Q&#x23;\n",
    "\n",
    "There are only 4 single-bit functions, so we can see how to implement them all as Q# oracles.\n",
    "\n",
    "> **Note:**\n",
    "All code snippets before Exercise 3 are just examples. They don't need to be modified and are not covered by tests."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### $f(x) \\equiv 0$\n",
    "\n",
    "This is the easiest function to implement: if $f(x) \\equiv 0$, $U_f |x\\rangle \\equiv (-1)^0 |x\\rangle = |x\\rangle$. \n",
    "This means that $U_f$ is an identity - a transformation which does absolutely nothing! \n",
    "This is very easy to express in Q#:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation PhaseOracle_Zero (x : Qubit) : Unit {\n",
    "    // Do nothing...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### $f(x) \\equiv 1$\n",
    "\n",
    "The second constant function is slightly trickier: if $f(x) \\equiv 1$, $U_f |x\\rangle \\equiv (-1)^1 |x\\rangle = - |x\\rangle$. \n",
    "Now $U_f$ is a negative identity, i.e., a transformation which applies a global phase of $-1$ to the state. \n",
    "A lot of algorithms just ignore the global phase accumulated in them, since it is not observable. \n",
    "However, if we want to be really meticulous, we can use Q# library operation [Microsoft.Quantum.Intrinsic.R](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.r) which performs a given rotation around the given axis. \n",
    "When called with `PauliI` axis, this operation applies a global phase; since it doesn't take the input into account, it can be applied to any qubit, for example, the first qubit of the input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "// Open namespace where the library function PI() is defined\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation PhaseOracle_One (x : Qubit) : Unit {\n",
    "    // Apply a global phase of -1\n",
    "    R(PauliI, 2.0 * PI(), x);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### $f(x) = x$\n",
    "\n",
    "$$U_f |x\\rangle = (-1)^{f(x)} |x\\rangle = (-1)^{x} |x\\rangle$$\n",
    "\n",
    "This means that we need to do nothing if the qubit is in the $|0\\rangle$ state, and apply a phase of $-1$ if it is in the $|1\\rangle$ state. This is exactly the effect of the [Z gate](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.z); as a reminder, \n",
    "\n",
    "$$Z = \\begin{bmatrix} 1 & 0 \\\\ 0 & -1\\end{bmatrix}: Z |0\\rangle = |0\\rangle, Z |1\\rangle = -|1\\rangle$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "operation PhaseOracle_X (x : Qubit) : Unit {\n",
    "    Z(x);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:blue\">Exercise 3</span>: Implement a quantum oracle for $f(x) = 1 - x$ in Q&#x23;\n",
    "\n",
    "You're ready to try and write some actual quantum code! Implement a quantum oracle that implements the last single-bit function, $f(x) = 1 - x$.\n",
    "\n",
    "**Input:** A qubit $x$.\n",
    "\n",
    "**Goal:** Apply a transformation $U_f$ to the qubit, defined as $U_f |x\\rangle = (-1)^{1-x} |x\\rangle$.\n",
    "\n",
    "<br/>\n",
    "\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click Here</b></summary>\n",
    "We can represent the effect of the oracle as\n",
    "\n",
    "$$U_f |x\\rangle = (-1)^{1-x} |x\\rangle = (-1) \\cdot (-1)^x |x\\rangle$$\n",
    "\n",
    "Can you get this effect by combining some of the previous oracles implementations?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T3_PhaseOracle_OneMinusX\n",
    "\n",
    "operation PhaseOracle_OneMinusX (x : Qubit) : Unit is Adj + Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solving the problem for single-bit functions: Deutsch algorithm\n",
    "\n",
    "Now let's return to the problem of figuring out whether the given function is constant or balanced for single-bit functions.\n",
    "What can we do if we are given a quantum oracle $U_f$ implementing the function $f(x)$?\n",
    "\n",
    "There are two possible inputs to the function, $|0\\rangle$ and $|1\\rangle$. Let's see what happens if we apply the oracle to their superposition:\n",
    "\n",
    "$$U_f \\left( \\frac{1}{\\sqrt2} \\big( |0\\rangle + |1\\rangle \\big) \\right) \n",
    "= \\frac{1}{\\sqrt2} \\big( U_f |0\\rangle + U_f |1\\rangle \\big) \n",
    "= \\frac{1}{\\sqrt2} \\big( (-1)^{f(0)} |0\\rangle + (-1)^{f(1)} |1\\rangle \\big)$$.\n",
    "\n",
    "* If $f(0) = f(1)$, the relative phases of the two basis states are the same, and the resulting state is $|+\\rangle = \\frac{1}{\\sqrt2} \\big( |0\\rangle + |1\\rangle \\big)$ (up to a global phase). \n",
    "* If $f(0) \\neq f(1)$, the relative phases of the two basis states differ by a factor of $-1$, and the resulting state is $|-\\rangle = \\frac{1}{\\sqrt2} \\big( |0\\rangle - |1\\rangle \\big)$ (up to a global phase). \n",
    "\n",
    "Now, the states $|+\\rangle$ and $|-\\rangle$ can be distinguished using measurement: if you apply the H gate to each of them, you'll get $H|+\\rangle = |0\\rangle$ if $f(0) = f(1)$, or $H|-\\rangle = |1\\rangle$ if $f(0) \\neq f(1)$. This means that one oracle call does not let you calculate both $f(0)$ and $f(1)$, but it allows you to figure out whether $f(0) = f(1)$!\n",
    "\n",
    "This is a special case of the Deutsch–Jozsa algorithm, called the Deutsch algorithm. \n",
    "The algorithm is very straightforward:\n",
    "\n",
    "1. Start with a qubit in the $|0\\rangle$ state.\n",
    "2. Apply the H gate to the qubit.\n",
    "3. Apply the oracle.\n",
    "4. Apply the H gate to the qubit again.\n",
    "5. Measure the qubit: if it is in the $|0\\rangle$ state, the function is constant, otherwise it is balanced.\n",
    "\n",
    "Note that this algorithm requires only <span style=\"color:green\">$1$</span> oracle call, and always produces the correct result."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can follow the steps of the algorithm for the constant and the balanced scenarios using a neat visualization. Since Deutsch algorithm deals only with states with real amplitudes, we can map all states on the unit circle, and follow the state evolution through the steps.\n",
    "\n",
    "1-2. Start with a qubit in the $|0\\rangle$ state and apply the H gate to the qubit.\n",
    "   <img width=60% src=\"./img/2-plus-state.png\"/>\n",
    "\n",
    "3. Apply the oracle.  \n",
    "   Here, the difference between the two scenarios becomes noticeable. In the constant scenario, $|0\\rangle$ and $|1\\rangle$ states get the same phase (either 1 or -1), so the state remains the same or acquires a global phase of -1, which is physically the same state. In the variable scenario, zero and one states get different phases, so the state changes!\n",
    "   <img width=60% src=\"./img/3-apply-oracle.png\"/>\n",
    "\n",
    "4. Apply the H gate to the qubit again.\n",
    "   Now, we get the $|0\\rangle$ state for both constant scenarios and the $|1\\rangle$ state for both variable scenarios!\n",
    "   <img width=60% src=\"./img/4-apply-hadamard.png\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:blue\">Exercise 4</span>: Implement the Deutsch algorithm!\n",
    "\n",
    "**Input:** The \"black box\" oracle the implements $f(x)$.  \n",
    "\n",
    "**Goal:** Return `true` if the function is constant ($f(0) = f(1)$), or `false` if it is balanced ($f(0) \\neq f(1)$).\n",
    "You can use only one oracle call!\n",
    "\n",
    "> Useful documentation: [Q# conditional expressions](https://docs.microsoft.com/azure/quantum/user-guide/language/expressions/conditionalexpressions)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T4_DeutschAlgorithm\n",
    "\n",
    "operation DeutschAlgorithm (oracle : (Qubit => Unit)) : Bool {\n",
    "    // Allocate a qubit for the input x.\n",
    "    use x = Qubit();\n",
    "    // Newly allocated qubits start in the |0⟩ state.\n",
    "\n",
    "    // The first step is to prepare the qubit in the required state before calling the oracle.\n",
    "    // A qubit can be transformed from the |0⟩ state to the |+⟩ state by applying a Hadamard gate H.\n",
    "    // ...\n",
    "\n",
    "    // Apply the oracle to the input qubit.\n",
    "    // The syntax is the same as for applying any function or operation.\n",
    "    // ...\n",
    "\n",
    "    // Apply a Hadamard gate to the qubit again.\n",
    "    // ...\n",
    "\n",
    "    // Measure the qubit in the computational basis using the M operation,\n",
    "    // and return the result using a conditional expression: cond ? ifTrue | ifFalse.\n",
    "    return ...;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Running the algorithm\n",
    "\n",
    "You have implemented the quantum version of the Deutsch algorithm - congratulations! The last step is to combine everything you've seen so far - run your code to check whether the oracles you've seen earlier in this tutorial implement constant or balanced functions.\n",
    "\n",
    "> This is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the `Run_DeutschAlgorithm` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_DeutschAlgorithm`).\n",
    "\n",
    "> Note that this task relies on your implementations of the previous tasks. If you are getting the \"No variable with that name exists.\" error, you might have to execute previous code cells before retrying this task. Don't forget to execute Q# code cells that define oracles in part II!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation RunDeutschAlgorithm () : String {\n",
    "    // You can use Fact function to check that the return value \n",
    "    // of DeutschAlgorithm operation matches the expected value.\n",
    "    // Uncomment the next line to run it.\n",
    "    \n",
    "    // Fact(DeutschAlgorithm(PhaseOracle_Zero) == true, \"f(x) = 0 not identified as constant\");\n",
    "    \n",
    "    // Run the algorithm for the rest of the oracles\n",
    "    // ...\n",
    "    \n",
    "    \n",
    "    // If all tests pass, report success!\n",
    "    return \"Success!\";\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate RunDeutschAlgorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Continue to [part III](./DeutschJozsaAlgorithmTutorial_P3.ipynb) to learn about multi-qubit quantum oracles and Deutsch-Jozsa algorithm for solving the general case of the problem."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}