UnitaryPatterns/UnitaryPatterns.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Unitary Patterns\n",
    "\n",
    "The **\"Unitary Patterns\"** quantum kata is a series of exercises designed\n",
    "to get you comfortable with creating unitary transformations which can be represented\n",
    "with matrices of certain shapes (with certain pattern of zero and non-zero values).\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.\n",
    "\n",
    "Within each section, tasks are given in approximate order of increasing difficulty; \n",
    "harder ones are marked with asterisks.\n",
    "\n",
    "<br/>\n",
    "\n",
    "Each task describes a matrix which your unitary needs to implement.\n",
    "The row and column indices of the matrix elements are in little-endian format (the least significant bit is stored first).\n",
    "For example, index 1 corresponds to the qubit state $|10...0\\rangle$, and to store this state in an array of qubits `qs` \n",
    "its first element `qs[0]` would have to be in state $|1\\rangle$ and the rest of the qubits would have to be in state $|0\\rangle$.\n",
    "\n",
    "In the example patterns provided in the tasks, `X` marks a \"non-zero\" element, and `.` marks a \"zero\" element.\n",
    "A \"zero\" element of a matrix is a complex number which has an absolute value of 0.001 or less,\n",
    "and a \"non-zero\" element is a complex number which has an absolute value of 0.001 or greater.\n",
    "You can see the details of the verification in [`Tests.qs`](.\\Tests.qs) file, operation `AssertOperationMatrixMatchesPattern`.\n",
    "\n",
    "Note that all tasks require you to implement a unitary transformation,\n",
    "which means that you're not allowed to use any measurements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To begin, first prepare this notebook for execution (if you skip this step, you'll get \"Syntax does not match any known patterns\" error when you try to execute Q# code in the next cells; if you skip the second step, you'll get \"Invalid test name\" error):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%package Microsoft.Quantum.Katas::0.8.1907.1701"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The package versions in the output of the cell above should always match. If you are running the Notebooks locally and the versions do not match, please install the IQ# version that matches the version of the `Microsoft.Quantum.Katas` package.\n",
    "> <details>\n",
    "> <summary><u>How to install the right IQ# version</u></summary>\n",
    "> For example, if the version of `Microsoft.Quantum.Katas` package above is 0.1.2.3, the installation steps are as follows:\n",
    ">\n",
    "> 1. Stop the kernel.\n",
    "> 2. Uninstall the existing version of IQ#:\n",
    ">        dotnet tool uninstall microsoft.quantum.iqsharp -g\n",
    "> 3. Install the matching version:\n",
    ">        dotnet tool install microsoft.quantum.iqsharp -g --version 0.1.2.3\n",
    "> 4. Reinstall the kernel:\n",
    ">        dotnet iqsharp install\n",
    "> 5. Restart the Notebook.\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%workspace reload"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1. Main diagonal\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:** \n",
    "Implement a unitary transformation on N qubits which is represented by a matrix\n",
    "with non-zero elements on the main diagonal and zero elements everywhere else.\n",
    "\n",
    "**Example:** For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    X...\n",
    "    .X..\n",
    "    ..X.\n",
    "    ...X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T01_MainDiagonal_Test \n",
    "\n",
    "operation MainDiagonal (qs : Qubit[]) : Unit {\n",
    "    // The simplest example of such a unitary transformation is represented by an identity matrix.\n",
    "    // This means that the operation doesn't need to do anything with the input qubits.\n",
    "    // Execute this cell to see that this solution is correct.\n",
    "\n",
    "    // You are welcome to try and come up with other diagonal unitaries.\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2. All-non-zero matrix\n",
    "\n",
    "**Input:**\n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:** \n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with all elements non-zero.\n",
    "\n",
    "**Example:** For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XXXX\n",
    "    XXXX\n",
    "    XXXX\n",
    "    XXXX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T02_AllNonZero_Test \n",
    "\n",
    "operation AllNonZero (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3. Block diagonal matrix\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:** \n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "which has 2x2 blocks of non-zero elements on the main diagonal and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XX......\n",
    "    XX......\n",
    "    ..XX....\n",
    "    ..XX....\n",
    "    ....XX..\n",
    "    ....XX..\n",
    "    ......XX\n",
    "    ......XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T03_BlockDiagonal_Test \n",
    "\n",
    "operation BlockDiagonal (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 4. Quarters\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements in top left and bottom right quarters \n",
    "and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XXXX....\n",
    "    XXXX....\n",
    "    XXXX....\n",
    "    XXXX....\n",
    "    ....XXXX\n",
    "    ....XXXX\n",
    "    ....XXXX\n",
    "    ....XXXX\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary>Need a hint? Click here</summary>\n",
    "  Represent this matrix as a tensor product of a $2 \\times 2$ diagonal matrix and a larger matrix with all non-zero elements.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T04_Quarters_Test \n",
    "\n",
    "operation Quarters (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 5. Even chessboard pattern\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements in positions where row and column indices have the same parity \n",
    "and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    X.X.\n",
    "    .X.X\n",
    "    X.X.\n",
    "    .X.X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T05_EvenChessPattern_Test \n",
    "\n",
    "operation EvenChessPattern (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 6. Odd chessboard pattern\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements in positions where row and column indices have different parity \n",
    "and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    .X.X\n",
    "    X.X.\n",
    "    .X.X\n",
    "    X.X."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T06_OddChessPattern_Test \n",
    "\n",
    "operation OddChessPattern (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 7. Anti-diagonal\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements on the anti-diagonal and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    ...X\n",
    "    ..X.\n",
    "    .X..\n",
    "    X..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T07_Antidiagonal_Test \n",
    "\n",
    "operation Antidiagonal (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 8. $2 \\times 2$ chessboard pattern\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "in which zero and non-zero elements form a chessboard pattern with 2x2 squares, \n",
    "with the top left square occupied by non-zero elements.\n",
    "\n",
    "**Example:** \n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XX..XX..\n",
    "    XX..XX..\n",
    "    ..XX..XX\n",
    "    ..XX..XX\n",
    "    XX..XX..\n",
    "    XX..XX..\n",
    "    ..XX..XX\n",
    "    ..XX..XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T08_ChessPattern2x2_Test \n",
    "\n",
    "operation ChessPattern2x2 (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 9. Two patterns\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix with \n",
    "* all zero elements in the top right and bottom left quarters, \n",
    "* an anti-diagonal pattern from task 1.6 in the top left quarter, \n",
    "* and an all-non-zero pattern from task 1.2 in the bottom right quarter.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    .X..\n",
    "    X...\n",
    "    ..XX\n",
    "    ..XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T09_TwoPatterns_Test \n",
    "\n",
    "operation TwoPatterns (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 10. Increasing blocks\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix defined recursively:\n",
    "\n",
    "* For N = 1 the matrix has non-zero elements on the main diagonal and zero elements everywhere else,\n",
    "* For larger N the matrix has\n",
    "   * all zero elements in the top right and bottom left quarters,\n",
    "   * the matrix for N-1 in the top left quarter, and \n",
    "   * all non-zero elements in the bottom right quarter.\n",
    "\n",
    "**Example:** \n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    X.......\n",
    "    .X......\n",
    "    ..XX....\n",
    "    ..XX....\n",
    "    ....XXXX\n",
    "    ....XXXX\n",
    "    ....XXXX\n",
    "    ....XXXX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T10_IncreasingBlocks_Test \n",
    "\n",
    "operation IncreasingBlocks (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 11. X-Wing fighter\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements on the main diagonal and the anti-diagonal \n",
    "and zero elements everywhere else.\n",
    "\n",
    "**Example:** \n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    X......X\n",
    "    .X....X.\n",
    "    ..X..X..\n",
    "    ...XX...\n",
    "    ...XX...\n",
    "    ..X..X..\n",
    "    .X....X.\n",
    "    X......X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_XWing_Fighter_Test \n",
    "\n",
    "operation XWing_Fighter (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 12. Rhombus\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements forming a rhombus of width 1 with sides parallel to main diagonals.\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    .XX.\n",
    "    X..X\n",
    "    X..X\n",
    "    .XX.\n",
    "\n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    ...XX...\n",
    "    ..X..X..\n",
    "    .X....X.\n",
    "    X......X\n",
    "    X......X\n",
    "    .X....X.\n",
    "    ..X..X..\n",
    "    ...XX..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_Rhombus_Test \n",
    "\n",
    "operation Rhombus (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 13*. TIE fighter\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state ($2 \\leq N \\leq 5$).\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements in the following positions:\n",
    "\n",
    "- The central $2 \\times 2$ sub-matrix;\n",
    "\n",
    "- The diagonals of the top right and bottom left sub-matrices of size $2^{N-1}-1$\n",
    "that do not overlap with the central $2 \\times 2$ sub-matrix;\n",
    "\n",
    "- The anti-diagonals of the top left and bottom right sub-matrices of size $2^{N-1}-1$\n",
    "that do not overlap with the central $2 \\times 2$ sub-matrix.\n",
    "\n",
    "**Example:** \n",
    "\n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    ..X..X..\n",
    "    .X....X.\n",
    "    X......X\n",
    "    ...XX...\n",
    "    ...XX...\n",
    "    X......X\n",
    "    .X....X.\n",
    "    ..X..X.."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_TIE_Fighter_Test \n",
    "\n",
    "operation TIE_Fighter (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 14**. Creeper\n",
    "\n",
    "**Input:** \n",
    "3 qubits in an arbitrary state.\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on 3 qubits which is represented by a matrix \n",
    "with non-zero elements in the following pattern: \n",
    "\n",
    "    XX....XX\n",
    "    XX....XX\n",
    "    ...XX...\n",
    "    ...XX...\n",
    "    ..X..X..\n",
    "    ..X..X..\n",
    "    XX....XX\n",
    "    XX....XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_Creeper_Test \n",
    "\n",
    "operation Creeper (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 15**. Hessenberg matrices\n",
    "\n",
    "**Input:** \n",
    "N qubits in an arbitrary state ($2 \\leq N \\leq 4$).\n",
    "\n",
    "**Goal:**\n",
    "Implement a unitary transformation on N qubits which is represented by a matrix \n",
    "with non-zero elements forming an upper diagonal matrix plus the first subdiagonal. \n",
    "This is called a [Hessenberg matrix](https://en.wikipedia.org/wiki/Hessenberg_matrix).\n",
    "\n",
    "**Example:** \n",
    "For N = 2, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XXXX\n",
    "    XXXX\n",
    "    .XXX\n",
    "    ..XX\n",
    "\n",
    "For N = 3, the matrix of the transformation should look as follows:\n",
    "\n",
    "    XXXXXXXX\n",
    "    XXXXXXXX\n",
    "    .XXXXXXX\n",
    "    ..XXXXXX\n",
    "    ...XXXXX\n",
    "    ....XXXX\n",
    "    .....XXX\n",
    "    ......XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T15_Hessenberg_Matrix_Test \n",
    "\n",
    "operation Hessenberg_Matrix (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}