GraphColoring/Workbook_GraphColoring.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph Coloring Kata Workbook\n",
    "\n",
    "**What is this workbook?**\n",
    "A workbook is a collection of problems, accompanied by solutions to them. \n",
    "The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required. \n",
    "\n",
    "Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n",
    "\n",
    "This workbook describes the solutions to the problems offered in the [Graph Coloring kata](./GraphColoring.ipynb). \n",
    "Since the tasks are offered as programming problems, the explanations also cover some elements of Q# that might be non-obvious for a first-time user."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Colors Representation and Manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. Initialize register to a color\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. An integer $C$ ($0 \\leq C \\leq 2^{N} - 1$).\n",
    "\n",
    "  2. An array of $N$ qubits in the $|0...0\\rangle$ state.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Prepare the array in the basis state which represents the binary notation of $C$. \n",
    "Use little-endian encoding (i.e., the least significant bit should be stored in the first qubit).\n",
    "\n",
    "**Example:** For $N = 2$ and $C = 2$ the state should be $|01\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We first need to convert the integer C to its binary representation. In Q#, we can use the [IntAsBoolArray](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.convert.intasboolarray) function to convert the input integer to its equivalent binary representation in little-endian `binaryC`.\n",
    "\n",
    "Next we need to use `binaryC` as a bit mask: whenever `binaryC[i]` is 1 (or `true` if stored as an array of boolean values), we need to flip the qubit by applying an X gate. We can do this using a `for` loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_InitializeColor \n",
    "\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation InitializeColor (C : Int, register : Qubit[]) : Unit is Adj {\n",
    "    let N = Length(register);\n",
    "    // Convert C to an array of bits in little endian format\n",
    "    let binaryC = IntAsBoolArray(C, N);\n",
    "    // Value \"true\" corresponds to bit 1 and requires applying an X gate\n",
    "    for i in 0 .. N - 1 {\n",
    "        if (binaryC[i]) {\n",
    "            X(register[i]);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, we can use a helpful library operation [ApplyPauliFromBitString](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.applypaulifrombitstring). \n",
    "It takes as input a Pauli operator $P \\in \\{I,X,Y,Z\\}$, a boolean value, a boolean array and a qubit register and applies the Pauli operator to the register using the boolean array as a bit mask: the operator is applied to the qubits that correspond to array elements equal to the given boolean value.\n",
    "\n",
    "We can think of `ApplyPauliFromBitString` as the following unitary transformation:\n",
    "\n",
    "$$P^{b_0} \\otimes P^{b_1} \\otimes ... \\otimes P^{b_{n-1}}$$\n",
    "\n",
    "Here $P^0=I, P^1 =P$ (the given Pauli operator), and $b_i \\in \\{0,1\\}$ are the elements of the given boolean array if the given boolean value is `true` or their negations if it is `false`. \n",
    "\n",
    "In our case, `ApplyPauliFromBitString(PauliX, true, binaryC, register)` represents the following transformation of `register`:\n",
    "\n",
    "$$|\\psi\\rangle \\xrightarrow{} X^{c_0} \\otimes X^{c_1} \\otimes ... \\otimes X^{c_{n-1}}|\\psi\\rangle$$\n",
    "\n",
    "where $c_0c_1...c_{n-1}$ is the binary representation of $C$.\n",
    "\n",
    "When the input qubit register is in the state $|0...0\\rangle$, `ApplyPauliFromBitString` operation will convert it into a basis state representing the boolean array, i.e., little-endian binary encoding of $C$:\n",
    "\n",
    "$$|0...0\\rangle \\xrightarrow{} X^{c_0} \\otimes X^{c_1} \\otimes ... \\otimes X^{c_{n-1}}|0...0\\rangle = |c_0c_1...c_{n-1}\\rangle = |C\\rangle$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_InitializeColor \n",
    "\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation InitializeColor (C : Int, register : Qubit[]) : Unit is Adj {\n",
    "    let N = Length(register);\n",
    "    // Convert C to an array of bits in little endian format\n",
    "    let binaryC = IntAsBoolArray(C, N);\n",
    "    // Value \"true\" corresponds to bit 1 and requires applying an X gate\n",
    "    ApplyPauliFromBitString(PauliX, true, binaryC, register);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.1 of the Graph Coloring kata.](./GraphColoring.ipynb#Task-1.1.-Initialize-register-to-a-color)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Read color from a register\n",
    "\n",
    "**Input:** An array of $N$ qubits which are guaranteed to be in one of the $2^{N}$ basis states.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "An $N$-bit integer that represents this basis state, in little-endian encoding. \n",
    "The operation should not change the state of the qubits.\n",
    "\n",
    "**Example:** For $N = 2$ and the qubits in the state $|01\\rangle$ return 2 (and keep the qubits in $|01\\rangle$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Since we are guaranteed that `register` is in one of the $2^N$ basis states, \n",
    "simply measuring it (without resetting the qubits to the $|0\\rangle$ state after the measurement) will not destroy any superposition and leave the state of the qubits unchanged, while giving us the necessary information. \n",
    "\n",
    "We can use the [MultiM](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.measurement.multim) operation to measure each of the qubits and store the result in an array of the type `Result[]`. \n",
    "\n",
    "We now need to convert these bits into an integer. We can do this directly using the [ResultArrayAsInt](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.convert.resultarrayasint) function which converts an array of `Result` values representing a little-endian encoding of an integer into the equivalent integer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_MeasureColor \n",
    "\n",
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation MeasureColor (register : Qubit[]) : Int {\n",
    "    let measurements = MultiM(register);\n",
    "    return ResultArrayAsInt(measurements);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.2 of the Graph Coloring kata.](./GraphColoring.ipynb#Task-1.2.-Read-color-from-a-register)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.3. Read coloring from a register\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. The number of elements in the coloring $K$.\n",
    "\n",
    "  2. An array of $K * N$ qubits which are guaranteed to be in one of the $2^{KN}$ basis states.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "An array of $K$ $N$-bit integers that represent this basis state. \n",
    "$i$-th integer of the array is stored in qubits with indices $i * N$, $i * N + 1$, ..., $i * N + N - 1$ in little-endian format. \n",
    "The operation should not change the state of the qubits.\n",
    "\n",
    "**Example:** \n",
    "For $N = 2$, $K = 2$ and the qubits in the state $|0110\\rangle$ return `[2, 1]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "This can be considered as $K$-copies version of the previous task. In that task we read the color from a register of size $N$.\n",
    "Here we have to return $K$ integers representing the $K$ colors from each of the $N$-bit registers. \n",
    "\n",
    "We are given $K$ and hence we can find out $N$ by dividing the `Length` of the register by $K$. \n",
    "\n",
    "Next we need to divide $KN$-qubit register into $K$ $N$-qubit registers. \n",
    "We use the Q# function [Chunks](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.arrays.chunks) which partitions the given array into chunks of the given length.\n",
    "\n",
    "Finally, we use the [ForEach](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.arrays.foreach) operation to apply the `MeasureColor` operation from task 2.2 to each element of `colorPartitions` and assemble the results of each application into the resulting array `coloring`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_MeasureColoring \n",
    "\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation MeasureColoring (K : Int, register : Qubit[]) : Int[] {\n",
    "    let N = Length(register) / K;\n",
    "    let colorPartitions = Chunks(N, register);\n",
    "    let coloring = ForEach(MeasureColor, colorPartitions);\n",
    "    return coloring;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.3 of the Graph Coloring kata.](./GraphColoring.ipynb#Task-1.3.-Read-coloring-from-a-register)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.4. 2-bit color equality oracle\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. An array of 2 qubits in an arbitrary state $|c_{0}\\rangle$ representing the first color.\n",
    "\n",
    "  2. An array of 2 qubits in an arbitrary state $|c_{1}\\rangle$ representing the second color.\n",
    "\n",
    "  3. A qubit in an arbitrary state $|y\\rangle$ (target qubit).\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Transform state $|c_{0}\\rangle|c_{1}\\rangle|y\\rangle$ into state $|c_{0}\\rangle|c_{1}\\rangle|y \\oplus f(c_{0},c_{1})\\rangle$ ($\\oplus$ is addition modulo 2), \n",
    "where $f(x) = 1$ if $c_{0}$ and $c_{1}$ are in the same state, and 0 otherwise. \n",
    "Leave the query register in the same state it started in.\n",
    "\n",
    "In this task you are allowed to allocate extra qubits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We are given that $f(c_0,c_1)=1$ if and only if $c_0=c_1$. Let's express this using XOR (or $\\oplus$) - a binary operation defined as follows:\n",
    "\n",
    "$$c_0 = c_1 \\Leftrightarrow c_0 \\oplus c_1 =0 $$\n",
    "\n",
    "We can express $f(c_0,c_1)$ as $1$ if $c_0\\oplus c_1=0$ and $0$ otherwise. The advantage of this representation over the previous one is that we can calculate the XOR of two bits using the $\\textrm{CNOT}$ operator. \n",
    "To do this, we allocate an extra qubit in the $|0\\rangle$ state and do two $\\textrm{CNOT}$s with each of the input bits as the control and the extra qubit as target. Since the effect of $\\textrm{CNOT}$ is $|x\\rangle|y\\rangle \\rightarrow |x\\rangle|y \\oplus x\\rangle$, the effect of such a pair of $\\textrm{CNOT}$s will be \n",
    "\n",
    "$$|b_0b_1\\rangle|0\\rangle \\rightarrow |b_0b_1\\rangle|(0 \\oplus b_0) \\oplus b_1\\rangle = |b_0b_1\\rangle|b_0 \\oplus b_1\\rangle$$\n",
    "\n",
    "Thus, we can compute bitwise XOR of bit strings $c_0$ and $c_1$ by allocating two auxiliary qubits $|a\\rangle$ in the initial state $|00\\rangle$ and applying the XOR computation procedure described above to pairs of corresponding bits in $c_0$ and $c_1$.\n",
    "\n",
    "We now need to flip the target qubit $|y\\rangle$ only if the auxiliary qubits $|a\\rangle$ are in the $|00\\rangle$ state. \n",
    "This can be done by using zero-controlled $X$ gate, i.e., `ControlledOnInt(0, X)`.\n",
    "Finally, we need to uncompute the bitwise XOR to ensure the auxiliary qubits are again in the $|00\\rangle$ state before releasing them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_ColorEqualityOracle_2bit \n",
    "\n",
    "operation ColorEqualityOracle_2bit (c0 : Qubit[], c1 : Qubit[], target : Qubit) : Unit is Adj+Ctl {\n",
    "    use a = Qubit[2];\n",
    "    within {\n",
    "        // Compute bitwise XOR of c0 and c1 and store it in a\n",
    "        CNOT(c0[0],a[0]);\n",
    "        CNOT(c0[1],a[1]);\n",
    "        CNOT(c1[0],a[0]);\n",
    "        CNOT(c1[1],a[1]);\n",
    "    } apply {\n",
    "        // If all XORs are 0, c0 = c1, and our function is 1\n",
    "        (ControlledOnInt(0, X))(a, target);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.4 of the Graph Coloring kata.](./GraphColoring.ipynb#Task-1.4.-2-bit-color-equality-oracle)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.5. N-bit color equality oracle (no extra qubits)\n",
    "\n",
    "This task is the same as task 1.4, but in this task you are NOT allowed to allocate extra qubits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Since this task is the generalized $N$-bit version of the previous task, we can approach it in a similar manner: compute the bitwise XOR of $N$-bit registers $c_0$ and $c_1$, and flip the target qubit if the XOR is $0$. \n",
    "However, this time we are not allowed to allocate extra qubits and thus must compute (and uncompute) XOR in-place.\n",
    "\n",
    "We can do this by storing $c_1 \\oplus c_0$ in $c_1$ itself: this is exactly the effect of the $\\textrm{CNOT}$ gate!\n",
    "We'll use $N$ $\\textrm{CNOT}$ gates, with each of the qubits of $c_0$ acting as the control and the respective qubits of $c_1$ acting as the target.\n",
    "The remaining procedure is exactly the same as the solution to task 1.4."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T15_ColorEqualityOracle_Nbit \n",
    "\n",
    "operation ColorEqualityOracle_Nbit (c0 : Qubit[], c1 : Qubit[], target : Qubit) : Unit is Adj+Ctl {\n",
    "    within {\n",
    "        // Compute bitwise XOR of c0 and c1 in place (storing it in c1)\n",
    "        for i in 0 .. Length(c0) - 1 {\n",
    "            CNOT(c0[i], c1[i]);\n",
    "        }\n",
    "    } apply {\n",
    "        // If all XORs are 0, c0 = c1, and our function is 1\n",
    "        (ControlledOnInt(0, X))(c1, target);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.5 of the Graph Coloring kata.](./GraphColoring.ipynb#Task-1.5.-N-bit-color-equality-oracle-(no-extra-qubits))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Vertex coloring problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. Classical verification of vertex coloring\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. The number of vertices in the graph $V$ ($V \\leq 6$).\n",
    "\n",
    "  2. An array of $E$ tuples of integers, representing the edges of the graph ($E \\leq 12$).  \n",
    "Each tuple gives the indices of the start and the end vertices of the edge.  \n",
    "The vertices are indexed $0$ through $V - 1$.\n",
    "\n",
    "  3. An array of $V$ integers, representing the vertex coloring of the graph. \n",
    "$i$-th element of the array is the color of the vertex number $i$.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "True if the given vertex coloring is valid (i.e., no pair of vertices connected by an edge have the same color), and false otherwise.\n",
    "\n",
    "**Example:** \n",
    "\n",
    "Graph 0 -- 1 -- 2 would have $V = 3$ and `edges = [(0, 1), (1, 2)]`.  \n",
    "Some of the valid colorings for it would be `[0, 1, 0]` and `[-1, 5, 18]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "A graph coloring valid when the nodes connected by every edge have a different color. This means that we have to check every edge, see if the nodes have the same color, and if it is the case, return that the graph coloring is invalid. If every edge passed the test, we can safely say the graph coloring is valid.\n",
    "\n",
    "Since the color of vertex $n$  is the $n$-th element of the `colors` array, we simply loop through every edge, which is a pair of vertices, and compare corresponding colors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_IsVertexColoringValid \n",
    "\n",
    "function IsVertexColoringValid (V : Int, edges: (Int, Int)[], colors: Int[]) : Bool {\n",
    "    // Loop through every edge\n",
    "    for (v0, v1) in edges {\n",
    "        // Compare the colors of vertices\n",
    "        if (colors[v0] == colors[v1]){\n",
    "            // A return statement stops the execution of the function\n",
    "            return false;\n",
    "        }\n",
    "    }\n",
    "    // If the code reaches this point, every edge was correct\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.1 of the Graph Coloring kata.](./GraphColoring.ipynb#Task-2.1.-Classical-verification-of-vertex-coloring)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Oracle for verifying vertex coloring\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. The number of vertices in the graph $V$ ($V \\leq 6$).\n",
    "\n",
    "  2. An array of $E$ tuples of integers, representing the edges of the graph (E $\\leq$ 12).  \n",
    "Each tuple gives the indices of the start and the end vertices of the edge.  \n",
    "The vertices are indexed $0$ through $V - 1$.\n",
    "\n",
    "  3. An array of $2V$ qubits `colorsRegister` that encodes the color assignments.\n",
    "\n",
    "  4. A qubit in an arbitrary state $|y\\rangle$ (target qubit).\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Transform state $|x, y\\rangle$ into state $|x, y \\oplus f(x)\\rangle$  ($\\oplus$ is addition modulo 2), \n",
    "where $f(x) = 1$ if the given vertex coloring is valid, and 0 otherwise. \n",
    "Leave the query register in the same state it started in.\n",
    "\n",
    "Each color in `colorsRegister` is represented as a 2-bit integer in little-endian format. \n",
    "See task 1.3 for a more detailed description of color assignments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The oracle will rely on the `ColorEqualityOracle_Nbit` operation from task 1.5. \n",
    "We will allocate an array of qubits, of the same size as the number of edges, that will be flipped if the vertices connected by the corresponding edge have the same color. \n",
    "This can easily be done with the operation defined in task 1.5. We will then check if the array is still in state $|0...0\\rangle$; if it is, the coloring is valid.\n",
    "\n",
    "Since the coloring is provided as an array of qubits, with 2 qubits per vertex (2 qubits = 4 basis states = 4 colors), we have to take the correct chunks of the coloring. We can deduce that the coloring of vertex $n$ is encoded in qubits in positions $2*n$ and $2*n+1$.\n",
    "\n",
    "Also, do not forget to uncompute to leave the qubits clean.\n",
    "\n",
    "> In Q#, a sub-array of array elements between indices $a$ and $b$, inclusive, is written as `array[a..b]` (see [array slicing documentation](https://docs.microsoft.com/azure/quantum/user-guide/language/expressions/itemaccessexpressions)).\n",
    ">\n",
    "> The uncomputing of the temporarily allocated qubits can be done using the `within ... apply ...` structure (see [conjugations documentation](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/conjugations))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_VertexColoringOracle \n",
    "\n",
    "operation VertexColoringOracle (V : Int, \n",
    "                                edges : (Int, Int)[], \n",
    "                                colorsRegister : Qubit[], \n",
    "                                target : Qubit) : Unit is Adj+Ctl {\n",
    "    // Store the number of edges\n",
    "    let edgesNumber = Length(edges);\n",
    "    // Allocate the array of qubits storing the conflicts of the coloring \n",
    "    use conflicts = Qubit[edgesNumber];\n",
    "    within {\n",
    "        // Iterate over every edge\n",
    "        for i in 0 .. edgesNumber - 1 {\n",
    "            // Deconstruct the edge tuple into two separate vertex indices\n",
    "            let (v0, v1) = edges[i];\n",
    "            // Use the operation from task 1.5 to track conflicts\n",
    "            ColorEqualityOracle_Nbit(colorsRegister[2*v0 .. 2*v0+1], \n",
    "                                     colorsRegister[2*v1 .. 2*v1+1], conflicts[i]);\n",
    "        }\n",
    "    } apply {\n",
    "        // If all the edges are colored properly, conflicts should be in state |0...0⟩\n",
    "        (ControlledOnInt(0, X))(conflicts, target);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.2 of the Graph Coloring kata.](./GraphColoring.ipynb#Task-2.2.-Oracle-for-verifying-vertex-coloring)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. Using Grover's search to find vertex coloring\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. The number of vertices in the graph $V$ ($V \\leq 6$).\n",
    "\n",
    "  2. A marking oracle which implements vertex coloring verification, as implemented in task 2.2.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "A valid vertex coloring for the graph, in a format used in task 2.1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "First we have to implement the generic Grover's algorithm. However, learning the implementation details is not the goal of this kata, so we will assume that you are already familiar with it; if not, please refer to the [Grover's Algorithm kata](./../GroversAlgorithm/GroversAlgorithm.ipynb). \n",
    "\n",
    "The first code cell implements the phase kickback trick to turn a marking oracle into a phase oracle. The second one is the actual implementation of Grover's algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation OracleConverter (markingOracle : ((Qubit[], Qubit) => Unit is Adj), register : Qubit[]) : Unit is Adj {\n",
    "    use target = Qubit();\n",
    "    within {\n",
    "        // Put the target qubit in the |-⟩ state\n",
    "        X(target);\n",
    "        H(target);\n",
    "    } apply {\n",
    "        // Apply the marking oracle\n",
    "        markingOracle(register, target);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation GroverAlgorithmLoop (markingOracle : ((Qubit[], Qubit) => Unit is Adj), register : Qubit[], iterations : Int) : Unit is Adj {\n",
    "    // Convert the marking oracle in a phase oracle\n",
    "    let phaseOracle = OracleConverter(markingOracle, _);\n",
    "    // Prepare an equal superposition of all basis states\n",
    "    ApplyToEachA(H, register);\n",
    "    // Apply Grover iterations\n",
    "    for _ in 1..iterations {\n",
    "        // Apply phase oracle\n",
    "        phaseOracle(register);\n",
    "        // Apply \"reflection about the mean\"\n",
    "        within {\n",
    "            ApplyToEachA(H, register);\n",
    "            ApplyToEachA(X, register);\n",
    "        } apply {\n",
    "            (Controlled Z)(Most(register), Tail(register));\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main part of this task is running Grover's algorithm to find a solution. \n",
    "\n",
    "To do this, we'll need to take some extra steps to use the generic implementation. Here is the flow:\n",
    "- Allocate an array of qubits to store graph coloring with 2 qubits per vertex and one more qubit to use when we verify that the solution we found is indeed correct.\n",
    "- Try running the algorithm with different numbers of Grover's iterations, starting with 1 iteration and increasing the number each time we don't find a solution. \n",
    "We will use two mutable variables for this, `iterations` to store iteration count and `correct` to indicate whether we found a correct solution, and the [repeat-until-success loop](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/conditionalloops#repeat-statement).\n",
    "- In the body of the loop we'll do the following steps:\n",
    "    - Use Grover's algorithm loop implemented in a previous code cell with the current number of iterations.\n",
    "    - Measure the qubit array to the result of Grover's algorithm. We can do that using the [`MultiM` operation](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.measurement.multim).\n",
    "    - Check whether the result is a valid graph coloring by applying the marking oracle to the qubit array that stores the coloring (remember that after the measurement the state of these qubits collapsed to the basis state that corresponds to the measurement results) and the extra qubit. \n",
    "    - Measure the extra qubit in the Pauli Z basis and reset it using the [`MResetZ` operation](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.measurement.mresetz):\n",
    "        - If the measurement result is `One`, the algorithm result is indeed a solution to the problem we're solving; we need to set `correct` variable to `true` and to decode the result into a graph coloring using the `MeasureColoring` operation from task 1.3.\n",
    "        - If the measurement result is `Zero`, the algorithm result is not a solution to our problem, and we do nothing.\n",
    "    - Reset the array that stored the coloring to prepare it for the next iteration using the [`ResetAll` operation](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.resetall).\n",
    "- We stop the loop if we found the solution or if we are running too many iterations (in this case we throw an exception to indicate that we didn't find a solution)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "tags": [
     "timeout"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T23_GroversAlgorithm \n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation GroversAlgorithm (V : Int, oracle : ((Qubit[], Qubit) => Unit is Adj)) : Int[] {\n",
    "    mutable coloring = new Int[V];\n",
    "    use (register, output) = (Qubit[2 * V], Qubit());\n",
    "    mutable correct = false;\n",
    "    mutable iterations = 1;\n",
    "    repeat {\n",
    "        Message($\"Trying iteration {iterations}\");\n",
    "        GroverAlgorithmLoop(oracle, register, iterations);\n",
    "        let temp = MultiM(register);\n",
    "        oracle(register, output);\n",
    "        if (MResetZ(output) == One) {\n",
    "            set correct = true;\n",
    "            set coloring = MeasureColoring(V, register);\n",
    "        }\n",
    "        ResetAll(register);\n",
    "    }\n",
    "    until (correct or iterations > 10)\n",
    "    fixup {\n",
    "        set iterations += 1;\n",
    "    }\n",
    "    if (not correct) {\n",
    "        fail \"No valid coloring was found\";\n",
    "    }\n",
    "    return coloring;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.3 of the Graph Coloring kata.](./GraphColoring.ipynb#Task-2.3.-Using-Grover's-search-to-find-vertex-coloring)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part III. Weak coloring problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.1. Determine if an edge contains the vertex\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "   1. An edge denoted by a tuple of integers.\n",
    "      Each tuple gives the indices of the start and the end vertices of the edge.\n",
    "   2. An integer denoting the vertex of the graph.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "True if the edge starts with vertex provided, and false otherwise.\n",
    "\n",
    "**Examples:** \n",
    "- edge $(0,1)$ contains vertex $0$, so return true;\n",
    "- edge $(0,1)$ contains vertex $1$, so return true;\n",
    "- edge $(2,3)$ does not contain vertex $1$, so return false."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "We first need to deconstruct the edge tuple, to extract the $start$ and $end$ vertices.\n",
    "\n",
    "Next, we return true, if the unpacked $start$ vertex or $end$ vertex is same as the given $vertex$; otherwise return false."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T31_DoesEdgeContainVertex\n",
    "\n",
    "function DoesEdgeContainVertex (edge: (Int, Int), vertex : Int) : Bool {\n",
    "    // Deconstruct the edge tuple\n",
    "    let (start, end) = edge;\n",
    "    // Check if start vertex or end vertex is same as the given vertex\n",
    "    return start == vertex or end == vertex;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3.1 of the Graph Coloring kata.](./GraphColoring.ipynb#Task-3.1.-Determine-if-an-edge-contains-the-vertex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.2. Determine if a vertex is weakly colored\n",
    "**Inputs:** \n",
    "\n",
    "  1. The number of vertices in the graph $V$ ($V \\leq 6$).\n",
    "\n",
    "  2. An array of $E$ tuples of integers, representing the edges of the graph ($E \\leq 12$).  \n",
    "Each tuple gives the indices of the start and the end vertices of the edge.  \n",
    "The vertices are indexed $0$ through $V - 1$.\n",
    "\n",
    "  3. An array of $V$ integers, representing the vertex coloring of the graph. \n",
    "$i$-th element of the array is the color of the vertex number $i$.\n",
    "\n",
    "  4. A vertex in the graph, indexed $0$ through $V - 1$.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "True if the vertex is weakly colored, (i.e., it is connected to at least one neighboring vertex of different color),\n",
    "and false otherwise."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "We need to consider two cases :\n",
    "1. The vertex is isolated (has no neighbors): return true.\n",
    "2. The vertex has at least one neighbor:\n",
    "   we have to check every neighbor one by one and see if any neighbor has different color; if it is the case, return true. If every neighbor has the same color, we can safely say the graph coloring is invalid for this vertex, and return false.\n",
    "\n",
    "To get the edges that include the given vertex, we can use the [Filtered](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.arrays.filtered) function from the [Microsoft.Quantum.Arrays](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.arrays) namespace, with the function we've defined in the previous task as the predicate.\n",
    "If the resulting array has length 0, the vertex has no neighbors, and we return false.\n",
    "Otherwise, we iterate over the edges that connect to this vertex and and compare the colors of their start and end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T32_IsVertexWeaklyColored\n",
    "\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "function IsVertexWeaklyColored(V : Int, edges: (Int, Int)[], colors: Int[], vertex : Int) : Bool {\n",
    "    let predicate = DoesEdgeContainVertex(_, vertex);\n",
    "    let connectingEdges = Filtered(predicate, edges);\n",
    "\n",
    "    // Case 1 : A vertex has no neighbors.\n",
    "    if Length(connectingEdges)==0 {\n",
    "        return true;\n",
    "    }\n",
    "\n",
    "    // Case 2 : A vertex has at least one neighbor.\n",
    "    for (start, end) in connectingEdges {\n",
    "        if colors[start] != colors[end] {\n",
    "            return true;\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // All neighbors have same color.\n",
    "    return false;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3.2. of the Graph Coloring kata.](./GraphColoring.ipynb#Task-3.2.-Determine-if-a-vertex-is-weakly-colored)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.3. Classical verification of weak coloring\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. The number of vertices in the graph $V$ ($V \\leq 6$).\n",
    "\n",
    "  2. An array of $E$ tuples of integers, representing the edges of the graph ($E \\leq 12$).  \n",
    "Each tuple gives the indices of the start and the end vertices of the edge.  \n",
    "The vertices are indexed $0$ through $V - 1$.\n",
    "\n",
    "  3. An array of $V$ integers, representing the vertex coloring of the graph. \n",
    "$i$-th element of the array is the color of the vertex number $i$.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "True if the given weak coloring is valid (i.e., every vertex is isolated or is connected to at least one neighboring vertex of different color), and false otherwise.\n",
    "\n",
    "**Example:** \n",
    "\n",
    "Consider a graph with $V = 3$ and `edges = [(0, 1), (0, 2), (1, 2)]`.  \n",
    "Some of the valid colorings for it would be `[0, 1, 0]` and `[-1, 5, 18]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "A weakly coloring is valid when all the vertices all weakly colored. This means that we have to check every vertex, see if any vertex is not weakly colored, and if it is the case, return that the weak coloring is invalid. If every vertex passed the test, we can safely say the weak coloring is valid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T33_IsWeakColoringValid\n",
    "\n",
    "function IsWeakColoringValid (V : Int, edges: (Int, Int)[], colors: Int[]) : Bool {\n",
    "    for vertex in 0 .. V - 1 {\n",
    "        if IsVertexWeaklyColored(V, edges, colors, vertex) == false {\n",
    "            return false;\n",
    "        }\n",
    "    }\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3.3. of the Graph Coloring kata.](./GraphColoring.ipynb#Task-3.3.-Classical-verification-of-weak-coloring)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.4. Oracle for verifying if a vertex is weakly colored\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. The number of vertices in the graph $V$ ($V \\leq 6$).\n",
    "\n",
    "  2. An array of $E$ tuples of integers, representing the edges of the graph (E $\\leq$ 12).  \n",
    "Each tuple gives the indices of the start and the end vertices of the edge.  \n",
    "The vertices are indexed $0$ through $V - 1$.\n",
    "\n",
    "  3. An array of $2V$ qubits `colorsRegister` that encodes the color assignments.\n",
    "\n",
    "  4. A qubit in an arbitrary state $|y\\rangle$ (target qubit).\n",
    "  \n",
    "  5. A vertex in the graph, indexed $0$ through $V - 1$\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Transform state $|x, y\\rangle$ into state $|x, y \\oplus f(x)\\rangle$  ($\\oplus$ is addition modulo 2), \n",
    "where $f(x) = 1$ if the given weak coloring is valid, and 0 otherwise. \n",
    "Leave the query register in the same state it started in.\n",
    "\n",
    "Each color in `colorsRegister` is represented as a 2-bit integer in little-endian format. \n",
    "See Task 1.3 for a more detailed description of color assignments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We'll start by getting the edges that include the given vertex, using the [Filtered](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.arrays.filtered) function from the [Microsoft.Quantum.Arrays](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.arrays) namespace like we did in Task 3.2.\n",
    "\n",
    "We will allocate an array of qubits, one qubit per neighbor of the given vertex, that will be flipped if the neighbor has the same color as that of the given vertex. \n",
    "This can easily be done with the operation `ColorEqualityOracle_Nbit` defined in Task 1.5. \n",
    "\n",
    "If the coloring is valid, at least one of the neighbors should have a different color, so the array should be in  any state but $|1...1\\rangle$. To implement this, we flip the target qubit unconditionally using the X gate, and then we flip it again only if qubits are in state $|1...1\\rangle$. (If this sounds complicated, we recommend that you go through the [Oracles tutorial](../tutorials/Oracles/Oracles.ipynb).)\n",
    "\n",
    "Since the coloring is provided as an array of qubits, with 2 qubits per vertex color, we have to take the correct chunks of the coloring. We've seen in previous tasks that the coloring of vertex $n$ is encoded in qubits in positions $2n$ and $2n+1$.\n",
    "Remember that in Q#, a sub-array of array elements between indices $a$ and $b$, inclusive, is written as `array[a..b]` (see [array slicing documentation](https://docs.microsoft.com/azure/quantum/user-guide/language/expressions/itemaccessexpressions)).\n",
    "\n",
    "Also, do not forget to uncompute to leave the temporarily allocated qubits clean before releasing them at the end of the operation.\n",
    "The uncomputing of the temporarily allocated qubits can be done using the `within ... apply ...` structure (see [conjugations documentation](https://docs.microsoft.com/azure/quantum/user-guide/language/statements/conjugations)).\n",
    "\n",
    "> Note that you need to execute solutions for tasks 1.5 and 3.1 for the code below to work, since it uses callables `ColorEqualityOracle_Nbit` and `DoesEdgeContainVertex` defined in them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T34_WeaklyColoredVertexOracle\n",
    "\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation WeaklyColoredVertexOracle(V : Int, edges: (Int, Int)[], colorsRegister : Qubit[], target : Qubit, vertex : Int) : Unit is Adj+Ctl {\n",
    "    // Filter out edges not connected to this vertex.\n",
    "    let predicate = DoesEdgeContainVertex(_, vertex);\n",
    "    let connectingEdges = Filtered(predicate, edges);\n",
    "\n",
    "    let N = Length(connectingEdges);\n",
    "    use conflictQubits = Qubit[N];\n",
    "\n",
    "    within {\n",
    "        // Mark all neighbors which are of the SAME color.\n",
    "        for ((start, end), conflictQubit) in Zipped(connectingEdges, conflictQubits) {\n",
    "            ColorEqualityOracle_Nbit(colorsRegister[start * 2 .. start * 2 + 1],\n",
    "                                     colorsRegister[end * 2 .. end * 2 + 1], \n",
    "                                     conflictQubit);\n",
    "        }\n",
    "    } apply {\n",
    "        // If any neighbor has a different color (i.e., at least one qubit is zero), flip target.\n",
    "        // In other words, don't flip only for |1..1⟩.\n",
    "        // (Remember that for N = 0, isolated vertex is ok, so target needs to be flipped as well.)\n",
    "        X(target);\n",
    "        if N != 0 {\n",
    "            // Flip for |1..1⟩.\n",
    "            Controlled X(conflictQubits, target);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3.4. of the Graph Coloring kata.](./GraphColoring.ipynb#Task-3.4.-Oracle-for-verifying-if-a-vertex-is-weakly-colored)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.5. Oracle for verifying weak coloring\n",
    "    \n",
    "**Inputs:**\n",
    "\n",
    "  1. The number of vertices in the graph $V$ ($V \\leq 6$).\n",
    "\n",
    "  2. An array of $E$ tuples of integers, representing the edges of the graph (E $\\leq$ 12).  \n",
    "Each tuple gives the indices of the start and the end vertices of the edge.  \n",
    "The vertices are indexed $0$ through $V - 1$.\n",
    "\n",
    "  3. An array of $2V$ qubits `colorsRegister` that encodes the color assignments.\n",
    "\n",
    "  4. A qubit in an arbitrary state $|y\\rangle$ (target qubit).\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "Transform state $|x, y\\rangle$ into state $|x, y \\oplus f(x)\\rangle$  ($\\oplus$ is addition modulo 2), \n",
    "where $f(x) = 1$ if the given weak coloring is valid, and 0 otherwise. \n",
    "Leave the query register in the same state it started in.\n",
    "\n",
    "Each color in `colorsRegister` is represented as a 2-bit integer in little-endian format. \n",
    "See Task 1.3 for a more detailed description of color assignments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We will allocate an array of qubits, one per vertex, that will be flipped if the corresponding vertex is weakly colored.\n",
    "This can easily be done with the `WeaklyColoredVertexOracle` operation defined in Task 3.4. We will then check if the array is in state $|1...1\\rangle$; if it is, the coloring is valid.\n",
    "\n",
    "As usual, remember to uncompute to return the temporarily allocated qubits to the $|0\\rangle$ state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T35_WeakColoringOracle\n",
    "\n",
    "operation WeakColoringOracle (\n",
    "    V : Int,\n",
    "    edges : (Int, Int)[],\n",
    "    colorsRegister : Qubit[],\n",
    "    target : Qubit\n",
    ") : Unit is Adj+Ctl {\n",
    "    use verticesQubits = Qubit[V];\n",
    "    within {\n",
    "        // Validate that each individual vertex is weakly colored.\n",
    "        for v in 0 .. V - 1 {\n",
    "            WeaklyColoredVertexOracle(V, edges, colorsRegister, verticesQubits[v], v);\n",
    "        }\n",
    "    } apply {\n",
    "        // If all vertices are weakly colored (all qubits are in |1⟩ state), weak coloring is valid.\n",
    "        Controlled X(verticesQubits, target);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3.5. of the Graph Coloring kata.](./GraphColoring.ipynb#Task-3.5.-Oracle-for-verifying-weak-coloring)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.6. Using Grover's search to find weak coloring\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. The number of vertices in the graph $V$ ($V \\leq 6$).\n",
    "\n",
    "  2. A marking oracle which implements weak coloring verification, as implemented in Task 3.5.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "A valid vertex coloring for the graph, in a format used in Task 3.3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "Since the oracle is the main component of Grover's search algorithm, and you are given it as a parameter, you can safely reuse the [solution of Task 2.3](#Task-2.3.-Using-Grover's-search-to-find-vertex-coloring) in this task as well!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3.6. of the Graph Coloring kata.](./GraphColoring.ipynb#Task-3.6.-Using-Grover's-search-to-find-weak-coloring)"
   ]
  }
 ],
 "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
}