tutorials/ExploringDeutschJozsaAlgorithm/DeutschJozsaAlgorithmTutorial_P3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Deutsch–Jozsa Algorithm Tutorial (Part III)\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](./DeutschJozsaAlgorithmTutorial_P2.ipynb) introduces single-qubit quantum oracles and the Deutsch algorithm for solving the problem for one-bit input functions.\n",
    "3. Part III 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 III. Multi-qubit quantum oracles and Deutsch-Jozsa algorithm\n",
    "\n",
    "## Multi-qubit oracles: the definition\n",
    "\n",
    "Expanding on the oracle definition from [part II of this tutorial](./DeutschJozsaAlgorithmTutorial_P2.ipynb#Single-qubit-oracles:-the-definition),\n",
    "the oracle for the general Deutsch-Jozsa problem is defined using a classical function $f : \\{0, 1\\}^N \\to \\{0, 1\\}$ which takes an $N$-bit binary input and produces an 1-bit binary output.\n",
    "\n",
    "To enable the oracle to act on quantum states instead of classical values, the 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",
    "The phase oracle $U_f$ for this function is defined as follows:\n",
    "\n",
    "$$U_f |\\vec{x} \\rangle = (-1)^{f(x)} |\\vec{x} \\rangle$$\n",
    "\n",
    "## Implementing multi-qubit oracles in Q&#x23;\n",
    "\n",
    "Let's take a look at how to implement multi-qubit oracles for some classical functions in Q#. We'll consider the same functions we used as an example in part I of the tutorial.\n",
    "\n",
    "> **Note:**\n",
    "All code snippets before Exercise 5 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: same as in the single-qubit oracle case, 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!"
   ]
  },
  {
   "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 also similar to the single-qubit oracle case: if $f(x) \\equiv 1$, $U_f |x\\rangle \\equiv (-1)^1 |x\\rangle = - |x\\rangle$, the oracle applies a global phase of $-1$ to the state which can be done using Q# library operation [Microsoft.Quantum.Intrinsic.R](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.r):"
   ]
  },
  {
   "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 \\bmod 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).\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 (here $\\bigoplus$ denotes sum modulo 2):\n",
    "\n",
    "$$f(x) = \\bigoplus_{k=0}^{N-1} x_k$$ \n",
    "\n",
    "Let's substitute this expression in the expression for the oracle effect on the quantum state:\n",
    "\n",
    "$$U_f |x\\rangle = (-1)^{f(x)} |x\\rangle = (-1)^{\\bigoplus_{k=0}^{N-1} x_k} |x\\rangle$$\n",
    "\n",
    "Since $(-1)^2 = 1$, we can replace sum modulo 2 with a regular sum in the exponent. Then we'll be able to rewrite it as a product of individual exponents for each bit:\n",
    "\n",
    "$$U_f |x\\rangle = (-1)^{\\sum_{k=0}^{N-1} x_k} |x\\rangle = \\prod_{k=0}^{N-1} {(-1)^{x_k}} |x\\rangle$$\n",
    "\n",
    "Now let's spell out the system state as a tensor product of individual qubit states:\n",
    "\n",
    "$$U_f |x\\rangle = \\prod_{k=0}^{N-1} {(-1)^{x_k}} |x_{0} \\rangle \\otimes \\cdots \\otimes |x_{N-1}\\rangle$$\n",
    "\n",
    "Tensor product is a linear operation, so we can bring each $(-1)^{x_k}$ scalar factor in next to the corresponding $|x_k\\rangle$:\n",
    "\n",
    "$$U_f |x\\rangle = (-1)^{x_0} |x_{k}\\rangle \\otimes \\dots \\otimes (-1)^{x_{N-1}} |x_{N-1}\\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 5</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 T5_MostSignificantBitOracle\n",
    "\n",
    "operation PhaseOracle_MostSignificantBit (x : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deutsch-Jozsa Algorithm\n",
    "\n",
    "Now that we have looked at the Deutsch algorithm and practiced implementing multi-qubit oracles, 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. Finally, we'll demonstrate the behavior of the algorithm visually for two different oracles.\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",
    "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$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 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 all 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": [
    "### Visualization\n",
    "\n",
    "Two examples of the algorithm in action are shown below using a simulation with 8 qubits. \n",
    "\n",
    "> We are using a visualization produced by the [Quantum State Visualizer](https://github.com/microsoft/Quantum/tree/main/samples/runtime/state-visualizer) sample that is part of the QDK. It plots the amplitudes of each basis state as a histogram and allows us to track the changes in the amplitudes throughout the algorithm simulation.\n",
    "\n",
    "First, consider the `PhaseOracle_One` oracle discussed above, which implements a constant function $f(x) = 1$. Observe how the final step of the algorithm converges on a measurement of 0 for all qubits, as expected for a constant function:\n",
    "\n",
    "<video controls width=800 height=600 src=\"state_viz_constant_annotated.mp4\">Amplitudes change animation for constant function</video>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Second, consider the `PhaseOracle_Xmod2` oracle discussed above, which implements a balanced function $f(x) = x \\bmod 2$. Observe how the final step of the algorithm converges on a non-zero measurement, indicating that the function is not constant.\n",
    "\n",
    "<video controls width=800 height=600 src=\"state_viz_balanced_annotated.mp4\">Amplitudes change animation for balanced function</video>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:blue\">Exercise 6</span>: Implement the Deutsch-Jozsa 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# iterations](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/iterations) and [Q# conditional branching](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/conditionalbranching)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T6_DeutschJozsaAlgorithm\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",
    "    use x = Qubit[...];\n",
    "    // Newly allocated qubits start in the |0⟩ state.\n",
    "\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",
    "    // To apply this to each qubit, you can use a for loop to iterate over all array elements\n",
    "    // using the following syntax: for q in qs { ... }\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 qubits of the array again.\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",
    "    // Return the value of the boolean variable.\n",
    "    return ...;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Running the Deutsch-Jozsa algorithm\n",
    "\n",
    "You have implemented the quantum version of the Deutsch-Jozsa 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 `RunDeutschJozsaAlgorithm` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate RunDeutschJozsaAlgorithm`).\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 RunDeutschJozsaAlgorithm () : String {\n",
    "    // You can use Fact function to check that the return value \n",
    "    // 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 RunDeutschJozsaAlgorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Different function types - what if our function is neither balanced nor constant?\n",
    "\n",
    "The setup for the Deutsch-Jozsa algorithm presupposes that the function we're trying to identify is perfectly constant or perfectly balanced in its output (indeed, we haven't even considered the possibility that an input outside of this space could be used). Although the algorithm will not converge to a solution in the same manner that we've seen so far when selecting another type of function as input, we can still derive some intuition for how quantum states behave probabilistically by considering some outside-the-box cases.\n",
    "\n",
    "Before thinking about particular cases, it's worthwhile to consider how to classify (in a purely qualitative fashion) our function $f(x)$ with respect to its outputs being balanced or constant. One might consider $f(x)$ to be a superposition of balanced and constant functions, such that it conveys incomplete properties of both types. $f(x)$ could then be said to be balanced for some subset of its inputs and constant for the remainder. We could ask ourselves, \"How balanced is $f(x)$?\" in the same way that we might ask, for a qubit, \"How 'close' is the qubit to a $|0\\rangle$ or $|1\\rangle$ state?\"\n",
    "\n",
    "For example, consider the following oracle that introduces an unbalanced (read: 'constant') aspect into what you might recognize as the operation for `PhaseOracle_Xmod2`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation PhaseOracle_AlmostBalanced (x : Qubit[]) : Unit {\n",
    "    // Add a -1 phase to the last qubit's |1⟩ basis state, balancing the overall state space evenly\n",
    "    Z(x[Length(x) - 1]);\n",
    "    \n",
    "    // Add a -1 phase to the |11111111⟩ basis state\n",
    "    // (using all qubits except the last one as controls for the Z gate)\n",
    "    Controlled Z(x[0 .. Length(x) - 2], x[Length(x) - 1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As noted, if this oracle is considered in the 8-qubit case, an additional $-1$ phase is introduced for the $|11111111\\rangle$ state.\n",
    "\n",
    "When we run this oracle through the algorithm, you can see that the probability amplitudes that we see *almost* perfectly match those for the case of a balanced function implemented by `PhaseOracle_Xmod2`. However, a probabilistic tail of very small, but nonzero, likelihood trails our idealized state that we would expect for a balanced function. Hence, we are not guaranteed to measure that the result of the algorithm is 1.\n",
    "\n",
    "<video controls width=800 height=600 src=\"almost_balanced_deutsch_josza_annotated.mp4\">Amplitude change animation for nearly-balanced function</video>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a final example, on the other side of the constancy spectrum, consider this almost constant oracle, nearly identical to the `PhaseOracle_Zero` oracle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation PhaseOracle_AlmostConstant (x : Qubit[]) : Unit {\n",
    "    // Add a -1 phase to the |11111111⟩ basis state\n",
    "    // (using all qubits except the last one as controls for the Z gate)\n",
    "    Controlled Z(x[0 .. Length(x) - 2], x[Length(x) - 1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This time, as noted, only a single state $|11111111\\rangle$ will be affected, causing the resultant distribution to be only slightly non-constant. As the algorithm progresses, also note that the same type of probabilistic tail is produced as above - but, this time, it detracts from the probability of measuring a result of 0!\n",
    "\n",
    "<video controls width=800 height=600 src=\"almost_constant_deutsch_josza_annotated.mp4\">Amplitude change animation for nearly-balanced function</video>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an exercise, you can try modifying the oracles discussed in this kata to make them neither purely constant nor purely balanced. With a little tweaking, you can see that the superposition of final, pre-measurement states falls between $|0\\rangle$ and $|1\\rangle$ proportionate to how constant or balanced the function is, respectively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 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/main/DeutschJozsaAlgorithm) offers you more exercises on quantum oracles, a different presentation of the Deutsch–Jozsa algorithm, and a couple of similar algorithms to explore.\n",
    "\n",
    "Continue to [part IV](./AQ/DeutschJozsaAlgorithmTutorial_P4.ipynb) to learn to run quantum algorithms in the cloud using Azure Quantum."
   ]
  }
 ],
 "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
}