907 строки
31 KiB
Plaintext
907 строки
31 KiB
Plaintext
{
|
|
"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 [];\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 [0, size = 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
|
|
}
|