GraphColoring/GraphColoring.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph Coloring\n",
    "\n",
    "The **\"Graph Coloring\"** quantum kata is a series of exercises designed\n",
    "to teach you the basics of using Grover search to solve constraint\n",
    "satisfaction problems, using graph coloring problem as an example.\n",
    "\n",
    "* [This Microsoft Learn module](https://docs.microsoft.com/learn/modules/solve-graph-coloring-problems-grovers-search/) walks you through solving graph coloring problems using Grover's search.\n",
    "* You can read more about graph coloring problems [here](https://en.wikipedia.org/wiki/Graph_coloring).\n",
    "* It is strongly recommended to complete the [Grover's Algorithm kata](./../GroversAlgorithm/GroversAlgorithm.ipynb) before proceeding to this one. You can also refer to its [README.md](./../GroversAlgorithm/README.md) for the list of resources on Grover's algorithm.\n",
    "* [SolveSATWithGrover](./../SolveSATWithGrover/SolveSATWithGrover.ipynb) is another kata covering oracle implementation for solving constraint satisfaction problems.\n",
    "\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "Your goal is to fill in the blank (marked with the `// ...` comments)\n",
    "with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).\n",
    "\n",
    "Within each section, tasks are given in approximate order of increasing difficulty; \n",
    "harder ones are marked with asterisks."
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_InitializeColor \n",
    "\n",
    "operation InitializeColor (C : Int, register : Qubit[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_MeasureColor \n",
    "\n",
    "operation MeasureColor (register : Qubit[]) : Int {\n",
    "    // ...\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_MeasureColoring \n",
    "\n",
    "operation MeasureColoring (K : Int, register : Qubit[]) : Int[] {\n",
    "    // ...\n",
    "    return new Int[0];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_GraphColoring.ipynb#Task-1.5.-N-bit-color-equality-oracle-(no-extra-qubits)).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Vertex coloring problem\n",
    "The vertex graph coloring is a coloring of graph vertices which \n",
    "labels each vertex with one of the given colors so that \n",
    "no two vertices of the same color are connected by an edge."
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_IsVertexColoringValid \n",
    "\n",
    "function IsVertexColoringValid (V : Int, edges: (Int, Int)[], colors: Int[]) : Bool {\n",
    "    // ...\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "timeout"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T23_GroversAlgorithm \n",
    "\n",
    "operation GroversAlgorithm (V : Int, oracle : ((Qubit[], Qubit) => Unit is Adj)) : Int[] {\n",
    "    // ...\n",
    "    return new Int[V];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_GraphColoring.ipynb#Task-2.3.-Using-Grover's-search-to-find-vertex-coloring).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part III. Weak coloring problem\n",
    "Weak graph coloring is a coloring of graph vertices which \n",
    "labels each vertex with one of the given colors so that \n",
    "each vertex is either isolated or is connected by an edge\n",
    "to at least one neighbor of a different color."
   ]
  },
  {
   "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 contains the 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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T31_DoesEdgeContainVertex\n",
    "\n",
    "function DoesEdgeContainVertex (edge: (Int, Int), vertex : Int) : Bool {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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.\n",
    "\n",
    "**Note:**\n",
    "\n",
    "An isolated vertex (a vertex without neighbors) is considered to be weakly colored.\n",
    "\n",
    "**Example:**\n",
    "\n",
    "For vertex $0$, in a graph containing `edges = [(0, 1), (0, 2), (1, 2)]` and  `colors = [0, 1, 0]`, vertex $0$ is weakly colored, since it has color 0 and is connected to vertex 1 which has color 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T32_IsVertexWeaklyColored\n",
    "\n",
    "function IsVertexWeaklyColored (V : Int, edges: (Int, Int)[], colors: Int[], vertex : Int) : Bool {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T33_IsWeakColoringValid\n",
    "\n",
    "function IsWeakColoringValid (V : Int, edges: (Int, Int)[], colors: Int[]) : Bool {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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": "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",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_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 weak coloring for the graph, in a format used in Task 3.3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T36_GroversAlgorithmForWeakColoring\n",
    "\n",
    "operation GroversAlgorithmForWeakColoring (V : Int, oracle : ((Qubit[], Qubit) => Unit is Adj)) : Int[] {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Graph Coloring Workbook](./Workbook_GraphColoring.ipynb#Task-3.6.-Using-Grover's-search-to-find-weak-coloring).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part IV. Triangle-free coloring problem\n",
    "\n",
    "Triangle-free graph coloring is a coloring of graph edges which labels each edge with one of two colors so that no three edges of the same color form a triangle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4.1. Convert the list of graph edges into an adjacency matrix\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$). Each tuple gives the indices of the start and the end vertices of the edge. The vertices are indexed $0$ through $V - 1$.\n",
    "\n",
    "**Output:**  \n",
    "A 2D array of integers representing this graph as an adjacency matrix:  the element [i][j] should be $-1$ if the vertices i and j are not connected with an edge, or store the index of the edge if the vertices i and j are connected with an edge. Elements [i][i] should be $-1$ unless there is an edge connecting vertex i to itself.\n",
    "\n",
    "**Example:**\n",
    "Consider a graph with $V = 3$ and edges = `[(0, 1), (0, 2), (1, 2)]`.\n",
    "The adjacency matrix for it would be:\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "-1 &  0 &  1 \\\\\n",
    " 0 & -1 &  2 \\\\\n",
    " 1 &  2 & -1\n",
    "\\end{bmatrix}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T41_EdgesListAsAdjacencyMatrix\n",
    "\n",
    "function EdgesListAsAdjacencyMatrix (V : Int, edges : (Int, Int)[]) : Int[][] {\n",
    "    // ...\n",
    "    return [];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4.2. Extract a list of triangles from an adjacency matrix\n",
    "\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "   1. The number of vertices in the graph $V (V \\leq 6)$.\n",
    "   \n",
    "   2. An adjacency matrix describing the graph in the format from task 4.1.\n",
    "   \n",
    "**Output:** \n",
    "\n",
    "An array of 3-tuples listing all triangles in the graph, that is, all triplets of vertices connected by edges. Each of the 3-tuples should list the triangle vertices in ascending order, and the 3-tuples in the array should be sorted in ascending order as well.\n",
    "\n",
    "**Example:** \n",
    "\n",
    "Consider the adjacency matrix\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "-1 &  0 &  1 \\\\\n",
    " 0 & -1 &  2 \\\\\n",
    " 1 &  2 & -1\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "The list of triangles for it would be `[(0, 1, 2)]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T42_AdjacencyMatrixAsTrianglesList\n",
    "\n",
    "function AdjacencyMatrixAsTrianglesList (V : Int, adjacencyMatrix : Int[][]) : (Int, Int, Int)[] {\n",
    "    // ...\n",
    "    return [];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4.3. Classical verification of triangle-free coloring\n",
    "**Inputs:**\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)$. Each tuple gives the indices of the start and the end vertices of the edge. The vertices are indexed $0$ through $V - 1$.\n",
    "   \n",
    "   3. An array of $E$ integers, representing the edge coloring of the graph. $i^{th}$ element of the array is the color of the edge number $i$, and it is $0$ or $1$. The colors of edges in this array are given in the same order as the edges in the \"edges\" array.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "`true` if the given coloring is triangle-free (i.e., no triangle of edges connecting 3 vertices has all three edges in the same color), and `false` otherwise.\n",
    "\n",
    "**Example:** \n",
    "\n",
    "Consider a graph with $V = 3$ and edges = `[(0, 1), (0, 2), (1, 2)]`. Some of the valid colorings for it would be `[0, 1, 0]` and `[-1, 5, 18]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T43_IsVertexColoringTriangleFree\n",
    "\n",
    "function IsVertexColoringTriangleFree (V : Int, edges: (Int, Int)[], colors: Int[]) : Bool {\n",
    "    // ...\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4.4. Oracle to check that three colors don't form a triangle (f(x) = 1 if at least two of three input bits are different)\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. a 3-qubit array `inputs`,\n",
    "  \n",
    "  2. a qubit `output`.\n",
    "  \n",
    "**Goal:** \n",
    "\n",
    "Flip the output qubit if and only if at least two of the input qubits are different.\n",
    "\n",
    "**Example:** \n",
    "\n",
    "For the result of applying the operation to state $(|001\\rangle + |110\\rangle + |111\\rangle) \\otimes |0\\rangle$ will be $|001\\rangle \\otimes |1\\rangle + |110\\rangle \\otimes |1\\rangle + |111\\rangle \\otimes |0\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T44_ValidTriangleOracle\n",
    "\n",
    "operation ValidTriangleOracle (inputs : Qubit[], output : Qubit) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4.5. Oracle for verifying triangle-free edge coloring (f(x) = 1 if the graph edge coloring is triangle-free)\n",
    "\n",
    "**Inputs:**\n",
    "  1. The number of vertices in the graph $V (V \\leq 6)$.\n",
    "  \n",
    "  2. An array of $E$ tuples of integers `edges`, representing the edges of the graph ($0 \\leq E \\leq V(V-1)/2$). Each tuple gives the indices of the start and the end vertices of the edge. The vertices are indexed $0$ through $V - 1$. The graph is undirected, so the order of the start and the end vertices in the edge doesn't matter.\n",
    "  \n",
    "  3. An array of $E$ qubits `colorsRegister` that encodes the color assignments of the edges. Each color will be $0$ or $1$ (stored in 1 qubit). The colors of edges in this array are given in the same order as the edges in the `edges` array.\n",
    "  \n",
    "  4. A qubit `target` in an arbitrary state.\n",
    "\n",
    "**Goal:** \n",
    "\n",
    "Implement a marking oracle for function $f(x) = 1$ if the coloring of the edges of the given graph described by this colors assignment is triangle-free, i.e., no triangle of edges connecting 3 vertices has all three edges in the same color.\n",
    "\n",
    "In this task you are not allowed to use quantum gates that use more qubits than the number of edges in the graph,\n",
    "unless there are 3 or less edges in the graph. For example, if the graph has 4 edges, you can only use 4-qubit gates or less.\n",
    "You are guaranteed that in tests that have 4 or more edges in the graph the number of triangles in the graph \n",
    "will be strictly less than the number of edges.\n",
    "\n",
    "**Example:** \n",
    "A graph with 3 vertices and 3 edges `[(0, 1), (1, 2), (2, 0)]` has one triangle.  \n",
    "The result of applying the operation to state $\\frac{1}{\\sqrt{3}} \\big(|001\\rangle + |110\\rangle + |111\\rangle\\big) \\otimes |0\\rangle$ will be $\\frac{1}{\\sqrt{3}} \\big(|001\\rangle \\otimes |1\\rangle + |110\\rangle \\otimes |1\\rangle + |111\\rangle \\otimes |0\\rangle\\big)$.\n",
    "The first two terms describe triangle-free colorings, and the last term describes a coloring where all edges of the triangle have the same color.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Make use of functions and operations you've defined in previous tasks. \n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T45_TriangleFreeColoringOracle\n",
    "\n",
    "operation TriangleFreeColoringOracle (\n",
    "    V : Int, \n",
    "    edges : (Int, Int)[], \n",
    "    colorsRegister : Qubit[], \n",
    "    target : Qubit\n",
    ") : Unit is Adj+Ctl {\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
}