2.DeutschJozsaAlgorithm/DeutschJozsaAlgorithmTutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Deutsch–Jozsa Algorithm Tutorial\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 will:\n",
    "* introduce you to the problem solved by the Deutsch–Jozsa algorithm and walk you through the classical solution to it,\n",
    "* give you a brief introduction to quantum oracles,\n",
    "* describe the idea behind the Deutsch–Jozsa algorithm and walk you through the math for it,\n",
    "* teach you how to implement the algorithm in the Q# programming language,\n",
    "* and finally help you to run your implementation of the algorithm on several quantum oracles to see for yourself how the algorithm works!\n",
    "\n",
    "Let's go!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To begin, first prepare this notebook for execution (if you skip the first step, you'll get \"Syntax does not match any known patterns\" error when you try to execute Q# code in the next cells; if you skip the second step, you'll get \"Invalid test name\" error):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%package Microsoft.Quantum.Katas::0.9.1908.2906"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The package versions in the output of the cell above should always match. If you are running the Notebooks locally and the versions do not match, please install the IQ# version that matches the version of the `Microsoft.Quantum.Katas` package.\n",
    "> <details>\n",
    "> <summary><u>How to install the right IQ# version</u></summary>\n",
    "> For example, if the version of `Microsoft.Quantum.Katas` package above is 0.1.2.3, the installation steps are as follows:\n",
    ">\n",
    "> 1. Stop the kernel.\n",
    "> 2. Uninstall the existing version of IQ#:\n",
    ">        dotnet tool uninstall microsoft.quantum.iqsharp -g\n",
    "> 3. Install the matching version:\n",
    ">        dotnet tool install microsoft.quantum.iqsharp -g --version 0.1.2.3\n",
    "> 4. Reinstall the kernel:\n",
    ">        dotnet iqsharp install\n",
    "> 5. Restart the Notebook.\n",
    "> </details>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%workspace reload"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part I. Problem Statement and Classical Algorithm\n",
    "\n",
    "## The problem\n",
    "\n",
    "You are given a classical function $f(x): \\{0, 1\\}^N \\to \\{0, 1\\}$. You are guaranteed that the function $f$ is\n",
    "* either *constant* (has the same value for all inputs) \n",
    "* or *balanced* (has value 0 for half of the inputs and 1 for the other half of the inputs). \n",
    "\n",
    "The task is to figure out whether the function is constant or balanced.\n",
    "\n",
    "## Examples\n",
    "\n",
    "* $f(x) \\equiv 0$ or $f(x) \\equiv 1$ are examples of constant functions (and they are actually the only constant functions in existence).\n",
    "* $f(x) = x \\text{ mod } 2$ (the least significant bit of $x$) or $f(x) = 1 \\text{ if the binary notation of }x \\text{ has odd number of 1s and 0 otherwise}$ are examples of balanced functions.  \n",
    "  Indeed, for both these functions you can check that for every possible input $x$ for which $f(x) = 0$ there exists an input $x^\\prime$ (equal to $x$ with the least significant bit flipped) such that $f(x^\\prime) = 1$, and vice versa, which means that the function is balanced.  \n",
    "  There exist more complicated examples of balanced functions, but we will not need to consider them for this tutorial.\n",
    "\n",
    "## Implementing classical functions in Q&#x23;\n",
    "\n",
    "Here is the implementation of these functions in Q#; it is pretty self-descriptory, since the functions are not only very simple but also classical."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Function 1. f(x) = 0\n",
    "function Function_Zero (x : Int) : Int {\n",
    "    return 0;\n",
    "}\n",
    "\n",
    "\n",
    "// Function 2. f(x) = 1\n",
    "function Function_One (x : Int) : Int {\n",
    "    return 1;\n",
    "}\n",
    "\n",
    "\n",
    "// Function 3. f(x) = x mod 2 (least significant bit of x)\n",
    "function Function_Xmod2 (x : Int) : Int {\n",
    "    return x % 2;\n",
    "}\n",
    "\n",
    "\n",
    "// Function 4. f(x) = 1 if the binary notation of x has odd number of 1s, and 0 otherwise\n",
    "function Function_OddNumberOfOnes (x : Int) : Int {\n",
    "    mutable nOnes = 0;\n",
    "    mutable xBits = x;\n",
    "    while (xBits > 0) {\n",
    "        if (xBits % 2 > 0) {\n",
    "            set nOnes += 1;\n",
    "        }\n",
    "        set xBits /= 2;\n",
    "    }\n",
    "    return nOnes % 2;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:blue\">Exercise 1</span>: Implement a classical function in Q&#x23;\n",
    "\n",
    "Try to implement a similar classical function in Q#!\n",
    "\n",
    "**Inputs:** \n",
    "1. An integer $x$.\n",
    "2. The number of bits in the input $N$ ($1 \\le N \\le 5$, $0 \\le x \\le 2^N-1$).\n",
    "\n",
    "**Output:** Return $f(x) = \\text{the most significant bit of }x$.\n",
    "\n",
    "> Useful documentation: [Q# Numeric Expressions](https://docs.microsoft.com/quantum/language/expressions#numeric-expressions)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata E1_ClassicalFunction_Test \n",
    "\n",
    "function Function_MostSignificantBit (x : Int, N : Int) : Int {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classical algorithm\n",
    "\n",
    "If we solve this problem classically, how many calls to the given function will we need? \n",
    "\n",
    "The first call will give us no information - regardless of whether it returns 0 or 1, the function could still be constant or balanced.\n",
    "In the best case scenario the second call will return a different value and we'll be able to conclude that the function is balanced in just <span style=\"color:red\">$2$</span> calls. \n",
    "However, if we get the same value for the first two calls, we'll have to keep querying the function until either we get a different value or until we do <span style=\"color:red\">$2^{N-1}+1$</span> queries that will return the same value - in this case we'll know for certain that the function will be constant.\n",
    "\n",
    "## <span style=\"color:blue\">Exercise 2</span>: Implement the classical algorithm!\n",
    "\n",
    "Q# is a domain-specific language, so it is not designed to handle arbitrary classical computations. However, this classical algorithm is so simple that you can easily implement it in Q#. Try it!\n",
    "\n",
    "**Inputs:** \n",
    "1. The number of bits in the input $N$ ($1 \\le N \\le 5$).\n",
    "2. The \"black box\" function that evaluates $f(x)$ on any given input $x \\in [0, 2^N-1]$.  \n",
    "  You are guaranteed that the function implemented by the black box is either constant or balanced.\n",
    "\n",
    "**Goal:** Return `true` if the function is constant, or `false` if it is balanced.\n",
    "\n",
    "> Useful documentation: [Q# statements](https://docs.microsoft.com/quantum/language/statements)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata E2_ClassicalAlgorithm_Test \n",
    "\n",
    "operation IsFunctionConstant_Classical (N : Int, f : (Int -> Int)) : Bool {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part II. Quantum Oracles\n",
    "\n",
    "## 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, in the case of Deutsch-Jozsa algorithm the function $f : \\{0, 1\\}^N \\to \\{0, 1\\}$ takes an $N$-bit binary input and produces an 1-bit binary output.\n",
    "\n",
    "The oracle has to act on quantum states instead of classical values. \n",
    "To enable this, integer input $x$ is represented in binary $x = (x_{0}, x_{1}, \\dots, x_{N-1})$, \n",
    "and encoded into an $N$-qubit register: $|\\vec{x} \\rangle = |x_{0} \\rangle \\otimes |x_{1} \\rangle \\otimes \\cdots \\otimes |x_{N-1} \\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 |\\vec{x} \\rangle = (-1)^{f(x)} |\\vec{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 $-1$ phase, 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",
    "> ## Example: Deutsch algorithm\n",
    ">\n",
    "> Consider, for example, the case of $N = 1$: there are two possible inputs to the function, $|0\\rangle$ and $|1\\rangle$, and we can 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 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 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",
    "> * 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",
    "\n",
    "## Implementing oracles in Q&#x23;\n",
    "\n",
    "Now that we've discussed the mathematical definition of the oracles, let's take a look at how to implement oracles for some classical functions in Q#. We'll consider the same 4 functions we used as an example in the first section."
   ]
  },
  {
   "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[0]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### $f(x) = x \\text{ mod } 2$\n",
    "\n",
    "In this oracle we will finally need to use the input! The binary representation of $x$ is $x = (x_{0}, x_{1}, \\dots, x_{N-1})$, with the least significant bit encoded in the last bit (stored in the last qubit of the input array): $f(x) = x_{N-1}$. Let's use this in the oracle effect expression:\n",
    "\n",
    "$$U_f |x\\rangle = (-1)^{f(x)} |x\\rangle = (-1)^{x_{N-1}} |x\\rangle = |x_{0} \\rangle \\otimes \\cdots \\otimes |x_{N-2} \\rangle \\otimes (-1)^{x_{N-1}} |x_{N-1}\\rangle$$\n",
    "\n",
    "This means that we only need to use the last qubit in the implementation: do nothing if it is $|0\\rangle$ and apply a phase of $-1$ if it is $|1\\rangle$. 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$$\n",
    "\n",
    "Finally, the expression for the oracle is:\n",
    "\n",
    "$$U_f = \\mathbb{1} \\otimes \\cdots \\otimes \\mathbb{1} \\otimes Z$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "operation PhaseOracle_Xmod2 (x : Qubit[]) : Unit {\n",
    "    // Length(x) gives you the length of the array.\n",
    "    // Array elements are indexed 0 through Length(x)-1, inclusive.\n",
    "    Z(x[Length(x) - 1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### $f(x) = 1 \\text{ if x has odd number of 1s, and 0 otherwise }$\n",
    "\n",
    "In this oracle the answer depends on all bits of the input. We can write $f(x)$ as follows:\n",
    "\n",
    "$$f(x) = \\bigoplus_{k=0}^{N-1} x_k$$ \n",
    "\n",
    "$$U_f |x\\rangle = (-1)^{f(x)} |x\\rangle = \\bigotimes_{k=0}^{N-1} (-1)^{x_k} |x_{k}\\rangle$$\n",
    "\n",
    "As we've seen in the previous oracle, this can be achieved by applying a Z gate to each qubit; you can use library function [ApplyToEach](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.applytoeach) to apply a gate to each qubit of the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "operation PhaseOracle_OddNumberOfOnes (x : Qubit[]) : Unit {\n",
    "    ApplyToEach(Z, x);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:blue\">Exercise 3</span>: Implement a quantum oracle in Q&#x23;\n",
    "\n",
    "You're ready to try and write some actual quantum code! Implement a quantum oracle that corresponds to the classical function from exercise 1.\n",
    "\n",
    "**Input:** A register of $N$ qubits $x$, stored as an array.\n",
    "\n",
    "**Goal:** Add a phase of $-1$ to each basis state that has the most significant bit of $x$ equal to $1$, and do nothing to the rest of the basis states. \n",
    "Remember that the most significant bit of $x$ is stored in the first qubit of the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata E3_QuantumOracle_Test\n",
    "\n",
    "operation PhaseOracle_MostSignificantBit (x : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part III. Quantum Algorithm\n",
    "\n",
    "Now that we have figured out how the oracles work and looked at the Deutsch algorithm, we can get back to solving the big problem. We'll present the algorithm in detail step-by-step and summarize it in the end.\n",
    "\n",
    "### Inputs\n",
    "\n",
    "You are given the number of bits in the oracle input $N$ and the oracle itself - a \"black box\" operation $U_f$ that implements a classical function $f(x)$. You are guaranteed that the function implemented by the oracle is either constant or balanced.\n",
    "\n",
    "### The starting state\n",
    "\n",
    "The algorithm starts with $N$ qubits in the $|0...0\\rangle = |0\\rangle^{\\otimes N}$ state.\n",
    "\n",
    "### Step 1. Apply Hadamard transform to each qubit\n",
    "\n",
    "Applying the H gate to one qubit in the $|0\\rangle$ state converts it to the $\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle \\big)$ state, which is an equal superposition of both basis states on one qubit. \n",
    "\n",
    "If we apply the H gate to each of the two qubits in the $|00\\rangle$ state, we'll get \n",
    "\n",
    "$$(H \\otimes H) |00\\rangle = \\big(H |0\\rangle \\big) \\otimes \\big(H |0\\rangle\\big) = \\left(\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle \\big)\\right) \\otimes \\left(\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle \\big)\\right) = \\frac{1}{2} \\big(|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle \\big)$$\n",
    "\n",
    "This is just an equal superposition of all basis states on two qubits! \n",
    "We can extend the same thinking to applying the H gate to each of the $N$ qubits in the $|0...0\\rangle$ state to conclude that this transforms them into a state that is an equal superposition of all basis states on $N$ qubits.\n",
    "\n",
    "Mathematically the transformation \"apply H gate to each of the $N$ qubits\" can be denoted as $H^{\\otimes N}$. After applying this transformation we'll get the following state:\n",
    "\n",
    "$$H^{\\otimes N} |0\\rangle^{\\otimes N} = \\big( H|0\\rangle \\big)^{\\otimes N} = \\left( \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle \\big) \\right)^{\\otimes N} = \\frac{1}{\\sqrt{2^N}} \\sum_{x=0}^{2^N-1} |x\\rangle$$\n",
    "\n",
    "\n",
    "### Step 2. Apply the oracle\n",
    "\n",
    "This step is the only step in which we use the knowledge of the classical function, given to us as the quantum oracle. \n",
    "This step will keep the amplitudes of the basis states for which $f(x) = 0$ unchanged, and multiply the amplitudes of the basis states for which $f(x) = 1$ by $-1$.\n",
    "\n",
    "Here is an example of the way the amplitudes of the states will change. After the first step the amplitudes of all basis states were the same: \n",
    "\n",
    "![Amplitudes after the first step of Deutsch-Jozsa algorithm](./img/Step1-amplitudes-800.png)\n",
    "\n",
    "Once the oracle is applied, some of the amplitudes will change to negative ones:\n",
    "\n",
    "![Amplitudes after the second step of Deutsch-Jozsa algorithm](./img/Step2-amplitudes-800.png)\n",
    "\n",
    "Mathematically the results of oracle application can be written as follows:\n",
    "\n",
    "$$U_f \\left(\\frac{1}{\\sqrt{2^N}} \\sum_{x=0}^{2^N-1} |x\\rangle \\right) = \\frac{1}{\\sqrt{2^N}} \\sum_{x=0}^{2^N-1} U_f|x\\rangle = \\frac{1}{\\sqrt{2^N}} \\sum_{x=0}^{2^N-1} (-1)^{f(x)} |x\\rangle$$\n",
    "\n",
    "### Step 3. Apply Hadamard transform to each qubit again\n",
    "\n",
    "In this step, let's not worry about the whole expression for the state of the qubits after applying the H gates to them; instead let's calculate only the resulting amplitude of the basis state $|0\\rangle^{\\otimes N}$.\n",
    "\n",
    "Consider one of the basis states $|x\\rangle$ in the expression $\\sum_{x=0}^{2^N-1} (-1)^{f(x)} |x\\rangle$.  \n",
    "It can be written as $|x\\rangle = |x_{0} \\rangle \\otimes \\cdots \\otimes |x_{N-1}\\rangle$, where each $|x_k\\rangle$ is either $|0\\rangle$ or $|1\\rangle$.  \n",
    "When we apply the H gates to $|x\\rangle$, we'll get $H^{\\otimes N} |x\\rangle = H|x_{0} \\rangle \\otimes \\cdots \\otimes H|x_{N-1}\\rangle$, where each term of the tensor product is either $H|0\\rangle = \\frac{1}{\\sqrt2}\\big(|0\\rangle + |1\\rangle \\big) = |+\\rangle$ or $H|1\\rangle = \\frac{1}{\\sqrt2}\\big(|0\\rangle - |1\\rangle \\big) = |-\\rangle$. \n",
    "If we open the brackets in this tensor product, we'll get a superposition of all $N$-qubit basis states, each of them with amplitude $\\frac{1}{\\sqrt{2^N}}$ or $-\\frac{1}{\\sqrt{2^N}}$ — and, since the amplitude of the $|0\\rangle$ state in both $|+\\rangle$ and $|-\\rangle$ is positive, we know that the amplitude of the basis state $|0\\rangle^{\\otimes N}$ will end up positive, i.e., $\\frac{1}{\\sqrt{2^N}}$.\n",
    "\n",
    "Now we can calculate the amplitude of the $|0\\rangle^{\\otimes N}$ state in the expression $H^{\\otimes N} \\left( \\frac{1}{\\sqrt{2^N}} \\sum_{x=0}^{2^N-1} (-1)^{f(x)} |x\\rangle \\right)$: in each of the $2^N$ terms of the sum its amplitude is $\\frac{1}{\\sqrt{2^N}}$; therefore, we get the total amplitude\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2^N}} \\sum_{x=0}^{2^N-1} (-1)^{f(x)} \\frac{1}{\\sqrt{2^N}} = \\frac{1}{2^N} \\sum_{x=0}^{2^N-1} (-1)^{f(x)}$$\n",
    "\n",
    "### Step 4. Perform measurements and interpret the result\n",
    "\n",
    "So far we did not use the fact that the function we are given is constant or balanced. Let's see how this affects the amplitude of the $|0\\rangle^{\\otimes N}$ state.\n",
    "\n",
    "If the function is constant, $f(x) = C$ (either always $0$ or always $1$), we get $\\frac{1}{2^N} \\sum_{x=0}^{2^N-1} (-1)^{f(x)} = \\frac{1}{2^N} \\sum_{x=0}^{2^N-1} (-1)^{C} = \\frac{1}{2^N} \\cdot 2^N (-1)^C = (-1)^C$. \n",
    "Since the sum of squares of amplitudes of all basis states always equals $1$, the amplitudes of the rest of the basis states have to be 0 - this means that the state of the qubits after step 3 *is* $|0\\rangle^{\\otimes N}$.\n",
    "\n",
    "If the function is balanced, i.e., returns $0$ for exactly half of the inputs and $1$ for the other half of the inputs, exactly half of the terms in the sum $\\frac{1}{2^N} \\sum_{x=0}^{2^N-1} (-1)^{f(x)}$ will be $1$ and the other half of the terms will be $-1$, and they will all cancel out, leaving the amplitude of $|0\\rangle^{\\otimes N}$ equal to $0$.\n",
    "\n",
    "Now, what happens when we measure all qubits? (Remember that the probability of getting a certain state as a result of measurement equals to the square of the amplitude of this state.)\n",
    "\n",
    "If the function is constant, the only measurement result we can get is all zeros - the probability of getting any other result is $0$. If the function is balanced, the probability of getting all zeros is $0$, so we'll get any measurement result except this.\n",
    "\n",
    "This is exactly the last step of the algorithm: **measure all qubits, if all measurement results are 0, the function is constant, otherwise it is balanced**.\n",
    "\n",
    "### Summary\n",
    "\n",
    "In the end the algorithm is very straightforward:\n",
    "\n",
    "1. Apply the H gate to each qubit.\n",
    "2. Apply the oracle.\n",
    "3. Apply the H gate to each qubit again.\n",
    "4. Measure each qubits.\n",
    "5. If all qubits were measured in $|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": [
    "## <span style=\"color:blue\">Exercise 4</span>: Implement the quantum algorithm!\n",
    "\n",
    "**Inputs:** \n",
    "1. The number of bits in the input $N$ ($1 \\le N \\le 5$).\n",
    "2. The \"black box\" oracle the implements $f(x)$.  \n",
    "  You are guaranteed that the function implemented by the oracle is either constant or balanced.\n",
    "\n",
    "**Goal:** Return `true` if the function is constant, or `false` if it is balanced.\n",
    "\n",
    "> Useful documentation: [Q# Control Flow](https://docs.microsoft.com/quantum/language/statements#control-flow)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata E4_QuantumAlgorithm_Test\n",
    "\n",
    "operation DeutschJozsaAlgorithm (N : Int, oracle : (Qubit[] => Unit)) : Bool {\n",
    "    // Create a boolean variable for storing the return value.\n",
    "    // You'll need to update it later, so it has to be declared as mutable.\n",
    "    mutable isConstant = ...;\n",
    "\n",
    "    // Allocate an array of N qubits for the input register x.\n",
    "    using (x = Qubit[...]) {\n",
    "        // Newly allocated qubits start in the |0⟩ state.\n",
    "        // The first step is to prepare the qubits 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 register.\n",
    "        // The syntax is the same as for applying any function or operation.\n",
    "        // ...\n",
    "\n",
    "        // Apply a Hadamard gate to each qubit of the input register again.\n",
    "        // ...\n",
    "\n",
    "        // Measure each qubit of the input register in the computational basis using the M operation.\n",
    "        // You can use a for loop to iterate over the range of indexes 0..N-1.\n",
    "        // Note that you can't return the answer in the middle of a loop,\n",
    "        // you have to update the variable isConstant using the \"set\" keyword.\n",
    "        // ...\n",
    "\n",
    "        // Before releasing the qubits make sure they are all in the |0⟩ state\n",
    "        // (otherwise you'll get a ReleasedQubitsAreNotInZeroState exception).\n",
    "        // You can use the library operation Reset which measures a qubit and applies a correction if necessary.\n",
    "        // The library operation ResetAll does the same for a register of qubits.\n",
    "        // ...\n",
    "    }\n",
    "    \n",
    "    // Return the value of the boolean variable.\n",
    "    return ...;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part IV. Running the Algorithm\n",
    "\n",
    "You have implemented the quantum version of the 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 in part II 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_DeutschJozsaAlgorithm` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_DeutschJozsaAlgorithm`).\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 Run_DeutschJozsaAlgorithm () : String {\n",
    "    // You can use Fact function to check that the return value of DeutschJozsaAlgorithm operation matches the expected value.\n",
    "    // Uncomment the next line to run it.\n",
    "    \n",
    "    // Fact(DeutschJozsaAlgorithm(4, PhaseOracle_Zero) == true, \"f(x) = 0 not identified as constant\");\n",
    "    \n",
    "    // Run the algorithm for the rest of the oracles\n",
    "    // ...\n",
    "    \n",
    "    // If all tests pass, report success!\n",
    "    return \"Success!\";\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate Run_DeutschJozsaAlgorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part V. What's Next?\n",
    "\n",
    "We hope you've enjoyed this tutorial and learned a lot from it! If you're looking to learn more about quantum computing and Q#, here are some suggestions:\n",
    "\n",
    "* The [Quantum Katas](https://github.com/microsoft/QuantumKatas/) are sets of programming exercises on quantum computing that can be solved using Q#. They cover a variety of topics, from the basics like the concepts of superposition and measurements to more interesting algorithms like Grover's search.\n",
    "* In particular, [DeutschJozsaAlgorithm kata](https://github.com/microsoft/QuantumKatas/tree/master/DeutschJozsaAlgorithm) offers you more exercises on quantum oracles, a different presentation of Deutsch–Jozsa algorithm, and a couple of similar algorithms."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}