tutorials/ExploringGroversAlgorithm/ExploringGroversAlgorithmTutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exploring Grover's Search Algorithm\n",
    "\n",
    "**Grover's search algorithm** is one of the most famous algorithms in quantum computing. The problem it solves is often referred to as \"searching a database\", but it is more accurate to think of it as \"inverting a function\". The algorithm can have practical value when applied on its own, but it can also be generalized and used as a building block for other algorithms. As such, Grover's algorithm is part of almost every introductory course on quantum computing.\n",
    "\n",
    "This tutorial will:\n",
    "* introduce you to the general problem solved by the Grover's algorithm,\n",
    "* walk you through some of the practical aspects of the algorithm,\n",
    "* and teach you to write code to explore applying them to a task of solving SAT problems using the Q# programming language.\n",
    "\n",
    "In the last section of the tutorial you will continue exploration of Grover's algorithm in a [companion Python notebook](./VisualizingGroversAlgorithm.ipynb) that will \n",
    "use the code we've written to build some interesting graphs and finish the discussion.\n",
    "\n",
    "Grover's algorithm is a massive topic that can hardly be covered in a single tutorial. This tutorial **will not**:\n",
    "* walk you through the Grover's algorithm implementation from scratch (the code you'll write in this tutorial will rely on routines implemented for you) - \n",
    "  if you're looking to learn the low-level implementation details, check out [GroversAlgorithm quantum kata](../../GroversAlgorithm/GroversAlgorithm.ipynb),\n",
    "* teach you to code quantum oracles that implement interesting functions for Grover's algorithm to invert - \n",
    "  if you're looking to learn more about implementing quantum oracles, check out [SolveSATWithGrover](../../SolveSATWithGrover/SolveSATWithGrover.ipynb) \n",
    "  or [GraphColoring](../../GraphColoring/GraphColoring.ipynb) quantum katas which cover writing oracles for solving SAT problems and graph coloring problems, respectively.\n",
    "\n",
    "Let's go!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part I. Problem Statement\n",
    "\n",
    "## The problem\n",
    "\n",
    "**You are given a classical function $f(x): \\{0, 1\\}^N \\to \\{0, 1\\}$. The task is to find an input $x_0$ for which $f(x_0) = 1$.**\n",
    "\n",
    "## Example: SAT problem\n",
    "\n",
    "[Boolean satisfiability problem](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem) (abbreviated as SAT problem) is a problem of finding an assignment of values to boolean variables that satisfies a given boolean formula or determining that such assignment does not exist. \n",
    "\n",
    "The input $x$ is the set of $N$ boolean variables $(x_0, x_1, ..., x_{N-1})$, each of which can be assigned value 0 (false) or 1 (true).\n",
    "\n",
    "The function $f(x)$ is represented as a conjunction (an AND operation, denoted as $\\wedge$) of $M$ clauses.\n",
    "Each clause is a disjunction (an OR operation, denoted as $\\vee$) of **one or several** variables $x_j$ or negated variables $\\neg x_j$:\n",
    "\n",
    "$$f(x) = \\bigwedge_i \\big(\\bigvee_k y_{ik} \\big),\\text{ where }y_{ik} =\\text{ either }x_j\\text{ or }\\neg x_j\\text{ for some }j \\in \\{0, \\dots, N-1\\}$$\n",
    "\n",
    "> As an small example of a SAT problem, consider the following formula: \n",
    "> $$f(x_0, x_1) = x_0 \\wedge (\\neg x_0 \\vee \\neg x_1)$$\n",
    ">\n",
    "> * For the formula to be satisfied (i.e., to have $f(x)$ evaluate to true), both clauses have to evaluate to true.\n",
    "> * The first clause is simply $x_0$, so we know that $x_0$ has to be true. \n",
    "> * The second clause is $\\neg x_0 \\vee \\neg x_1$, which can be true if either of $x_0$ or $x_1$ is false; \n",
    "> since we know that $x_0$ has to be true, $x_1$ has to be false.\n",
    "> * We conclude that the formula can be satisfied using the variables assignment $x = (true, false)$.\n",
    "\n",
    "SAT problem is an excellent match for Grover's search algorithm: it maps naturally to the description of the problem solved by the algorithm, and can be implemented relatively easily using quantum gates. \n",
    "For more details on implementing instances of SAT problem as quantum oracles, see [SolveSATWithGrover quantum kata](https://github.com/Microsoft/QuantumKatas/tree/main/SolveSATWithGrover)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In our Q# code, we will represent an instance of SAT problem as a 2-dimensional array of tuples `problem` in the following format:\n",
    "\n",
    "* $i$-th element of `problem` describes the $i$-th clause of $f(x)$; \n",
    "it is an array of one or more tuples, each of them describing one literal of the clause.\n",
    "* Each tuple is an `(Int, Bool)` pair: the first element is the index $j$ of the variable $x_j$, and the second element is `true` if the variable is included as itself ($x_j$) and `false` if it is included as a negation ($\\neg x_j$)\n",
    "\n",
    "The example of a SAT problem we considered earlier, $f(x_0, x_1) = x_0 \\wedge (\\neg x_0 \\vee \\neg x_1)$, is represented in this format as `[[(0, true)], [(0, false), (1, false)]]`.\n",
    "\n",
    "### <font color=\"blue\">Exercise 1</font>: Try converting array description of a SAT problem into a formula!\n",
    "\n",
    "You can use a Q# function `SATInstanceAsString` to convert the array representation of a SAT instance to a string representation of the formula. Try it out!\n",
    "\n",
    "* Execute the following code to run `SATInstanceAsString` on one example of SAT problem.\n",
    "* Modify line 6 of the code to run `SATInstanceAsString` on other instances of SAT problem.  \n",
    "\n",
    "> * <font color=\"blue\">All exercises in this tutorial are implemented as pairs of code cells: the first code cell defines the code you want to execute, and the second cell executes this code.</font>\n",
    "> * <font color=\"blue\">You can run and re-run each cell using `Ctrl+Enter` (or `⌘+Enter` on a Mac).</font>\n",
    "> * <font color=\"blue\">Any compilation errors will be reported when you run the first cell, any runtime errors - when you run the second cell.</font>\n",
    "> * <font color=\"blue\">You can turn on line numbers in the code cells using `View > Toggle Line Numbers` menu.</font>\n",
    "\n",
    ">  Here are some interesting SAT instances with 3 variables that you might want to use later in the tutorial:\n",
    ">  * $f_1(x) = (x_0) \\wedge (\\neg x_0 \\vee \\neg x_1) \\wedge (x_1 \\vee x_2)$ (1 solution):  \n",
    "    `[[(0, true)], [(0, false), (1, false)], [(1, true), (2, true)]]`\n",
    ">  * $f_2(x) = (x_0 \\vee x_1) \\wedge (\\neg x_0 \\vee \\neg x_1) \\wedge (x_1 \\vee x_2) \\wedge (\\neg x_1 \\vee \\neg x_2)$ (2 solutions):  \n",
    "     `[[(0, true), (1, true)], [(0, false), (1, false)], [(1, true), (2, true)], [(1, false), (2, false)]]`\n",
    ">  * $f_3(x) = (\\neg x_1) \\wedge (x_0 \\vee x_2)$ (3 solutions):  \n",
    "    `[[(1, false)], [(0, true), (2, true)]]`\n",
    ">  * $f_4(x) = (x_0 \\vee x_1) \\wedge (\\neg x_0 \\vee \\neg x_1)$ (4 solutions):  \n",
    "    `[[(0, true), (1, true)], [(0, false), (1, false)]]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// This namespace contains helpful operations for you to use during the tutorial\n",
    "open Quantum.Kata.ExploringGroversAlgorithm;\n",
    "\n",
    "function ConvertSATInstanceToString () : Unit {\n",
    "    // Function \"Message\" prints its string argument to the output\n",
    "    Message(SATInstanceAsString( [[(0, true)], [(0, false), (1, false)]] ));\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate ConvertSATInstanceToString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classical algorithm\n",
    "\n",
    "If we solve this problem classically, how many evaluations of the given function will we need? \n",
    "\n",
    "If we don't know anything about the internal structure of the function, we can not do better than try evaluating the function on different inputs until we either hit one which produces the desired output or try all inputs and conclude that the desired input doesn't exist. This requires $O(2^N)$ function evaluations, since in the worst case scenario we'll need to try all inputs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part II. Grover's Search Algorithm\n",
    "\n",
    "### Inputs\n",
    "\n",
    "You are given the number of bits in the function input $N$ and the quantum oracle - a \"black box\" quantum operation $U_f$ that implements a classical function $f(x)$. \n",
    "The oracle $U_f$ is defined by its effect on the individual inputs (\"basis states\"): if the value of the function on the input register $\\vec{x}$ $f(x) = 1$, the state of the output $y$ is flipped (0 becomes 1 and vice versa). \n",
    "Formally this can be written as follows:\n",
    "\n",
    "$$U_f |\\vec{x} \\rangle |y\\rangle = |\\vec{x} \\rangle |y \\oplus f(x) \\rangle$$\n",
    "\n",
    "The oracle is implemented in a way which allows to perform calculations not only on individual inputs, but also on superpositions of inputs. The details of this implementation are outside of the scope of this tutorial, but this implementation is the key that makes Grover's algorithm possible.\n",
    "\n",
    "### Algorithm summary\n",
    "\n",
    "The high-level outline of the algorithm is very simple:\n",
    "\n",
    "1. Initialize the quantum system to a well-known starting state.\n",
    "2. Apply a fixed sequence of operations called \"Grover iteration\" several times; each iteration includes one call of the oracle \"black box\".\n",
    "3. Perform measurements: they will produce the desired output with high probability.\n",
    "\n",
    "In this tutorial we will use pre-written implementation of the well-known sections of the algorithm (including the actual quantum operations). This will allow us to focus on the more interesting nuances of the algorithm and applying it to solving problems."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=\"blue\">Exercise 2</font>: Run Grover's algorithm to solve a SAT problem\n",
    "\n",
    "Let's start with the most basic implementation of Grover's algorithm and see how it works to solve a problem. \n",
    "We will tweak this code and improve it in the later tasks.\n",
    "\n",
    "* Execute the following code to run Grover's algorithm on one example of SAT problem.\n",
    "* Modify the code to run Grover's algorithm on other instances of SAT problem. \n",
    "  Try instances with varying number of variable assignments that satisfy the formula, including the instances which are not satisfiable, for example, $f(x) = x_0 \\wedge \\neg x_0$. \n",
    "  Does the algorithm always produce correct answer? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "open Quantum.Kata.ExploringGroversAlgorithm;\n",
    "\n",
    "operation RunGroversAlgorithm_SimpleLoop () : Unit {\n",
    "    // Create a data structure describing the SAT instance we want to solve\n",
    "    let problem = [[(0, true)], [(0, false), (1, false)]];\n",
    "    // The number of variables in this formula is 2\n",
    "    let variableCount = 2;\n",
    "    \n",
    "    Message($\"Solving SAT problem {SATInstanceAsString(problem)}...\");\n",
    "    \n",
    "    // We start by defining a quantum oracle for the instance of a SAT problem we want to solve.\n",
    "    // We use a pre-written operation \"CreateOracleForSATInstance\" to do that.\n",
    "    let oracle = CreateOracleForSATInstance(problem);\n",
    "    \n",
    "    // We will discuss choosing the right number of iterations later\n",
    "    let iterationCount = 1;\n",
    "    \n",
    "    // Allocate the qubits for running the algorithm\n",
    "    use register = Qubit[variableCount];\n",
    "    // Run the iterations using a pre-written operation\n",
    "    GroversAlgorithm_Loop(register, oracle, iterationCount);\n",
    "\n",
    "    // Perform measurements to get the variables assignment.\n",
    "    // \"MultiM\" operation measures all qubits and returns an array of measurement results, and\n",
    "    // \"ResultArrayAsBoolArray\" converts it to an array of boolean variables.\n",
    "    let assignment = ResultArrayAsBoolArray(MultiM(register));\n",
    "\n",
    "    // Output the results\n",
    "    Message($\"{VariableAssignmentAsString(assignment)}\");\n",
    "\n",
    "    // Reset the qubits before releasing them, otherwise you'll get a ReleasedQubitsAreNotInZeroState exception\n",
    "    ResetAll(register);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate RunGroversAlgorithm_SimpleLoop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you've tried running the algorithm from part II on different SAT instances, you've probably noticed that for some formulas the algorithm produces incorrect results. \n",
    "This is to be expected: *Grover's algorithm is a probabilistic algorithm*, which means that even in the best case it has a non-zero failure probability. \n",
    "In the next section we will look at how to verify that the answer produced by the algorithm is correct, and how to re-run the algorithm if the first run produced an incorrect answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part III. Verifying the algorithm output\n",
    "\n",
    "There are two ways to verify that the output of the algorithm $x_0$ is correct:\n",
    "\n",
    "1. If you have a classical description of the problem instance you're solving, you can do the verification classically, same as you would do for a classical randomized algorithm. \n",
    "In the case of the SAT problem, you would assign the values produced by the algorithm to the variables in the formula and check whether this assignment satisfies the formula.\n",
    "2. In the general case the algorithm only gets the oracle as an input and doesn't have the information about the classical problem structure. \n",
    "However, all information necessary to verify the output is already contained in the oracle itself!  \n",
    "The effect of the oracle on inputs, encoded as basis states of the qubit register, is defined as \n",
    "$$U_f |\\vec{x} \\rangle |y\\rangle = |\\vec{x} \\rangle |y \\oplus f(x) \\rangle$$\n",
    "This means that if you encode the vector state $\\vec{x_0}$ produced by the algorithm as a basis state of the qubit register, \n",
    "allocate an extra qubit in the $|0\\rangle$ state, and apply the oracle $U_f$ to these qubits, you'll get \n",
    "$$U_f |\\vec{x_0} \\rangle |0\\rangle = |\\vec{x} \\rangle |f(x) \\rangle$$\n",
    "If you measure the extra qubit afterwards, you'll get exactly $f(x)$: if it is 1, the algorithm produced a correct answer, otherwise it did not (but you can re-run the algorithm from scratch again and hopefully get a correct answer on the next attempt!)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=\"blue\">Exercise 3</font>: Verify the output of Grover's algorithm\n",
    "\n",
    "Modify the following code to add output verification to Grover's algorithm.\n",
    "\n",
    "> <font color=\"blue\">When you execute the following cell for the first time, it will produce several compilation errors.  \n",
    "    Your task is to fill in the missing sections of the code (denoted by `...`) following the prompts given in the code comments to fix the compilation errors and to implement the required functionality.  \n",
    "    If you get stuck, scroll down to the next text cell for the complete code for the answer check!</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "invalid_code"
    ]
   },
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "open Quantum.Kata.ExploringGroversAlgorithm;\n",
    "\n",
    "operation RunGroversAlgorithm_OutputVerification () : Unit {\n",
    "    // Use a different SAT instance to get a higher probability of failure\n",
    "    let problem = [[(0, true), (1, true)], [(0, false), (1, false)]];\n",
    "    let variableCount = 2;\n",
    "    \n",
    "    Message($\"Solving SAT problem {SATInstanceAsString(problem)}...\");\n",
    "    \n",
    "    let oracle = CreateOracleForSATInstance(problem);\n",
    "    let iterationCount = 1;\n",
    "    \n",
    "    use register = Qubit[variableCount];\n",
    "    GroversAlgorithm_Loop(register, oracle, iterationCount);\n",
    "    let assignment = ResultArrayAsBoolArray(MultiM(register));\n",
    "    Message($\"{VariableAssignmentAsString(assignment)}\");\n",
    "\n",
    "    // ========================== Check that the answer is correct. ==========================\n",
    "\n",
    "    // Allocate another qubit to keep the result of evaluating the function. \n",
    "    // You can allocate a single qubit with the following syntax in using statement: <variable name> = Qubit()\n",
    "    use ... \n",
    "    // After measuring \"register\" on line 17, the qubits in \"register\" end up \n",
    "    // in the state that encodes the answer produced by the algorithm (decoded in \"assignment\" variable).\n",
    "    // Call oracle with \"register\" as the first parameter (function input x) \n",
    "    // and the newly allocated qubit as the second parameter (function output f(x))\n",
    "    // to evaluate the function on that answer.\n",
    "    ...\n",
    "\n",
    "    // Measure the newly allocated qubit and check if the measurement result is Zero or One;\n",
    "    // One means the algorithm returned correct answer, Zero - incorrect.\n",
    "    // You can measure the qubit and reset it immediately using MResetZ operation, \n",
    "    // and compare the measurement result to the constants Zero or One using \"==\" operator.\n",
    "    if ... {\n",
    "        // Report the correct/incorrect result using Message function.\n",
    "        Message(...);\n",
    "    } else {\n",
    "        Message(...);\n",
    "    }\n",
    "\n",
    "    ResetAll(register);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "invalid_code"
    ]
   },
   "outputs": [],
   "source": [
    "%simulate RunGroversAlgorithm_OutputVerification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "    <summary><b>Click here for the complete answer validation code</b></summary>\n",
    "<code>    use y = Qubit() {\n",
    "        oracle(register, y);\n",
    "        if MResetZ(y) == One {\n",
    "            Message(\"Correct!\");\n",
    "        } else {\n",
    "            Message(\"Incorrect\");\n",
    "        }\n",
    "    }\n",
    "</code>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=\"blue\">Exercise 4</font>: Re-run Grover's algorithm in case of incorrect answer\n",
    "\n",
    "Modify the following code to re-run Grover's algorithm if the first run produced an incorrect answer. This logic is implemented by Q#'s `repeat ... until` loop.\n",
    "\n",
    "> <font color=\"blue\">You can copy the code from the previous exercise to use as loop body.  \n",
    "    If you get stuck, scroll down to the next text cell for the complete code for rerunning the algorithm!</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "invalid_code"
    ]
   },
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "open Quantum.Kata.ExploringGroversAlgorithm;\n",
    "\n",
    "operation RunGroversAlgorithm_RerunIncorrectAnswer () : Unit {\n",
    "    // Use a different SAT instance to get a higher probability of failure\n",
    "    let problem = [[(0, true), (1, true)], [(0, false), (1, false)]];\n",
    "    let variableCount = 2;\n",
    "    \n",
    "    Message($\"Solving SAT problem {SATInstanceAsString(problem)}...\");\n",
    "    \n",
    "    let oracle = CreateOracleForSATInstance(problem);\n",
    "    let iterationCount = 1;\n",
    "    \n",
    "    use register = Qubit[variableCount];\n",
    "\n",
    "    // ======== Use repeat-until-success loop to re-run algorithm in case of a failure ========\n",
    "\n",
    "    // Define a mutable variable to serve as the exit condition.\n",
    "    mutable isAnswerCorrect = false;\n",
    "    // Define a mutable variable to store the answer once you've found a correct one.\n",
    "    mutable finalAnswer = [false, false];\n",
    "\n",
    "    repeat {\n",
    "        // Loop body: run Grover's search using \"GroversAlgorithm_Loop\",\n",
    "        // measure the answer and check whether it is correct.\n",
    "        // Use \"set <variable name> = <value>;\" to update mutable variables.\n",
    "        ...\n",
    "\n",
    "        // Remember to reset the qubits in \"register\" at the end of each iteration!\n",
    "    } until (isAnswerCorrect);\n",
    "\n",
    "    // Output the final answer.\n",
    "    Message($\"{finalAnswer}\");\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "invalid_code"
    ]
   },
   "outputs": [],
   "source": [
    "%simulate RunGroversAlgorithm_RerunIncorrectAnswer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "    <summary><b>Click here for the complete code for rerunning the algorithm</b></summary>\n",
    "<code>mutable isAnswerCorrect = false;\n",
    "mutable finalAnswer = [false, false];\n",
    "repeat {\n",
    "    GroversAlgorithm_Loop(register, oracle, iterationCount);\n",
    "    set finalAnswer = ResultArrayAsBoolArray(MultiM(register));\n",
    "    Message($\"Verifying answer {finalAnswer}\");\n",
    "    use y = Qubit() {\n",
    "        oracle(register, y);\n",
    "        if (MResetZ(y) == One) {\n",
    "            set isAnswerCorrect = true;\n",
    "        }\n",
    "    }\n",
    "    ResetAll(register);\n",
    "} until (isAnswerCorrect);\n",
    "</code>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part IV. Exploring the success probability of the algorithm\n",
    "\n",
    "If you've tried running the algorithm from part II on different SAT instances, you've probably noticed that \n",
    "different instances of the problem have different probability of the algorithm successfully finding a solution to them.\n",
    "This probability depends on several parameters:\n",
    "\n",
    "* the size of the search space (i.e., the number of variables in the formula $N$) \n",
    "* the number of solutions to the problem (i.e., the number of variable assignments that satisfy the formula $M$),\n",
    "* and the number of Grover iterations the algorithm performs.\n",
    "\n",
    "In this section we will take a look at how varying these parameters affects the success probability of Grover's search algorithm, \n",
    "and at how to tune the algorithm to increase the success probability. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=\"blue\">Exercise 5</font>: Calculate the success probability of Grover's algorithm\n",
    "\n",
    "Modify the following code to run Grover's algorithm multiple times, check whether the algorithm found correct answer each time, and aggregate the results into success probability of the algorithm.\n",
    "\n",
    "> <font color=\"blue\">You can copy the code from the exercises 3-4 to use as loop body.</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "invalid_code"
    ]
   },
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "open Quantum.Kata.ExploringGroversAlgorithm;\n",
    "\n",
    "operation RunGroversAlgorithm_CalculateSuccessProbability () : Unit {\n",
    "    // Here are the SAT instances with different success probabilities mentioned earlier to get you started\n",
    "    // 1 solution: [[(0, true)], [(0, false), (1, false)], [(1, true), (2, true)]]\n",
    "    // 2 solutions: [[(0, true), (1, true)], [(0, false), (1, false)], [(1, true), (2, true)], [(1, false), (2, false)]]\n",
    "    // 3 solutions: [[(1, false)], [(0, true), (2, true)]]\n",
    "    // 4 solutions: [[(0, true), (1, true)], [(0, false), (1, false)]]\n",
    "    let variableCount = 3;\n",
    "    let problem = [[(1, false)], [(0, true), (2, true)]];\n",
    "    \n",
    "    Message($\"Solving SAT problem {SATInstanceAsString(problem)}...\");\n",
    "    \n",
    "    let oracle = CreateOracleForSATInstance(problem);\n",
    "    let iterationCount = 1;\n",
    "    \n",
    "    use register = Qubit[variableCount];\n",
    "\n",
    "    // ======== Use for loop to run algorithm a fixed number of times ========\n",
    "\n",
    "    // Define a mutable variable to store the number of times the algorithm succeeded.\n",
    "    mutable successCount = 0;\n",
    "\n",
    "    for i in 1 .. 100 {\n",
    "        // Loop body: run Grover's search using \"GroversAlgorithm_Loop\",\n",
    "        // measure the answer and check whether it is correct.\n",
    "        // Use \"set successCount += 1;\" to increment the success counter.\n",
    "        ...\n",
    "\n",
    "        // Remember to reset the qubits in \"register\" at the end of each iteration!\n",
    "    }\n",
    "\n",
    "    // Output the success probability of the algorithm.\n",
    "    Message($\"The algorithm succeeds with {successCount}% probability.\");\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "invalid_code"
    ]
   },
   "outputs": [],
   "source": [
    "%simulate RunGroversAlgorithm_CalculateSuccessProbability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "    <summary><b>Click here for the complete code for probability calculation</b></summary>\n",
    "<code>mutable successCount = 0;\n",
    "for (i in 1 .. 100) {\n",
    "    GroversAlgorithm_Loop(register, oracle, iterationCount);\n",
    "    let answer = ResultArrayAsBoolArray(MultiM(register));\n",
    "    use y = Qubit() {\n",
    "        oracle(register, y);\n",
    "        if MResetZ(y) == One {\n",
    "            set successCount += 1;\n",
    "        }\n",
    "    }\n",
    "    ResetAll(register);\n",
    "}\n",
    "Message($\"The algorithm succeeds with {successCount}% probability.\");\n",
    "</code>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=\"blue\">Demo</font>: Exploring the success probability of Grover's algorithm\n",
    "\n",
    "At this stage you have completed the quantum code necessary to run Grover's algorithm and estimate its success probability. \n",
    "To continue our exploration of Grover's algorithm, we'll switch to a [companion Python notebook](./VisualizingGroversAlgorithm.ipynb) that shows \n",
    "how to invoke Q# code from Python host, uses the code we've written to build some interesting graphs and finishes the discussion of the algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part V. What's Next?\n",
    "\n",
    "We hope you've enjoyed this tutorial and learned a lot from it! If you're looking to learn more about quantum computing and Q#, here are some suggestions:\n",
    "\n",
    "* The [Quantum Katas](https://github.com/microsoft/QuantumKatas/) are sets of programming exercises on quantum computing that can be solved using Q#. \n",
    "  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, [GroversAlgorithm kata](https://github.com/microsoft/QuantumKatas/tree/main/GroversAlgorithm) \n",
    "  offers you exercises on implementing simple quantum oracles and a step-by-step implementation of Grover search algorithm \n",
    "  (all the internals that were hidden under the hood of `GroversAlgorithm_Loop` operation in this tutorial!).\n",
    "* [SolveSATWithGrover kata](https://github.com/microsoft/QuantumKatas/tree/main/SolveSATWithGrover) teaches you how to implement quantum oracles for SAT problems, \n",
    "  starting with the simple building blocks like implementing AND and OR operations in a quantum way.\n",
    "* [GraphColoring kata](https://github.com/microsoft/QuantumKatas/tree/main/GraphColoring) is another interesting kata that teaches you how to implement quantum oracles for graph coloring problems.\n",
    "* [BoundedKnapsack kata](https://github.com/microsoft/QuantumKatas/tree/main/BoundedKnapsack) handles more complicated problem, the knapsack problem, showing how to use Grover's search for optimization problems."
   ]
  }
 ],
 "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
}