The "Graph Coloring" quantum kata is a series of exercises designed to teach you the basics of using Grover search to solve constraint satisfaction problems, using graph coloring problem as an example.
Each task is wrapped in one operation preceded by the description of the task.
Your goal is to fill in the blank (marked with the // ...
comments)
with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).
Within each section, tasks are given in approximate order of increasing difficulty; harder ones are marked with asterisks.
Inputs:
An integer $C$ ($0 \leq C \leq 2^{N} - 1$).
An array of $N$ qubits in the $|0...0\rangle$ state.
Goal:
Prepare the array in the basis state which represents the binary notation of $C$. Use little-endian encoding (i.e., the least significant bit should be stored in the first qubit).
Example: For $N = 2$ and $C = 2$ the state should be $|01\rangle$.
%kata T11_InitializeColor
operation InitializeColor (C : Int, register : Qubit[]) : Unit is Adj {
// ...
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Input: An array of $N$ qubits which are guaranteed to be in one of the $2^{N}$ basis states.
Output:
An $N$-bit integer that represents this basis state, in little-endian encoding. The operation should not change the state of the qubits.
Example: For $N = 2$ and the qubits in the state $|01\rangle$ return 2 (and keep the qubits in $|01\rangle$).
%kata T12_MeasureColor
operation MeasureColor (register : Qubit[]) : Int {
// ...
return -1;
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Inputs:
The number of elements in the coloring $K$.
An array of $K * N$ qubits which are guaranteed to be in one of the $2^{KN}$ basis states.
Output:
An array of $K$ $N$-bit integers that represent this basis state. $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. The operation should not change the state of the qubits.
Example:
For $N = 2$, $K = 2$ and the qubits in the state $|0110\rangle$ return [2, 1]
.
%kata T13_MeasureColoring
operation MeasureColoring (K : Int, register : Qubit[]) : Int[] {
// ...
return [];
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Inputs:
An array of 2 qubits in an arbitrary state $|c_{0}\rangle$ representing the first color.
An array of 2 qubits in an arbitrary state $|c_{1}\rangle$ representing the second color.
A qubit in an arbitrary state $|y\rangle$ (target qubit).
Goal:
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), where $f(x) = 1$ if $c_{0}$ and $c_{1}$ are in the same state, and 0 otherwise. Leave the query register in the same state it started in.
In this task you are allowed to allocate extra qubits.
%kata T14_ColorEqualityOracle_2bit
operation ColorEqualityOracle_2bit (c0 : Qubit[], c1 : Qubit[], target : Qubit) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
This task is the same as task 1.4, but in this task you are NOT allowed to allocate extra qubits.
%kata T15_ColorEqualityOracle_Nbit
operation ColorEqualityOracle_Nbit (c0 : Qubit[], c1 : Qubit[], target : Qubit) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
The vertex graph coloring is a coloring of graph vertices which labels each vertex with one of the given colors so that no two vertices of the same color are connected by an edge.
Inputs:
The number of vertices in the graph $V$ ($V \leq 6$).
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$.
$i$-th element of the array is the color of the vertex number $i$.
Output:
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.
Example:
Graph 0 -- 1 -- 2 would have $V = 3$ and edges = [(0, 1), (1, 2)]
.
Some of the valid colorings for it would be [0, 1, 0]
and [-1, 5, 18]
.
%kata T21_IsVertexColoringValid
function IsVertexColoringValid (V : Int, edges: (Int, Int)[], colors: Int[]) : Bool {
// ...
return true;
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Inputs:
The number of vertices in the graph $V$ ($V \leq 6$).
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$.
An array of $2V$ qubits colorsRegister
that encodes the color assignments.
A qubit in an arbitrary state $|y\rangle$ (target qubit).
Goal:
Transform state $|x, y\rangle$ into state $|x, y \oplus f(x)\rangle$ ($\oplus$ is addition modulo 2), where $f(x) = 1$ if the given vertex coloring is valid, and 0 otherwise. Leave the query register in the same state it started in.
Each color in colorsRegister
is represented as a 2-bit integer in little-endian format.
See task 1.3 for a more detailed description of color assignments.
%kata T22_VertexColoringOracle
operation VertexColoringOracle (V : Int,
edges : (Int, Int)[],
colorsRegister : Qubit[],
target : Qubit) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Inputs:
The number of vertices in the graph $V$ ($V \leq 6$).
A marking oracle which implements vertex coloring verification, as implemented in task 2.2.
Output:
A valid vertex coloring for the graph, in a format used in task 2.1.
%kata T23_GroversAlgorithm
operation GroversAlgorithm (V : Int, oracle : ((Qubit[], Qubit) => Unit is Adj)) : Int[] {
// ...
return [0, size = V];
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Weak graph coloring is a coloring of graph vertices which labels each vertex with one of the given colors so that each vertex is either isolated or is connected by an edge to at least one neighbor of a different color.
Inputs:
Output:
True if the edge contains the vertex provided, and false otherwise.
Examples:
%kata T31_DoesEdgeContainVertex
function DoesEdgeContainVertex (edge: (Int, Int), vertex : Int) : Bool {
// ...
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Inputs:
The number of vertices in the graph $V$ ($V \leq 6$).
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$.
$i$-th element of the array is the color of the vertex number $i$.
Output:
True if the vertex is weakly colored (i.e., it is connected to at least one neighboring vertex of different color), and false otherwise.
Note:
An isolated vertex (a vertex without neighbors) is considered to be weakly colored.
Example:
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.
%kata T32_IsVertexWeaklyColored
function IsVertexWeaklyColored (V : Int, edges: (Int, Int)[], colors: Int[], vertex : Int) : Bool {
// ...
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Inputs:
The number of vertices in the graph $V$ ($V \leq 6$).
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$.
$i$-th element of the array is the color of the vertex number $i$.
Output:
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.
Example:
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]
.
%kata T33_IsWeakColoringValid
function IsWeakColoringValid (V : Int, edges: (Int, Int)[], colors: Int[]) : Bool {
// ...
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Inputs:
The number of vertices in the graph $V$ ($V \leq 6$).
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$.
An array of $2V$ qubits colorsRegister
that encodes the color assignments.
A qubit in an arbitrary state $|y\rangle$ (target qubit).
A vertex in the graph, indexed $0$ through $V - 1$.
Goal:
Transform state $|x, y\rangle$ into state $|x, y \oplus f(x)\rangle$ ($\oplus$ is addition modulo 2), where $f(x) = 1$ if the given weak coloring is valid, and 0 otherwise. Leave the query register in the same state it started in.
Each color in colorsRegister
is represented as a 2-bit integer in little-endian format.
See $Task\ 1.3$ for a more detailed description of color assignments.
%kata T34_WeaklyColoredVertexOracle
open Microsoft.Quantum.Arrays;
operation WeaklyColoredVertexOracle(V : Int, edges: (Int, Int)[], colorsRegister : Qubit[], target : Qubit, vertex : Int) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Inputs:
The number of vertices in the graph $V$ ($V \leq 6$).
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$.
An array of $2V$ qubits colorsRegister
that encodes the color assignments.
A qubit in an arbitrary state $|y\rangle$ (target qubit).
Goal:
Transform state $|x, y\rangle$ into state $|x, y \oplus f(x)\rangle$ ($\oplus$ is addition modulo 2), where $f(x) = 1$ if the given weak coloring is valid, and 0 otherwise. Leave the query register in the same state it started in.
Each color in colorsRegister
is represented as a 2-bit integer in little-endian format.
See $Task\ 1.3$ for a more detailed description of color assignments.
%kata T35_WeakColoringOracle
operation WeakColoringOracle (
V : Int,
edges : (Int, Int)[],
colorsRegister : Qubit[],
target : Qubit
) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
Inputs:
The number of vertices in the graph $V$ ($V \leq 6$).
A marking oracle which implements weak coloring verification, as implemented in Task 3.5.
Output:
A valid weak coloring for the graph, in a format used in Task 3.3.
%kata T36_GroversAlgorithmForWeakColoring
operation GroversAlgorithmForWeakColoring (V : Int, oracle : ((Qubit[], Qubit) => Unit is Adj)) : Int[] {
// ...
}
Can't come up with a solution? See the explained solution in the Graph Coloring Workbook.
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.
Inputs:
The number of vertices in the graph $V$ ($V \leq 6$).
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$.
Output:
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.
Example:
Consider a graph with $V = 3$ and edges = [(0, 1), (0, 2), (1, 2)]
.
The adjacency matrix for it would be:
%kata T41_EdgesListAsAdjacencyMatrix
function EdgesListAsAdjacencyMatrix (V : Int, edges : (Int, Int)[]) : Int[][] {
// ...
return [];
}
Inputs:
The number of vertices in the graph $V (V \leq 6)$.
An adjacency matrix describing the graph in the format from task 4.1.
Output:
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.
Example:
Consider the adjacency matrix $$ \begin{bmatrix} -1 & 0 & 1 \\ 0 & -1 & 2 \\ 1 & 2 & -1 \end{bmatrix} $$
The list of triangles for it would be [(0, 1, 2)]
.
%kata T42_AdjacencyMatrixAsTrianglesList
function AdjacencyMatrixAsTrianglesList (V : Int, adjacencyMatrix : Int[][]) : (Int, Int, Int)[] {
// ...
return [];
}
Inputs:
The number of vertices in the graph $V (V \leq 6)$.
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$.
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.
Output:
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.
Example:
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]
.
%kata T43_IsVertexColoringTriangleFree
function IsVertexColoringTriangleFree (V : Int, edges: (Int, Int)[], colors: Int[]) : Bool {
// ...
return true;
}
Inputs:
a 3-qubit array inputs
,
a qubit output
.
Goal:
Flip the output qubit if and only if at least two of the input qubits are different.
Example:
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$.
%kata T44_ValidTriangleOracle
operation ValidTriangleOracle (inputs : Qubit[], output : Qubit) : Unit is Adj+Ctl {
// ...
}
Inputs:
The number of vertices in the graph $V (V \leq 6)$.
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.
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.
A qubit target
in an arbitrary state.
Goal:
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.
In this task you are not allowed to use quantum gates that use more qubits than the number of edges in the graph, 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. You are guaranteed that in tests that have 4 or more edges in the graph the number of triangles in the graph will be strictly less than the number of edges.
Example:
A graph with 3 vertices and 3 edges [(0, 1), (1, 2), (2, 0)]
has one triangle.
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)$.
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.
%kata T45_TriangleFreeColoringOracle
operation TriangleFreeColoringOracle (
V : Int,
edges : (Int, Int)[],
colorsRegister : Qubit[],
target : Qubit
) : Unit is Adj+Ctl {
// ...
}