DeutschJozsaAlgorithm/DeutschJozsaAlgorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Deutsch-Jozsa algorithm\n",
    "\n",
    "The **Deutsch–Jozsa algorithm** quantum kata is a series of exercises designed\n",
    "to get you familiar with programming in Q#.\n",
    "\n",
    "It covers the following topics:\n",
    "* writing oracles (quantum operations which implement certain classical functions),\n",
    "* Bernstein-Vazirani algorithm for recovering the parameters of a scalar product function,\n",
    "* Deutsch-Jozsa algorithm for recognizing a function as constant or balanced, and\n",
    "* writing tests in Q#.\n",
    "\n",
    "You can read more about the quantum oracles, Deutsch and Deutsch-Jozsa algorithms in the [ExploringDeutschJozsaAlgorithm tutorial](../tutorials/ExploringDeutschJozsaAlgorithm/DeutschJozsaAlgorithmTutorial_P1.ipynb).\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "Your goal is to fill in the blanks (marked with `// ...` comments)\n",
    "with some Q# code that solves the task. To verify your answer, run the cell with Ctrl+Enter (⌘+Enter on macOS)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Oracles\n",
    "\n",
    "In this section you will implement oracles defined by classical functions using the following rules:\n",
    " - a function $f\\left(x_0, ..., x_{N-1}\\right)$ with N bits of input $x = \\left(x_0, ..., x_{N-1}\\right)$ and 1 bit of output $y$\n",
    "   defines an oracle which acts on N input qubits and 1 output qubit.\n",
    " - the oracle effect on qubits in computational basis states is defined as follows:\n",
    "   $|x\\rangle |y\\rangle \\to |x\\rangle |y \\oplus f(x)\\rangle$   ($\\oplus$ is addition modulo 2).\n",
    " - the oracle effect on qubits in superposition is defined following the linearity of quantum operations.\n",
    " - the oracle must act properly on qubits in all possible input states.\n",
    " \n",
    "You can read more about quantum oracles in [Q# documentation](https://docs.microsoft.com/azure/quantum/concepts-oracles)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. $f(x) = 0$\n",
    "\n",
    "**Inputs:** \n",
    "1. N qubits in an arbitrary state $|x\\rangle$ (input register)\n",
    "2. a qubit in an arbitrary state $|y\\rangle$ (output qubit)\n",
    "\n",
    "\n",
    "**Goal:**  transform state $|x, y\\rangle$ into state $|x, y \\oplus f(x)\\rangle$ ($\\oplus$ is addition modulo 2)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_Oracle_Zero \n",
    "\n",
    "operation Oracle_Zero (x : Qubit[], y : Qubit) : Unit {\n",
    "    // Since f(x) = 0 for all values of x, |y ⊕ f(x)⟩ = |y⟩.\n",
    "    // This means that the operation doesn't need to do any transformation to the inputs.\n",
    "    \n",
    "    // Run the cell (using Ctrl/⌘ + Enter) to see that the test passes.\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. $f(x) = 1$\n",
    "\n",
    "**Inputs:** \n",
    "1. N qubits in an arbitrary state $|x\\rangle$ (input register)\n",
    "2. a qubit in an arbitrary state $|y\\rangle$ (output qubit)\n",
    "\n",
    "\n",
    "**Goal:**  transform state $|x, y\\rangle$ into state $|x, y \\oplus f(x)\\rangle$ ($\\oplus$ is addition modulo 2).\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Since $f(x) = 1$ for all values of x, $|y \\oplus f(x)\\rangle = |y \\oplus 1\\rangle = |NOT y\\rangle$.\n",
    "  This means that the operation needs to flip qubit y (i.e. transform $|0\\rangle$ to $|1\\rangle$ and vice versa).\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_Oracle_One \n",
    "\n",
    "operation Oracle_One (x : Qubit[], y : Qubit) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.3. $f(x) = x_k$ (the value of k-th qubit)\n",
    "\n",
    "**Inputs:** \n",
    "1. N qubits in an arbitrary state $|x\\rangle$ (input register)\n",
    "2. a qubit in an arbitrary state $|y\\rangle$ (output qubit)\n",
    "3. 0-based index of the qubit from input register ($0 \\le k < N$)\n",
    "\n",
    "**Goal:**  transform state $|x, y\\rangle$ into state $|x, y \\oplus x_k\\rangle$ ($\\oplus$ is addition modulo 2)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_Oracle_Kth_Qubit \n",
    "\n",
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation Oracle_Kth_Qubit (x : Qubit[], y : Qubit, k : Int) : Unit {\n",
    "    // The following line enforces the constraints on the value of k that you are given.\n",
    "    // You don't need to modify it. Feel free to remove it, this won't cause your code to fail.\n",
    "    EqualityFactB(0 <= k and k < Length(x), true, \"k should be between 0 and N-1, inclusive\");\n",
    "\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.4. f(x) = 1 if x has odd number of 1s, and 0 otherwise\n",
    "\n",
    "**Inputs:** \n",
    "1. N qubits in an arbitrary state $|x\\rangle$ (input register)\n",
    "2. a qubit in an arbitrary state $|y\\rangle$ (output qubit)\n",
    "\n",
    "\n",
    "**Goal:**  transform state $|x, y\\rangle$ into state $|x, y \\oplus f(x)\\rangle$ ($\\oplus$ is addition modulo 2).\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  $f(x)$ can be represented as $x_0 \\oplus x_1 \\oplus ... \\oplus x_{N-1}$.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_Oracle_OddNumberOfOnes\n",
    "\n",
    "operation Oracle_OddNumberOfOnes (x : Qubit[], y : Qubit) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.5. $f(x) = \\bigoplus\\limits_{i=0}^{N-1} r_i x_i$ for a given bit vector r (scalar product function)\n",
    "\n",
    "**Inputs:** \n",
    "1. N qubits in an arbitrary state $|x\\rangle$ (input register)\n",
    "2. a qubit in an arbitrary state $|y\\rangle$ (output qubit)\n",
    "3. a bit vector of length N represented as an `Int[]`.\n",
    "   You are guaranteed that the qubit array and the bit vector have the same length.\n",
    "\n",
    "**Goal:**  transform state $|x, y\\rangle$ into state $|x, y \\oplus f(x)\\rangle$ ($\\oplus$ is addition modulo 2)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T15_Oracle_ProductFunction\n",
    "\n",
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation Oracle_ProductFunction (x : Qubit[], y : Qubit, r : Int[]) : Unit {\n",
    "    // The following line enforces the constraint on the input arrays.\n",
    "    // You don't need to modify it. Feel free to remove it, this won't cause your code to fail.\n",
    "    EqualityFactI(Length(x), Length(r), \"Arrays should have the same length\");\n",
    "\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.6. $f(x) = \\bigoplus\\limits_{i=0}^{N-1} \\left(r_i x_i + (1 - r_i) (1 - x_i) \\right)$ for a given bit vector r (scalar product function)\n",
    "\n",
    "**Inputs:** \n",
    "1. N qubits in an arbitrary state $|x\\rangle$ (input register)\n",
    "2. a qubit in an arbitrary state $|y\\rangle$ (output qubit)\n",
    "3. a bit vector of length N represented as an `Int[]`.\n",
    "   You are guaranteed that the qubit array and the bit vector have the same length.\n",
    "\n",
    "**Goal:**  transform state $|x, y\\rangle$ into state $|x, y \\oplus f(x)\\rangle$ ($\\oplus$ is addition modulo 2).\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Since each addition is done modulo 2, you can evaluate the effect of each term independently$.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T16_Oracle_ProductWithNegationFunction\n",
    "\n",
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation Oracle_ProductWithNegationFunction (x : Qubit[], y : Qubit, r : Int[]) : Unit {\n",
    "    // The following line enforces the constraint on the input arrays.\n",
    "    // You don't need to modify it. Feel free to remove it, this won't cause your code to fail.\n",
    "    EqualityFactI(Length(x), Length(r), \"Arrays should have the same length\");\n",
    "\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.7. $f(x) = \\bigoplus\\limits_{i=0}^{N-1} x_i + $ (1 if prefix of x is equal to the given bit vector, and 0 otherwise) modulo 2\n",
    "\n",
    "**Inputs:** \n",
    "1. N qubits in an arbitrary state $|x\\rangle$ (input register)\n",
    "2. a qubit in an arbitrary state $|y\\rangle$ (output qubit)\n",
    "3. a bit vector of length $K$ represented as an `Int[]` ($1 \\le K \\le N$).\n",
    "\n",
    "**Goal:**  transform state $|x, y\\rangle$ into state $|x, y \\oplus f(x)\\rangle$ ($\\oplus$ is addition modulo 2).\n",
    "\n",
    "> A prefix of length K of a state $|x\\rangle = |x_0, ..., x_{N-1}\\rangle$ is the state of its first K qubits $|x_0, ..., x_{K-1}\\rangle$. For example, a prefix of length 2 of a state $|0110\\rangle$ is 01.\n",
    "\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  The first term is the same as in task 1.4. To implement the second term, you can use `Controlled` functor which allows to perform multicontrolled gates (gates with multiple control qubits).\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T17_Oracle_HammingWithPrefix\n",
    "\n",
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation Oracle_HammingWithPrefix (x : Qubit[], y : Qubit, prefix : Int[]) : Unit {\n",
    "    // The following line enforces the constraint on the input arrays.\n",
    "    // You don't need to modify it. Feel free to remove it, this won't cause your code to fail.\n",
    "    let K = Length(prefix);\n",
    "    EqualityFactB(1 <= K and K <= Length(x), true, \"K should be between 1 and N, inclusive\");\n",
    "\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.8. f(x) = 1 if x has two or three bits (out of three) set to 1, and 0 otherwise (majority function)\n",
    "\n",
    "**Inputs:** \n",
    "1. 3 qubits in an arbitrary state $|x\\rangle$ (input register)\n",
    "2. a qubit in an arbitrary state $|y\\rangle$ (output qubit)\n",
    "\n",
    "\n",
    "**Goal:**  transform state $|x, y\\rangle$ into state $|x, y \\oplus f(x)\\rangle$ ($\\oplus$ is addition modulo 2).\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Represent $f(x)$ in terms of AND and $\\oplus$ operations.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T18_Oracle_MajorityFunction\n",
    "\n",
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation Oracle_MajorityFunction (x : Qubit[], y : Qubit) : Unit {\n",
    "    // The following line enforces the constraint on the input array.\n",
    "    // You don't need to modify it. Feel free to remove it, this won't cause your code to fail.\n",
    "    EqualityFactI(3, Length(x), \"x should have exactly 3 qubits\");\n",
    "\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Deutsch-Jozsa Algorithm\n",
    "\n",
    "In this section you will implement the Deutsch-Jozsa algorithm and run it on the oracles you've defined in part I to observe the results. \n",
    "\n",
    "This algorithm solves the following problem. You are given a quantum oracle which implements a classical function $f(x): \\{0, 1\\}^N \\to \\{0, 1\\}$. You are guaranteed that the function $f$ is either constant (has the same value for all inputs) or balanced (has value 0 for half of the inputs and 1 for the other half of the inputs). The goal of the algorithm is to figure out whether the function is constant or balanced in just one oracle call.\n",
    " \n",
    "* You can read more about the Deutsch-Jozsa algorithms and explore its finer points in the [ExploringDeutschJozsaAlgorithm tutorial](../tutorials/ExploringDeutschJozsaAlgorithm/DeutschJozsaAlgorithmTutorial.ipynb).\n",
    "* You can read more about the Deutsch-Jozsa algorithm in [Wikipedia](https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm).\n",
    "* [Lecture 5: A simple searching algorithm; the Deutsch-Jozsa algorithm](https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.05.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. State preparation for Deutsch-Jozsa algorithm\n",
    "\n",
    "**Inputs:**\n",
    "1. N qubits in $|0\\rangle$ state (query register)\n",
    "2. a qubit in $|0\\rangle$ state (answer register)\n",
    "\n",
    "**Goal:**\n",
    "1. Prepare an equal superposition of all basis vectors from $|0...0\\rangle$ to $|1...1\\rangle$ on query register\n",
    "   (i.e., state $\\frac{1}{\\sqrt{2^N}}\\big(|0...0\\rangle + ... + |1...1\\rangle\\big)$ ).\n",
    "2. Prepare $|-\\rangle = \\frac{1}{\\sqrt2} (|0\\rangle - |1\\rangle)$ state on answer register.    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_DJ_StatePrep\n",
    "\n",
    "operation DJ_StatePrep (query : Qubit[], answer : Qubit) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Deutsch-Jozsa Algorithm\n",
    "\n",
    "**Inputs:** \n",
    "1. the number of qubits $N$ in the input register for the function f\n",
    "2. a quantum operation which implements the oracle $|x, y\\rangle \\to |x, y \\oplus f(x)\\rangle$, where x is an $N$-qubit input register, y is a 1-qubit answer register, and f is a Boolean function\n",
    "\n",
    "\n",
    "**Output:**  `true` if the function f is constant, or `false` if the function f is balanced."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_DJ_Algorithm\n",
    "\n",
    "operation DJ_Algorithm (N : Int, oracle : ((Qubit[], 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",
    "    // ...\n",
    "\n",
    "    // Allocate an array of N qubits for the input register x and one qubit for the answer register y.\n",
    "    use (x, y) = (Qubit[N], 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",
    "    // Each qubit of the input register has to be in the |+⟩ state.\n",
    "    // ...\n",
    "\n",
    "    // The answer register has to be in the |-⟩ state.\n",
    "    // ...\n",
    "\n",
    "    // Apply the oracle to the input register and the answer register.\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",
    "    // If any of the measurement results is One, the function implemented by the oracle is balanced.\n",
    "    // ...\n",
    "\n",
    "    // Before releasing the qubits make sure they are all in the |0⟩ state.\n",
    "    // ...\n",
    "    \n",
    "    // Return the answer.\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. Running Deutsch-Jozsa Algorithm\n",
    "\n",
    "**Goal**: Use your implementation of Deutsch-Jozsa algorithm from task 2.1 to test each of the oracles you've implemented in part I for being constant or balanced.\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_DeutschJozsa_Algorithm` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_DeutschJozsa_Algorithm`).\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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation Run_DeutschJozsa_Algorithm () : String {\n",
    "    // You can use the Fact function to check that the return value of DJ_Algorithm operation matches the expected value.\n",
    "    // Uncomment the next line to test the algorithm on the oracle for f(x) = 0.\n",
    "    // Fact(DJ_Algorithm(4, Oracle_Zero), \"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_DeutschJozsa_Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part III. Bernstein–Vazirani Algorithm\n",
    "\n",
    "In this section you will implement the Bernstein-Vazirani algorithm and run it on the oracles you've defined in part I to observe the results. \n",
    "\n",
    "This algorithm solves the following problem. You are given a quantum oracle which implements a classical function $f(x): \\{0, 1\\}^N \\to \\{0, 1\\}$. You are guaranteed that the function $f$ can be represented as a scalar product, i.e., there exists a bit vector $r = (r_0, ..., r_{N-1})$ such that $f(x) = \\bigoplus \\limits_{i=0}^{N-1} x_i r_i$. The goal of the algorithm is to reconstruct the bit vector $r$ in just one oracle call.\n",
    " \n",
    "You can read more about the Bernstein-Vazirani algorithm in [\"Quantum Algorithm Implementations for Beginners\"](https://arxiv.org/abs/1804.03719), section III."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.1. Bernstein-Vazirani Algorithm\n",
    "\n",
    "**Inputs:** \n",
    "1. the number of qubits $N$ in the input register for the function f\n",
    "2. a quantum operation which implements the oracle $|x, y\\rangle \\to |x, y \\oplus f(x)\\rangle$, where x is an $N$-qubit input register, y is a 1-qubit answer register, and f is a Boolean function\n",
    "\n",
    "\n",
    "**Output:**  The bit vector $r$ reconstructed from the oracle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T31_BV_Algorithm\n",
    "\n",
    "operation BV_Algorithm (N : Int, oracle : ((Qubit[], Qubit) => Unit)) : Int[] {\n",
    "    // The algorithm is very similar to Deutsch-Jozsa algorithm; try to implement it without hints.\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.2. Running Bernstein-Vazirani Algorithm\n",
    "\n",
    "**Goal**: Use your implementation of Bernstein-Vazirani algorithm from task 3.1 to reconstruct the hidden vector $r$ for the oracles you've implemented in part I.\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_BernsteinVazirani_Algorithm` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_BernsteinVazirani_Algorithm`).\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.\n",
    "\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Not all oracles from part I can be represented as scalar product functions. The most generic oracle you can use in this task is Oracle_ProductFunction from task 1.5; Oracle_Zero, Oracle_Kth_Qubit and Oracle_OddNumberOfOnes are special cases of this oracle.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation Run_BernsteinVazirani_Algorithm () : String {\n",
    "    // Now use the library function AllEqualityFactI in Microsoft.Quantum.Diagnostics to verify the results of the algorithm.\n",
    "    // Uncomment the following lines to test the algorithm on the oracle for f(x) = 0.\n",
    "    // AllEqualityFactI(BV_Algorithm(3, Oracle_Zero), [0, 0, 0], \"Incorrect result for f(x) = 0\");\n",
    "    \n",
    "    // Run the algorithm on 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_BernsteinVazirani_Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part IV. Come up with your own algorithm!\n",
    "\n",
    "In this section you will come up with your own algorithm to solve a problem similar to the one described in part III. \n",
    "\n",
    "The problem is formulated as follows. You are given a quantum oracle which implements a classical function $f(x): \\{0, 1\\}^N \\to \\{0, 1\\}$. You are guaranteed that there exists a bit vector $r = (r_0, ..., r_{N-1})$ such that the function $f$ can be represented as follows: $f(x) = \\bigoplus \\limits_{i=0}^{N-1} \\left( x_i r_i + (1 - x_i)(1 - r_i) \\right)$. You have to reconstruct the bit vector $r$ in just one oracle call.\n",
    "\n",
    "> Note that you have implemented the oracle for this function in task 1.6."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4. Noname Algorithm\n",
    "\n",
    "**Inputs:** \n",
    "1. the number of qubits $N$ in the input register for the function f\n",
    "2. a quantum operation which implements the oracle $|x, y\\rangle \\to |x, y \\oplus f(x)\\rangle$, where x is an $N$-qubit input register, y is a 1-qubit answer register, and f is a Boolean function\n",
    "\n",
    "**Output:**  Any bit vector $r$ that would generate the same oracle as the one you are given.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  For each oracle there are multiple bit vectors that generate it; it is sufficient to find any one of them.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T41_Noname_Algorithm\n",
    "\n",
    "operation Noname_Algorithm (N : Int, oracle : ((Qubit[], Qubit) => Unit)) : Int[] {\n",
    "    // The algorithm is very similar to Bernstein-Vazirani algorithm; try to implement it without hints.\n",
    "    // ...\n",
    "}"
   ]
  }
 ],
 "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
}