tutorials/Oracles/Oracles.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Oracles Tutorial\n",
    "\n",
    "Quantum oracles are a key part of many quantum algorithms that rely on quantum implementation of a classical function. The algorithms' discussions often assume that the quantum oracle that implements the function of interest is provided.  This tutorial dives deeper into the definition of different types of quantum oracles, their properties, and the basic ways to implement the oracles.\n",
    "\n",
    "This tutorial will:\n",
    "* introduce you to quantum oracles and how they relate to classical oracles,\n",
    "* explain two types of quantum oracles - phase oracles and marking oracles,\n",
    "* introduce phase kickback and its uses for oracles implementation,\n",
    "* teach you to implement quantum oracles in Q# and to test your implementations.\n",
    "\n",
    "Before diving into the material, we recommend you to make sure you're comfortable with the fundamental quantum concepts, in particular [basic quantum computing gates](../MultiQubitGates/MultiQubitGates.ipynb) (especially controlled gates).\n",
    "\n",
    "Let's get started!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part I. Introduction to Quantum Oracles\n",
    "\n",
    "## Classical Oracles\n",
    "In classical computing, we often discuss \"black box\" versus \"white box\" testing.  In \"white box\" testing, the implementation of a function is visible to the tester,  thus they can verify specific runtime or memory complexity expectations for the algorithm.  \n",
    "However, in \"black box\" testing the tester doesn't have access to the details of the function implementation, but only to the \"box\" that takes an input and produces the corresponding output. This means the tester can only test the functionality and expected behavior of the function, but not the implementation has been abstracted away.\n",
    "\n",
    "Formally, a **classical oracle** is a function that, provided some input, produces a *deterministic* output\n",
    "(the same input *always* results in the same output).\n",
    "\n",
    "Some classical problems (typically [decision problems](https://en.wikipedia.org/wiki/Decision_problem)) are also expressed in terms of oracles; in this case we do not care about how the function is implemented, but only about the functionality that it provides.  \n",
    "\n",
    "> Suppose I provided you a function which takes two list parameters as input, where these lists represent the availability of two employees at a company during the week.  The function returns true if there is a day (Monday, Tuesday, Wednesday, Thursday, or Friday) for which they are both free and could schedule a meeting, and false if no such date exists.\n",
    ">\n",
    "> This function is an example of a classical oracle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Task 1.1</span>: Implement a classical oracle\n",
    "**Input:** \n",
    "  A bit vector of length 3 represented as a `Bool[]` - a binary representation of a number.\n",
    "\n",
    "**Output:**\n",
    "  Return `true` if the input array represents the number $7$, and `false` otherwise.\n",
    "\n",
    "**Examples:**\n",
    "\n",
    "* If the input array is `[true, true, true]`, return `true`.\n",
    "* If the input array is `[true, true, false]`, return `false`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_IsSeven_ClassicalOracle\n",
    "\n",
    "function IsSeven(x: Bool[]) : Bool {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum Oracles\n",
    "\n",
    "An oracle in the quantum world is a \"black box\" operation that is used as input to an algorithm (such as Deutsch-Jozsa algorithm or Grover's search algorithm which you'll learn later). \n",
    "Many quantum algorithms assume an oracle implementation of some classical function as input, but this is a very strong assumption - sometimes implementing the oracle for a function is a lot more complex than the algorithm that will use this oracle!  \n",
    "In this tutorial you will learn the properties of quantum oracles and how to implement them.\n",
    "\n",
    "A quantum oracle implements a function $f: \\{0,1\\}^n \\rightarrow \\{0,1\\}^m$, where $x$ is an $n$-bit input state\n",
    "of the form $x = (x_{0}, x_{1}, \\dots, x_{n-1})$. In most commonly used cases $m=1$, i.e., the function can return values $0$ or $1$; in this tutorial we will focus on this class of functions.\n",
    "\n",
    "Quantum oracles operate on qubit arrays (and can take classical parameters as well).  The classical input is encoded into the state of an $n$-qubit register:  \n",
    "$$|x\\rangle = |x_0\\rangle \\otimes |x_1\\rangle \\otimes ... \\otimes |x_{n-1}\\rangle,$$ \n",
    "where $|x_i\\rangle$ represents the state of the $i$-th qubit.  \n",
    "\n",
    "Oracles must be unitary transformations, and follow the same rules of linear algebra as other quantum operations. (See the [linear algebra tutorial](../LinearAlgebra/LinearAlgebra.ipynb) if you need a refresher.)\n",
    "This allows us to define quantum oracles based on their effect on the basis states - tensor products of single-qubit basis states $|0\\rangle$ and $|1\\rangle$. \n",
    "\n",
    "> For example, an oracle that implements a function that takes 2 bits of input will be defined using its effect on basis states $|00\\rangle$, $|01\\rangle$, $|10\\rangle$, and $|11\\rangle$.  \n",
    "\n",
    "There are two types of quantum oracles: phase oracles and marking oracles.  Let's take a closer look at them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Phase Oracles\n",
    "A phase oracle $U_{phase}$ is an oracle that encodes the value of the classical function $f$ it implements in the *phase* of the qubit state. When provided an input basis state $|\\vec{x}\\rangle$, it flips the sign of that state if $f(x)=1$:\n",
    "\n",
    "$$U_{phase} |\\vec{x}\\rangle = (-1)^{f(x)}|\\vec{x}\\rangle$$\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",
    "A phase oracle doesn't have an \"output\", unlike the function it implements; the effect of the oracle application is the change in the state of the system.\n",
    "\n",
    "### <span style=\"color:blue\">Demo 1.1</span>: Phase oracle for alternating bit pattern function\n",
    "\n",
    "Consider the function $f(x)$ that takes $3$ bits of input and returns $1$ if $x=101$ or $x=010$, and $0$ otherwise.\n",
    "\n",
    "The phase oracle that implements this function will take an array of 3 qubits as an input, flip the sign of basis states $|101\\rangle$ and $|010\\rangle$, and leave the rest of the basis states unchanged. Let's see the effect of this oracle on a superposition state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "// This operation implements the oracle; we will learn how to implement oracles later in the tutorial\n",
    "operation AlternatingBitPattern_PhaseOracle (x: Qubit[]) : Unit is Adj + Ctl {\n",
    "    let PatternOne = ControlledOnBitString([false, true, false], Z);\n",
    "    let PatternTwo = ControlledOnBitString([true, false, true], Z);\n",
    "    use q = Qubit();\n",
    "    X(q);\n",
    "    PatternOne(x, q);\n",
    "    PatternTwo(x, q);\n",
    "    X(q);\n",
    "}\n",
    "\n",
    "operation PhaseOracle_Demo() : Unit {\n",
    "    // Allocate 3 qubits in the |000⟩ state\n",
    "    use q = Qubit[3];\n",
    "    // Prepare an equal superposition of all basis states\n",
    "    ApplyToEachA(H, q);\n",
    "\n",
    "    // Print the current state of the system; notice the phases of each basis state\n",
    "    Message(\"Starting state (equal superposition of all basis states):\");\n",
    "    DumpMachine();\n",
    "\n",
    "    // Apply the oracle\n",
    "    AlternatingBitPattern_PhaseOracle(q);\n",
    "\n",
    "    // Print the resulting state; notice which phases changed\n",
    "    Message(\"State after applying the phase oracle:\");\n",
    "    DumpMachine();\n",
    "\n",
    "    // Reset our state back to all zeros for deallocation\n",
    "    ResetAll(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "%simulate PhaseOracle_Demo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We introduced the function [ControlledOnBitString](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring) provided by the Q# Standard library.\n",
    "It defines a variant of a gate controlled on a state specified by a bit mask; for example, bit mask `[true, false]` means that the gate should be applied only if the two control qubits are in the $|10\\rangle$ state.\n",
    " \n",
    "The sequence of steps that implement this variant are:\n",
    "1. Apply the $X$ gate to each control qubit that corresponds to a `false` element of the bit mask. After this, if the control qubits started in the $|10\\rangle$ state, they'll end up in the $|11\\rangle$ state, and if they started in any other state, they'll end up in any state but $|11\\rangle$.\n",
    "2. Apply the regular controlled version of the gate.\n",
    "3. Apply the $X$ gate to the same qubits to return them to their original state.\n",
    "\n",
    "Due to this [conjugation pattern](https://learn.microsoft.com/en-us/azure/quantum/user-guide/language/statements/conjugations), the time complexity of this function is 2 * N, where N is the number of control qubits. To learn its internal implementation (and the very similar [ControlledOnInt](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint)), please refer to the [Q# source code](https://github.com/microsoft/QuantumLibraries/blob/c0b851735542117cf6d73f8946ab6eef8c84384d/Standard/src/Canon/Utils/ControlledOnBitString.qs#L107)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Notice that the input state in the demo above is an equal superposition of all basis states. \n",
    "After applying the oracle the absolute values of all amplitudes are the same, but the states $|010\\rangle$ and $|101\\rangle$ had their phase flipped to negative!  \n",
    "> Recall that these two states are exactly the inputs for which $f(x) = 1$, thus they are exactly the two states we expect to experience a phase flip!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you will implement the classical oracle that you've implemented in task 1.1 as a quantum phase oracle $U_{7,phase}$.\n",
    "\n",
    "### <span style=\"color:blue\">Task 1.2</span>: Implement a phase oracle\n",
    "\n",
    "**Input:**\n",
    "  3 qubits in an arbitrary state $|x\\rangle$ (input/query register).\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Flip the sign of the input state $|x\\rangle$ if the input register is in\n",
    "the state $|111\\rangle$ (encoding the integer $7$), and leave the input register unchanged otherwise.  \n",
    "Don't allocate extra qubits to perform this operation.\n",
    "\n",
    "**Examples:**\n",
    "\n",
    "* If the query register is in the state $|111\\rangle$, flip its sign.\n",
    "* If the query register is in the state $|010\\rangle$ or $|101\\rangle$, do nothing.\n",
    "\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  To solve this problem, you need to find a gate that will only flip the sign of the $|111\\rangle$ basis state.  Which single-qubit gate flips the sign of the basis state $|1\\rangle$ but not $|0\\rangle$? How can you modify this gate to solve this problem?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_IsSeven_PhaseOracle \n",
    "\n",
    "operation IsSeven_PhaseOracle (x : Qubit[]) : Unit is Adj + Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "    <summary><b>For a closer look at the mathematical properties of this oracle, click here</b></summary>\n",
    "\n",
    "Consider how the oracle from task 1.2 acts on two basis states:\n",
    "$$U_{7,phase} |111\\rangle = -|111\\rangle$$\n",
    "$$U_{7,phase} |110\\rangle = |110\\rangle$$\n",
    "\n",
    "You can see that $U_{7,phase}$ does not change the input if it's a basis state (other than adding a global phase), and $U_{7,phase}$ does not change the norm of the state ($U_{7,phase}$ is a unitary operator).  \n",
    "\n",
    "However, if we applied this oracle to a superposition state instead, what will that look like?\n",
    "\n",
    "Suppose that $|\\beta\\rangle$ is an equal superposition of the $|6\\rangle$ and $|7\\rangle$ states (encoded in big endian, with most significant bit first): \n",
    "$$|\\beta\\rangle = \\frac{1}{\\sqrt{2}} \\big(|110\\rangle + |111\\rangle\\big) = |11\\rangle \\otimes \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + |1\\rangle\\big) = |11\\rangle \\otimes |+\\rangle = |11+\\rangle$$\n",
    "\n",
    "Let's consider how our operator $U_{7,phase}$ acts on this state:\n",
    "$$U_{7,phase} |\\beta\\rangle = U_{7,phase} \\Big[\\frac{1}{\\sqrt{2}} \\big(|110\\rangle + |111\\rangle\\big)\\Big] = $$\n",
    "$$= \\frac{1}{\\sqrt{2}} \\big(U_{7,phase} |110\\rangle + U_{7,phase} |111\\rangle\\big) = \\frac{1}{\\sqrt{2}} \\big(|110\\rangle - |111\\rangle\\big) := |\\gamma\\rangle$$\n",
    "\n",
    "Was our input state modified during this operation? Let's simplify $|\\gamma\\rangle$:\n",
    "$$|\\gamma\\rangle = \\frac{1}{\\sqrt{2}} \\big(|110\\rangle - |111\\rangle\\big) = |11\\rangle \\otimes \\frac{1}{\\sqrt{2}} \\big(|0\\rangle - |1\\rangle\\big) = $$\n",
    "$$= |11\\rangle \\otimes |-\\rangle = |11-\\rangle \\neq |\\beta\\rangle$$\n",
    "\n",
    "Here we see that the oracle modifies the input, if the input state was a *superposition* of the basis states, as a phase oracle will only modify the sign of the basis states.  Thus when a superposition state is provided as input to an oracle, the input state can be modified via the application of the quantum oracle.\n",
    "\n",
    "> It is also worth noting that while the oracle modified the input when provided a superposition state, it did *not* modify the norm of that state.  As an exercise, you can verify this yourself by taking the norm of $|\\beta\\rangle$ and $|\\gamma\\rangle$, which both will result in a value of $1$.\n",
    ">\n",
    "> As another exercise, consider how you could distinguish between the input and output state programmatically?  Is there an operation that you could apply to the initial state $|\\beta\\rangle$ and the final state $|\\gamma\\rangle$ to show that the two states are not equivalent through measurement?  As a hint, think about how you could convert the superposition states $|\\beta\\rangle$ and $|\\gamma\\rangle$ into the basis states.\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Marking Oracles\n",
    "\n",
    "A marking oracle $U_{mark}$ is an oracle that encodes the value of the classical function $f$ it implements in the *amplitude* of the qubit state. When provided an input array of qubits in the basis state $|\\vec{x}\\rangle$ and an output qubit in the basis state $|y\\rangle$, it flips the state of the output qubit if $f(x)=1$. (You can also represent this as addition modulo 2 between $f(x)$ and $y$.)  Hence $U_{mark}$ is an operator that performs the following operation:\n",
    "\n",
    "$$U_{mark}|\\vec{x}\\rangle |y\\rangle = U_{mark}\\big(|\\vec{x}\\rangle \\otimes |y\\rangle\\big) = |\\vec{x}\\rangle \\otimes |y \\oplus f(x)\\rangle$$\n",
    "\n",
    "Again, since all quantum operations are linear, you can figure out the effect of this operation on superposition state knowing its effect on the basis states using its linearity. \n",
    "\n",
    "A marking oracle has distinct \"input\" and \"output\" qubits, but in general the effect of the oracle application is the change in the state of the whole system rather than of the \"output\" qubits only. We will look at this closer in a moment.\n",
    "\n",
    "### <span style=\"color:blue\">Demo 1.2</span>: Marking oracle  for alternating bit pattern function\n",
    "\n",
    "Consider the function $f(x)$ that takes $3$ bits of input and returns $1$ if $x=101$ or $x=010$, and $0$ otherwise (it is the same function we've seen in demo 1.1).\n",
    "\n",
    "The marking oracle that implements this function will take an array of 3 qubits as an \"input\" register and an \"output\" qubit, and will flip the state of the output qubit if the input qubit was in basis state $|101\\rangle$ or $|010\\rangle$, and do nothing otherwise. Let's see the effect of this oracle on a superposition state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "// This operation implements the oracle; we will learn how to implement oracles later in the tutorial\n",
    "operation AlternatingBitPattern_MarkingOracle(x: Qubit[], y: Qubit) : Unit is Adj + Ctl {\n",
    "    let PatternOne = ControlledOnBitString([false, true, false], X);\n",
    "    let PatternTwo = ControlledOnBitString([true, false, true], X);\n",
    "    PatternOne(x, y);\n",
    "    PatternTwo(x, y);\n",
    "}\n",
    "\n",
    "operation MarkingOracle_Demo() : Unit {\n",
    "    // Allocate the qubits in the |000⟩|0⟩ state\n",
    "    use (x, y) = (Qubit[3], Qubit());\n",
    "    // Prepare an equal superposition of all basis states in the input register\n",
    "    ApplyToEachA(H, x);\n",
    "\n",
    "    // Print the current state of the system; notice the amplitudes of each basis state\n",
    "    Message(\"Starting state (equal superposition of all basis states ⊗ |0⟩):\");\n",
    "    DumpMachine();\n",
    "\n",
    "    // Apply the oracle\n",
    "    AlternatingBitPattern_MarkingOracle(x, y);\n",
    "\n",
    "    // Print the resulting state; notice which amplitudes changed\n",
    "    Message(\"State after applying the marking oracle:\");\n",
    "    DumpMachine();\n",
    "\n",
    "    // Reset our state back to all zeros for deallocation\n",
    "    ResetAll(x + [y]);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate MarkingOracle_Demo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Let's compare the initial state to the final state from the above demo. \n",
    "In the initial state we had a tensor product of an equal superposition of all 3-qubit basis states and the state $|0\\rangle$.  In the final state, this is no longer the case. \n",
    "The basis states $|010\\rangle \\otimes |0\\rangle$ and $|101\\rangle \\otimes |0\\rangle$ no longer have non-zero amplitudes, and instead $|010\\rangle \\otimes |1\\rangle$ and $|101\\rangle \\otimes |1\\rangle$ has non-zero amplitudes.\n",
    ">\n",
    "> This is exactly the result that we expect.  Recall our function $f(x)$: $f(x)=1$ if and only if $x=010$ or $x=101$.  The first three qubits (variable `x`) represent the input state $|x\\rangle$, and the last qubit (variable `y`) represents the output state $|y\\rangle$.  Thus when we have the two basis states, $|x\\rangle=|010\\rangle$ or $|x\\rangle=|101\\rangle$, we will flip the state of the qubit $|y\\rangle$, causing these two initial states to be tensored with $|1\\rangle$ in the final state where originally they were tensored with $|0\\rangle$.\n",
    ">\n",
    "> Since the rest of the basis states correspond to $f(x) = 0$, all other basis states in the initial superposition remain unchanged."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you will implement the same function you've seen in the first two tasks as a marking oracle $U_{7,mark}$.\n",
    "\n",
    "### <span style=\"color:blue\">Task 1.3</span>: Implement a marking oracle\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. 3 qubits in an arbitrary state $|x\\rangle$ (input/query register)\n",
    "    \n",
    "  2. A qubit in an arbitrary state $|y\\rangle$ (target qubit)\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Flip the state of $|y\\rangle$ if the input register is in the \n",
    "state $|111\\rangle$, and leave the state $|y\\rangle$ unchanged otherwise.\n",
    "\n",
    "**Examples:**\n",
    "\n",
    "* If the query register is in the state $|111\\rangle$, flip the state of the target qubit $|y\\rangle$.\n",
    "* If the query register is in the state $|010\\rangle$ or $|101\\rangle$, do nothing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_IsSeven_MarkingOracle \n",
    "\n",
    "operation IsSeven_MarkingOracle (x: Qubit[], y: Qubit) : Unit is Adj + Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "    <summary><b>For a closer look at the mathematical properties of this oracle, click here</b></summary>\n",
    "\n",
    "Consider how the oracle from task 1.3 acts on two input basis states and two \"output\" basis states:\n",
    "\n",
    "$$U_{7,mark} |111\\rangle |0\\rangle = |111\\rangle |0 \\oplus f(111)\\rangle = |111\\rangle |0 \\oplus 1\\rangle = |111\\rangle |1\\rangle$$\n",
    "$$U_{7,mark} |111\\rangle |1\\rangle = |111\\rangle |1 \\oplus f(111)\\rangle = |111\\rangle |1 \\oplus 1\\rangle = |111\\rangle |0\\rangle$$\n",
    "\n",
    "$$U_{7,mark} |110\\rangle |0\\rangle = |110\\rangle |0 \\oplus f(110)\\rangle = |110\\rangle |0 \\oplus 0\\rangle = |110\\rangle |0\\rangle$$\n",
    "$$U_{7,mark} |110\\rangle |1\\rangle = |110\\rangle |1 \\oplus f(110)\\rangle = |110\\rangle |1 \\oplus 0\\rangle = |110\\rangle |1\\rangle$$\n",
    "\n",
    "You can see that the state of the input qubit array is unchanged, and the state of the output qubit changes if $f(x) = 1$ and is unchanged if $f(x) = 0$ - this matches the definition of a marking oracle precisely.\n",
    "\n",
    "Now let's again apply this oracle to a superposition state $|\\alpha\\rangle$ such that $|x\\rangle$ is a superposition of the $|6\\rangle$ and $|7\\rangle$ basis states and $|y\\rangle = |0\\rangle$:\n",
    "$$|\\alpha\\rangle = \\frac{1}{\\sqrt{2}}\\big(|110\\rangle + |111\\rangle\\big)|0\\rangle = \n",
    "|11\\rangle \\otimes \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + |1\\rangle\\big) \\otimes |0\\rangle = |11+\\rangle |0\\rangle$$\n",
    "\n",
    "Let's consider how our operator $U_{7,mark}$ acts on this state.\n",
    "\n",
    "> Recall that oracles are linear operators, thus they can be applied to each term individually.\n",
    "\n",
    "$$U_{7,mark} |\\alpha\\rangle = \\frac{1}{\\sqrt{2}} \\big(U_{7,mark}|110\\rangle |0\\rangle + U_{7,mark}|111\\rangle |0\\rangle\\big) =$$\n",
    "$$= \\frac{1}{\\sqrt{2}} \\big(|110\\rangle |0\\rangle + |111\\rangle |1\\rangle\\big) := |\\epsilon\\rangle$$\n",
    "\n",
    "Was our input state modified during this operation?  Let's simplify the resulting state $|\\epsilon\\rangle$:\n",
    "$$|\\epsilon\\rangle = \\frac{1}{\\sqrt{2}} \\big(|110\\rangle |0\\rangle + |111\\rangle |1\\rangle\\big) = |11\\rangle \\otimes \\frac{1}{\\sqrt{2}} \\big(|0\\rangle |0\\rangle + |1\\rangle |1\\rangle\\big) = $$\n",
    "$$= |11\\rangle \\otimes \\frac{1}{\\sqrt{2}} \\big(|00\\rangle + |11\\rangle\\big) = |11\\rangle \\otimes |\\Phi^+\\rangle = |11\\Phi^+\\rangle$$\n",
    "\n",
    "We have entangled the states of qubits $|x\\rangle$ and $|y\\rangle$!  This is a common occurrence for marking oracles when the input is a superposition of basis states: after applying the oracle, the input $|x\\rangle$ will often become entangled with $|y\\rangle$. Thus, while applying the marking oracle to a basis state will leave the input array unchanged, applying the marking oracle to a superposition state will change the state of both the input array and the output qubit.\n",
    "\n",
    ">As an exercise, what entangled state would we get in the previous example if $|y\\rangle = |1\\rangle$ instead of $|y\\rangle = |0\\rangle$?\n",
    ">\n",
    "> <br/>\n",
    "> <details>\n",
    ">   <summary><b>Click here for the answer!</b></summary>\n",
    "> $$U_{7,mark} |11+\\rangle |1\\rangle = |11\\rangle \\otimes \\frac1{\\sqrt2}\\big(|01\\rangle + |10\\rangle\\big) = |11\\rangle |\\Psi^+\\rangle$$\n",
    "> </details>\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part II: Phase Kickback\n",
    "\n",
    "Previously we considered applying marking oracles when the register $|x\\rangle$ was in a basis state or a superposition state, and the target qubit $|y\\rangle$ in a basis state.  How might the effect of applying marking oracles change if the target is also in a superposition state?  In this case we will observe **phase kickback** - the relative phase from the target qubit affecting (\"kicked back\" into) the state of the input qubits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to observe phase kickback, we use the target qubit $|y\\rangle=|-\\rangle$.  \n",
    "\n",
    "> This is the standard choice for two reasons. \n",
    "> First, for phase kickback to occur, the target qubit must have a difference in relative phase between the basis states $|0\\rangle$ and $|1\\rangle$. \n",
    "> Second, the target qubit must be in an equal superposition, otherwise it will become entangled with the input register.\n",
    "\n",
    "Let's see the results of applying a marking oracle $U_{mark}$ which implements the function $f(x)$ to the input register $|x\\rangle$ and the target qubit in state $|-\\rangle$:\n",
    "* If the input register $|x\\rangle$ is in a basis state:\n",
    "$$U_{mark} |x\\rangle |-\\rangle = \\frac1{\\sqrt2} \\big(U_{mark}|x\\rangle|0\\rangle - U_{mark}|x\\rangle |1\\rangle\\big) \n",
    "= \\frac1{\\sqrt2} \\big(|x\\rangle|0\\oplus f(x)\\rangle - |x\\rangle |1\\oplus f(x)\\rangle\\big) = \\\\ \n",
    "= \\begin{cases} \n",
    "    \\frac1{\\sqrt2} \\big(|x\\rangle|0\\rangle - |x\\rangle |1\\rangle\\big) = |x\\rangle|-\\rangle \\text{ if } f(x) = 0 \\\\ \n",
    "    \\frac1{\\sqrt2} \\big(|x\\rangle|1\\rangle - |x\\rangle |0\\rangle\\big) = -|x\\rangle|-\\rangle \\text{ if } f(x) = 1\n",
    "  \\end{cases} \n",
    "= (-1)^{f(x)}|x\\rangle |-\\rangle$$\n",
    "\n",
    "\n",
    "* If the input register is in a superposition state, say $|x\\rangle = \\frac1{\\sqrt2} \\big(|b_1\\rangle + |b_2\\rangle\\big)$, where $|b_1\\rangle$ and $|b_2\\rangle$ are basis states:\n",
    "$$U_{mark} |x\\rangle |-\\rangle = U_{mark} \\frac{1}{\\sqrt{2}} \\big(|b_1\\rangle + |b_2\\rangle\\big) |-\\rangle = \n",
    " \\frac{1}{\\sqrt{2}} \\big( U_{mark}|b_1\\rangle|-\\rangle + U_{mark}|b_2\\rangle|-\\rangle\\big) = \\\\\n",
    "= \\frac{1}{\\sqrt{2}} \\big( (-1)^{f(b_1)}|b_1\\rangle + (-1)^{f(b_2)}|b_2\\rangle\\big) |-\\rangle$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that in both cases applying $U_{mark}$ does not change the state of the target qubit, but it does change the state of the input register. \n",
    "Thus we can drop the target qubit without any repercussions after the application of the oracle. \n",
    "Notice that the input register is now in the following state:\n",
    "$$|\\psi\\rangle = \\frac{1}{\\sqrt{2}} \\big( (-1)^{f(b_1)}|b_1\\rangle + (-1)^{f(b_2)}|b_2\\rangle\\big),$$\n",
    "\n",
    "which looks exactly as if we applied a phase oracle to $|x\\rangle$ instead of applying a marking oracle to $|x\\rangle|-\\rangle$!  This is a very important application of phase kickback: it allows to convert a marking oracle into a phase oracle - which you will implement in the next task.\n",
    "\n",
    "> Another important application of this effect is **phase estimation** algorithm, which allows to estimate an eigenvalue of an eigenvector. You can learn more about this important algorithm in the [PhaseEstimation kata](../../PhaseEstimation/PhaseEstimation.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "    <summary><b>If you would like to see an example of phase kickback using oracles we've previously seen in this tutorial, click here</b></summary>\n",
    "\n",
    "Consider the following example using the $U_{7,mark}$ oracle. Let's begin with $|x\\rangle$ as an equal superposition of the $6$ and $7$ basis states and $|y\\rangle=|-\\rangle$, the overall state is:\n",
    "$$|\\eta\\rangle = \\Big[\\frac{1}{\\sqrt{2}}\\big(|110\\rangle + |111\\rangle\\big)\\Big] \\otimes \\frac{1}{\\sqrt{2}}\\big(|0\\rangle - |1\\rangle\\big) = $$\n",
    "$$ = \\frac{1}{2} \\big(|110\\rangle|0\\rangle + |111\\rangle|0\\rangle - |110\\rangle|1\\rangle - |111\\rangle|1\\rangle\\big)$$\n",
    "\n",
    "How does $U_{7,mark}$ act on this state?\n",
    "$$U_{7,mark}|\\eta\\rangle = U_{7,mark} \\frac{1}{2} \\big(|110\\rangle|0\\rangle + |111\\rangle|0\\rangle - |110\\rangle|1\\rangle - |111\\rangle|1\\rangle \\big) = $$\n",
    "$$= \\frac{1}{2} \\big( U_{7,mark}|110\\rangle|0\\rangle + U_{7,mark}|111\\rangle|0\\rangle - U_{7,mark}|110\\rangle|1\\rangle - U_{7,mark}|111\\rangle|1\\rangle \\big) = $$\n",
    "$$= \\frac{1}{2} \\big(|110\\rangle|0\\rangle + |111\\rangle|1\\rangle - |110\\rangle|1\\rangle - |111\\rangle|0\\rangle \\big) := |\\xi\\rangle$$\n",
    "    \n",
    "Now we would like to observe how our input state $|\\eta\\rangle$ was modified by the oracle.  Let's simplify the resulting state $|\\xi\\rangle$:\n",
    "$$|\\xi\\rangle = \\frac{1}{2} \\big(|110\\rangle|0\\rangle + |111\\rangle|1\\rangle - |110\\rangle|1\\rangle - |111\\rangle|0\\rangle\\big)  = $$\n",
    "$$= \\frac{1}{2} \\big(|110\\rangle|0\\rangle - |110\\rangle|1\\rangle - |111\\rangle|0\\rangle + |111\\rangle|1\\rangle \\big) = $$\n",
    "$$= \\frac{1}{2} \\Big[|110\\rangle \\otimes \\big(|0\\rangle - |1\\rangle \\big) + |111\\rangle \\otimes \\big(|1\\rangle - |0\\rangle\\big)\\Big] = $$\n",
    "$$ = \\Big[\\frac{1}{\\sqrt{2}} \\big( |110\\rangle - |111\\rangle \\big) \\Big] \\otimes \\Big[ \\frac{1}{\\sqrt{2}} \\big( |0\\rangle - |1\\rangle \\big) \\Big] = $$\n",
    "$$= \\Big[\\frac{1}{\\sqrt{2}} \\big( |110\\rangle - |111\\rangle \\big) \\Big] \\otimes |-\\rangle$$\n",
    "\n",
    "Finally, let's compare $|\\eta\\rangle$ and $|\\xi\\rangle$; below are the final equations repeated for your convenience:\n",
    "$$|\\eta\\rangle = \\Big[\\frac{1}{\\sqrt{2}}\\big(|110\\rangle + |111\\rangle\\big)\\Big] \\otimes |-\\rangle$$\n",
    "$$|\\xi\\rangle = \\Big[\\frac{1}{\\sqrt{2}}\\big(|110\\rangle - |111\\rangle\\big)\\Big] \\otimes |-\\rangle$$\n",
    "\n",
    "We can see that these two equations are identical, except for the $-1$ phase that appeared on the $|111\\rangle$ basis state (representing $7$).  This is a specific example of the phase kickback effect, as the phase from $|-\\rangle$ has been *kicked back* into $|x\\rangle$.\n",
    "    \n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>How could we distinguish the states $|\\eta\\rangle = |11+\\rangle |-\\rangle$ and $|\\xi\\rangle = |11-\\rangle |-\\rangle$?  Take a moment to think, then click here to see if you were correct</b></summary>\n",
    "Recall that we can only observe alterations to out input state by performing a measurement.\n",
    "If we apply Hadamard gate to the third qubit, we will be able to distinguish between the input state and the output state. \n",
    "    $$(I\\otimes I \\otimes H)|11+\\rangle = |110\\rangle \\\\ (I\\otimes I \\otimes H)|11-\\rangle = |111\\rangle$$ \n",
    "Now if we were to measure the third qubit, we'll be able to distinguish the starting state and the state after phase kickback occurred.\n",
    "</details>\n",
    "    \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Task 2.1</span>: Apply the marking oracle as a phase oracle\n",
    "**Inputs:**\n",
    "\n",
    "  1. A marking oracle implementing an unknown $N$-bit function $f(x)$.\n",
    "  2. $N$ qubits in an arbitrary state (input/query register).\n",
    "  \n",
    "**Goal:**\n",
    "\n",
    "Flip the phase of each basis state $|x\\rangle$ for which $f(x) = 1$. You can only access $f(x)$ via the marking oracle you are given.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "    Recall that you can allocate extra qubits to assist in this operation.  Is there a state that you could prepare with an auxiliary qubit which would help you to convert the marking oracle to a phase oracle?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_ApplyMarkingOracleAsPhaseOracle\n",
    "\n",
    "operation ApplyMarkingOracleAsPhaseOracle (markingOracle: ((Qubit[], Qubit) => Unit is Adj + Ctl), \n",
    "                                           qubits: Qubit[]) : Unit is Adj + Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Demo 2.1</span>: Oracle conversion\n",
    "\n",
    "In this demo we will use your implementation from task 2.1 to convert the marking oracle from task 1.3 to a phase oracle.  Then we will compare this converted oracle to the phase oracle that you implemented in task 1.2.\n",
    "\n",
    "> *You must have tasks 1.2, 1.3, and 2.1 solved correctly for this demo to work!*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation OracleConverterDemo () : Unit {\n",
    "    // Allocate the qubits in the state |000⟩\n",
    "    use register = Qubit[3];\n",
    "    // Prepare an equal superposition state\n",
    "    ApplyToEachA(H, register);\n",
    "\n",
    "    Message(\"The equal superposition state:\");\n",
    "    DumpMachine();\n",
    "\n",
    "    // Apply the oracle from task 1.2\n",
    "    IsSeven_PhaseOracle(register);\n",
    "\n",
    "    // Dump the state after application of the oracle\n",
    "    Message(\"The state after applying the phase oracle from task 1.2:\");\n",
    "    DumpMachine();\n",
    "\n",
    "    // Reset the qubits for deallocation\n",
    "    ResetAll(register);\n",
    "\n",
    "    // Prepare an equal superposition state again\n",
    "    ApplyToEachA(H, register);\n",
    "\n",
    "    // Apply the marking oracle from task 1.3 as a phase oracle\n",
    "    ApplyMarkingOracleAsPhaseOracle(IsSeven_MarkingOracle, register);\n",
    "\n",
    "    // Dump the state after application of the oracle\n",
    "    Message(\"The state after applying the converted marking oracle from task 1.3:\");\n",
    "    DumpMachine();\n",
    "\n",
    "    // reset the qubits for deallocation\n",
    "    ResetAll(register);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "%simulate OracleConverterDemo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Notice from the above demo that your phase oracle $U_{7,phase}$ behaves the same as the converted version of your marking oracle $U_{7,mark}$, both of which induce a phase flip on the basis state $|111\\rangle$!\n",
    "\n",
    "This way to convert a marking oracle to a phase oracle is useful because many quantum algorithms, such as Grover's search algorithm, rely on a phase oracle, but it is often easier to implement the function as a marking oracle. \n",
    "This converter provides a way to implement the function of interest as a marking oracle and then convert it into a phase oracle, which could then be leveraged in a quantum algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part III: Implementing Quantum Oracles\n",
    "\n",
    "In this section you will implement a few more complicated quantum oracles. \n",
    "\n",
    "> Notice that the operation declarations below require adjoint and controlled variants of the oracle to be automatically generated. This is common practice that makes testing and reusing the code easier. Typically Q# compiler will easily generate these variants, as long as you don't use mutable variables or operations that don't support these functors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Task 3.1</span>: Implement the OR oracle\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. $N$ qubits in an arbitrary state $|x\\rangle$ (input/query register).\n",
    "  2. A qubit in an arbitrary state $|y\\rangle$ (target qubit).\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Flip the state of $|y\\rangle$ if the input register is in any basis state\n",
    "except for $|00...0\\rangle$ (the all zero state).\n",
    "\n",
    "**Examples:**\n",
    "\n",
    "* If the query register is in the state $|10000001\\rangle$, $|11101101\\rangle$ or $|0010101\\rangle$, flip the state $|y\\rangle$.\n",
    "* If the query register is in the state $|000\\rangle$, do nothing.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Before implementing this oracle, answer the question: are you implementing a marking or a phase oracle?  Click here for the answer!</b></summary>\n",
    "    This is a marking oracle, because we are flipping the state of the target qubit $|y\\rangle$ based on the state of the input $|x\\rangle$.\n",
    "</details>\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  You need to flip the state of $|y\\rangle$ for every input except $|00...0\\rangle$, or, alternatively, flip it unconditionally and then flip it for the $|00...0\\rangle$ state.   You may find the Q# library function <a href=\"https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint\">ControlledOnInt</a> useful in your implementation.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T31_Or_Oracle\n",
    "\n",
    "operation Or_Oracle (x: Qubit[], y: Qubit) : Unit is Adj + Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Notice that you can modify the state of the input register during your computations (this is what `ControlledOnInt` function does under the hood). \n",
    "> However, it is essential to undo those modifications (\"uncompute\" the changes), except the final one, so that the oracle will preserve the input if it is a basis state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Task 3.2</span>: Implement the $k$-th bit oracle\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. $N$ qubits in an arbitrary state $|x\\rangle$ (input/query register).\n",
    "  2. An integer $k$ such that $0 \\leq k < N$.\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Flip the sign of the input state $|x\\rangle$ if the $k$-th bit of $x$ is $1$.  \n",
    "**Implement this oracle without using auxiliary qubits.**\n",
    "\n",
    "**Examples:**\n",
    "\n",
    "* If the query register is in the state $|010\\rangle$ and $k=0$, do nothing.\n",
    "* If the query register is in the state $|010\\rangle$ and $k=1$, flip the sign of the basis state.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Before implementing this oracle, answer the question: are you implementing a marking or a phase oracle?  Click here for the answer!</b></summary>\n",
    "    This is a phase oracle, because we are changing the phase of the input state $|x\\rangle$ based on the value of the function $f(x)$.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T32_KthBit_Oracle\n",
    "\n",
    "operation KthBit_Oracle (x: Qubit[], k: Int) : Unit is Adj + Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Notice how the oracles - both phase and marking - can take extra \"classical\" parameters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another key tool for implementing quantum oracles is allocating auxiliary qubits to assist in a computation.  Below are some exercises where you will practice that."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Task 3.3</span>: Implement the OR oracle of all bits except the $k$-th\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. $N$ qubits in an arbitrary state $|x\\rangle$ (input/query register).\n",
    "  2. An integer $k$ such that $0 \\leq k < N$.\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Flip the sign of the basis state $|x\\rangle$ if any of the bits of $x$ (not considering the $k$-th bit) are $1$ in input register. In other words, the input register with the $k$-th qubit excluded should not be in the all zero state to flip the sign of the input register. The state of the $k$-th qubit does not affect the result.\n",
    "\n",
    "Feel free to explore implementing this operation with or without auxiliary qubits.\n",
    "\n",
    "**Examples:**\n",
    "\n",
    "* If the query register is in the state $|010\\rangle$ and $k=0$, flip the sign of the register.\n",
    "* If the query register is in the state $|010\\rangle$ and $k=1$, do nothing.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Before implementing this oracle, answer the question: are you implementing a marking or a phase oracle?  Click here for the answer!</b></summary>\n",
    "    This is a phase oracle, because we are changing the phase of the input state $|x\\rangle$ based on the value of the function $f(x)$.\n",
    "</details>\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  You can reuse the previously implemented oracles and operations, same as how you would use library operations.\n",
    "  <br/>\n",
    "  You can use <a href=\"https://docs.microsoft.com/en-us/azure/quantum/user-guide/language/expressions/itemaccessexpressions\">array slicing</a> to get parts of the array before and after the $k$-th element.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T33_OrOfBitsExceptKth_Oracle\n",
    "\n",
    "operation OrOfBitsExceptKth_Oracle(x: Qubit[], k: Int) : Unit is Adj + Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part IV: More Oracles!  Implementation and Testing:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Task 4.1</span>: Implement the arbitrary bit pattern oracle\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. $N$ qubits in an arbitrary state $|x\\rangle$ (input/query register).\n",
    "  2. A qubit in an arbitrary state $|y\\rangle$ (target qubit).\n",
    "  3. A boolean array of length $N$ `pattern` representing a basis state; `true` and `false` elements correspond to $|1\\rangle$ and $|0\\rangle$, respectively.\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Flip the state of $|y\\rangle$ if the input register matches the basis state\n",
    "represented by `pattern`.  \n",
    "\n",
    "**Examples:**\n",
    "\n",
    "* If the query register is in the state $|010\\rangle$ and `pattern = [false, true, false]`, flip the state $|y\\rangle$.\n",
    "* If the query register is in the state $|1001\\rangle$ and `pattern = [false, true, true, false]`, do nothing.\n",
    "    \n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Before implementing this oracle, answer the question: are you implementing a marking or a phase oracle?  Click here for the answer!</b></summary>\n",
    "    This is a marking oracle, because we are flipping the state of the target qubit $|y\\rangle$ based on the state of the input $|x\\rangle$.\n",
    "</details>\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  You need to flip the state of $|y\\rangle$ if $|x\\rangle$ matches the given pattern.  You may find the Q# library function <a href=\"https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring\">ControlledOnBitString</a> useful in your implementation.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T41_ArbitraryBitPattern_Oracle\n",
    "\n",
    "operation ArbitraryBitPattern_Oracle (x: Qubit[], y: Qubit, pattern: Bool[]) : Unit is Adj + Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Task 4.2</span>: Implement the arbitrary bit pattern oracle (challenge version)\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. $N$ qubits in an arbitrary state $|x\\rangle$ (input/query register).\n",
    "  2. A boolean array of length $N$ `pattern` representing a basis state; `true` and `false` elements correspond to $|1\\rangle$ and $|0\\rangle$, respectively.\n",
    "\n",
    "**Goal:**\n",
    " \n",
    "Flip the sign of the input state $|x\\rangle$ if the input register matches the basis state\n",
    "represented by `pattern`.  \n",
    "**Implement this oracle without using auxiliary qubits**\n",
    "\n",
    "**Examples:**\n",
    "\n",
    " * If the query register is in the state $|010\\rangle$ and `pattern = [false, true, false]`, flip the sign of the input register.\n",
    " * If the query register is in the state $|1001\\rangle$ and `pattern = [false, true, true, false]`, do nothing.\n",
    "  \n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Before implementing this oracle, answer the question: are you implementing a marking or a phase oracle?  Click here for the answer!</b></summary>\n",
    "    This is a phase oracle, because we are changing the phase of the input state $|x\\rangle$ based on the value of the function $f(x)$.\n",
    "</details>\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Can you transform the state of the input register based on the <code>pattern</code> value so as to have to flip the phase only for the $|1...1\\rangle$ state?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T42_ArbitraryBitPattern_Oracle_Challenge\n",
    "\n",
    "operation ArbitraryBitPattern_Oracle_Challenge(x: Qubit[], pattern: Bool[]) : Unit is Adj + Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Task 4.3</span>: Implement the meeting oracle\n",
    "\n",
    "Suppose that you would like to schedule a meeting with your co-worker Jasmine. \n",
    "You both work five day workweeks, and $|x\\rangle$ and $|jasmine\\rangle$ are 5-bit states that represent your and Jasmine's schedules. \n",
    "The schedules are indicators of a person being busy on that day: a $1$ bit means that person is busy on that day, and $0$ means they're free for a meeting that day. Implement a function that determines if you and Jasmine can schedule a meeting during the week, i.e., whether there is a day when both schedules have a $0$ simultaneously.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. 5 qubits in an arbitrary state $|x\\rangle$ representing your schedule for the week (input/query register).\n",
    "  2. 5 qubits in an arbitrary state $|jasmine\\rangle$ representing Jasmine's schedule for the week (input/query register).\n",
    "  3. A qubit in an arbitrary state $|y\\rangle$ (target qubit).\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Flip the state of $|y\\rangle$ if you and Jasmine are both free on the same day for at least one day during the week.  Recall that a $0$ means that a person is free on that day.\n",
    "\n",
    "**Examples:**\n",
    "\n",
    "* If $|x\\rangle=|10101\\rangle$ and $|jasmine\\rangle=|01010\\rangle$, do nothing (there is no day on which you both are free).\n",
    "* If $|x\\rangle=|10001\\rangle$ and $|jasmine\\rangle=|01010\\rangle$, flip the state $|y\\rangle$ (you are both free on Wednesday).\n",
    "* If $|x\\rangle=|00000\\rangle$ and $|jasmine\\rangle=|00000\\rangle$, flip the state $|y\\rangle$ (you are both free all week).\n",
    "* If $|x\\rangle=|11111\\rangle$ and $|jasmine\\rangle=|11111\\rangle$, do nothing (you are both busy all week).\n",
    "    \n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Before implementing this oracle, answer the question: are you implementing a marking or a phase oracle?  Click here for the answer!</b></summary>\n",
    "    This is a marking oracle, because we are flipping the state of the target qubit $|y\\rangle$ based on the state of the inputs $|x\\rangle$ and $|jasmine\\rangle$. Notice that even though we do not have the typical single-input-register situation that we saw earlier, this is still a marking oracle.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T43_Meeting_Oracle\n",
    "\n",
    "operation Meeting_Oracle(x: Qubit[], jasmine: Qubit[], y: Qubit) : Unit is Adj + Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Demo 4.1</span>: Testing an oracle implementation\n",
    "\n",
    "In this demo we show how you could test an oracle that you've implemented for your own problem. \n",
    "For all of the previous oracles that you've implemented, we've been testing your oracle against a reference solution for that task. \n",
    "However, if you're designing an oracle for a new problem, you do not have a reference solution for it - if you did, there would be no point for you to program the oracle in the first place!\n",
    "\n",
    "A good way to test a quantum oracle of interest is to write a classical oracle that performs the same computation classically, and then compare the effect of your quantum oracle on the basis states with the output of the classical oracle for every input (or a lot of the inputs if you are constrained by runtime) to ensure that they match.\n",
    "\n",
    "Here we will test your implementation from task 4.3 by comparing it to the classical code implementing the same function. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Arrays;\n",
    "open Microsoft.Quantum.Diagnostics;\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "// The classical function to perform the same computation\n",
    "function Meeting_Classical (x: Bool[], jasmine: Bool[]) : Bool {\n",
    "    for i in IndexRange(x) {\n",
    "        if (not x[i]) and (not jasmine[i]) {\n",
    "            // They have a day that they can both meet\n",
    "            return true;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // At least one of them is busy every day of the week\n",
    "    return false;\n",
    "}\n",
    "\n",
    "operation Test_Meeting_Oracle () : Unit {\n",
    "    // There are 2^5 ways to arrange each of the schedules - let's try all of them\n",
    "    for k in 0 .. 2^5 - 1 { \n",
    "        for j in 0 .. 2^5 - 1 {\n",
    "            // Convert your and Jasmine's schedules to bit arrays\n",
    "            let binaryX = IntAsBoolArray(k, 5);\n",
    "            let binaryJasmine = IntAsBoolArray(j, 5);\n",
    "            \n",
    "            // Calculate the function classically\n",
    "            let classicalResult = Meeting_Classical(binaryX, binaryJasmine);\n",
    "                \n",
    "            // create a register of qubits so we can represent\n",
    "            // your schedule, jasmine's schedule, and the output\n",
    "            use (x, jasmine, target) = (Qubit[5], Qubit[5], Qubit());\n",
    "            // Prepare the quantum schedules in basis states matching the binary schedules\n",
    "            ApplyPauliFromBitString(PauliX, true, binaryX, x);\n",
    "            ApplyPauliFromBitString(PauliX, true, binaryJasmine, jasmine);\n",
    "\n",
    "            // Apply the quantum oracle\n",
    "            Meeting_Oracle(x, jasmine, target);\n",
    "\n",
    "            // Check that the result of the quantum algorithm matched that\n",
    "            // of the classical algorithm\n",
    "            AssertQubit(classicalResult ? One | Zero, target);\n",
    "\n",
    "            // Undo the preparation of basis states x and jasmine\n",
    "            ApplyPauliFromBitString(PauliX, true, binaryX, x);\n",
    "            ApplyPauliFromBitString(PauliX, true, binaryJasmine, jasmine);\n",
    "\n",
    "            // Check that the oracle did not change its input states\n",
    "            AssertAllZero(x);\n",
    "            AssertAllZero(jasmine);\n",
    "\n",
    "            Reset(target);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    Message(\"Success!\");\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "%simulate Test_Meeting_Oracle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part V: What's next?\n",
    "\n",
    "Thanks for learning with us!  We hope that you enjoyed the tutorial. If you'd like to learn more about implementing quantum oracles, here are some suggestions:\n",
    "\n",
    "* [Grover's algorithm kata](../../GroversAlgorithm/GroversAlgorithm.ipynb) and [Deutsch-Jozsa algorithm kata](./../DeutschJozsaAlgorithm/DeutschJozsaAlgorithm.ipynb) include simple oracles for you to practice.\n",
    "* [Marking oracles kata](../../MarkingOracles/MarkingOracles.ipynb) includes practice tasks on more advanced oracles.\n",
    "* [Solving SAT problems using Grover's algorithm](../../SolveSATWithGrover/SolveSATWithGrover.ipynb) covers implementing oracles for SAT problems.\n",
    "* [Solving graph coloring problems using Grover's algorithm](../../GraphColoring/GraphColoring.ipynb) covers implementing oracles for graph coloring problem.\n",
    "* [Solving bounded knapsack problems using Grover's algorithm](../../BoundedKnapsack/BoundedKnapsack.ipynb) covers implementing oracles for bounded knapsack problem.\n",
    "\n",
    "If you'd like to learn more about quantum algorithms that rely on quantum oracles:\n",
    "* [Exploring Deutsch-Jozsa algorithm tutorial](https://github.com/microsoft/QuantumKatas/tree/main/tutorials/ExploringDeutschJozsaAlgorithm) introduces the simplest oracle-based algorithm.\n",
    "* [Exploring Grover’s search algorithm tutorial](https://github.com/microsoft/QuantumKatas/tree/main/tutorials/ExploringGroversAlgorithm) introduces another important quantum algorithm which is used as a build block in many other algorithms.\n",
    "* [Microsoft Learn module on using Grover's search to solve graph coloring problems](https://docs.microsoft.com/learn/modules/solve-graph-coloring-problems-grovers-search/) provides a detailed example of building a more complicated oracle to solve the graph coloring problem."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.27"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}