UnitaryPatterns/Workbook_UnitaryPatterns.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Unitary Patterns Workbook\n",
    "\n",
    "**What is this workbook?**\n",
    "A workbook is a collection of problems, accompanied by solutions to them. \n",
    "The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required. \n",
    "\n",
    "Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n",
    "\n",
    "This workbook describes the solutions to the problems offered in the [UnitaryPatterns](./UnitaryPatterns.ipynb). \n",
    "\n",
    "\n",
    "**What you should know for this workbook**\n",
    "\n",
    "1. Basic single-qubit gates and multi-qubit gates.\n",
    "2. The concept of tensor product."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For an overview of all the gates have a look at the Q# quick reference [here](./../quickref/qsharp-quick-reference.pdf)."
   ]
  },
  {
   "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\n",
    "\n",
    "### Solution\n",
    "\n",
    "The required unitary transformation is a diagonal matrix in which all diagonal elements are non-zero. \n",
    "Since the transformation has to be unitary, i.e., it must preserve the norm of the vectors it is applied to, all diagonal elements have to have norm of $1$, i.e., be represented as complex numbers $e^{i\\alpha}$ for some real $\\alpha$.\n",
    "\n",
    "The simplest such unitary is the identity matrix $I^{\\otimes N}$, where $N$ is the number of qubits.\n",
    "For $N=2$ this would be \n",
    "$$\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\end{bmatrix} \n",
    "= \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} \\otimes \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix}$$\n",
    "\n",
    "For a general $N$ this can be achieved by applying the unitary $I$ to all qubits, \n",
    "which is equivalent to a no-op."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T01_MainDiagonal \n",
    "\n",
    "operation MainDiagonal (qs : Qubit[]) : Unit {\n",
    "    // We don't need to write out applying identity unitary, since it is a no-op\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-1.-Main-diagonal)"
   ]
  },
  {
   "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\n",
    "\n",
    "### Solution\n",
    "\n",
    "We need to construct a unitary that converts any basis state into a superposition of all basis states.\n",
    "\n",
    "For $N=1$ the simplest such unitary is the Hadamard gate $H=\\frac{1}{\\sqrt2}\\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix}$. \n",
    "Similarly, for any $N$ such a unitary would be $U=H^{\\otimes N}$ (apply $H$ to each qubit).\n",
    "\n",
    "For $N=2$ this would be \n",
    "$$H^{\\otimes 2} = \\frac{1}{\\sqrt2}\\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix} \\otimes \\frac{1}{\\sqrt2}\\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix}\n",
    "= \\frac{1}{2}\\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & -1 & 1 & -1 \\\\ 1 & 1 & -1 & -1 \\\\ 1 & -1 & -1 & 1 \\end{bmatrix} $$\n",
    "\n",
    "Hadamard matrices are guaranteed to have all their elements either $\\frac{1}{\\sqrt{2^N}}$ or $-\\frac{1}{\\sqrt{2^N}}$. \n",
    "This can be easily proven via induction, as the $H$ matrix has no non-zero elements. Since each element of a tensor product is a result of multiplication of several elements of the $H$ matrix, it cannot be zero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T02_AllNonZero \n",
    "\n",
    "operation AllNonZero (qs : Qubit[]) : Unit {\n",
    "    ApplyToEach(H, qs); \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-2.-All-non-zero-matrix)"
   ]
  },
  {
   "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 $2 \\times 2$ 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\n",
    "\n",
    "### Solution\n",
    "\n",
    "From the approach we took in the previous tasks, we can see a pattern:\n",
    "we need to break the given unitary transformation into a tensor product of smaller matrices.\n",
    "\n",
    "The block diagonal matrix can be broken into product of two matrices.\n",
    "\n",
    "For the illustrative $N=3$ case we can break it into\n",
    "$$ \\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\end{bmatrix} \\otimes\n",
    "\\begin{bmatrix} x & x \\\\ x & x \\end{bmatrix}\n",
    "= \\begin{bmatrix} x & x & . & . & . & . & . & .\\\\\n",
    "x & x & . & . & . & . & . & .\\\\\n",
    ". & . & x & x & . & . & . & .\\\\\n",
    ". & . & x & x & . & . & . & .\\\\\n",
    ". & . & . & . & x & x & . & .\\\\\n",
    ". & . & . & . & x & x & . & .\\\\\n",
    ". & . & . & . & . & . & x & x\\\\\n",
    ". & . & . & . & . & . & x & x \\end{bmatrix} $$\n",
    "    \n",
    "For a general $N\\gt2$ we have the required transformation $ U = I^{\\otimes N-1} \\otimes \\begin{bmatrix} x & x \\\\ x & x \\end{bmatrix}$, where the second matrix has all non-zero elements.\n",
    "\n",
    "The $2 \\times 2$ matrix can be chosen as the Hadamard matrix $H = \\frac{1}{\\sqrt2}\\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix}$. \n",
    "\n",
    "Thus the required unitary transformation is $U = I^{\\otimes N-1} \\otimes H$.\n",
    "\n",
    "> Note that this is the first task in which endianness matters: the indices in the matrices use little endian, this the rightmost unitary in the tensor product (which corresponds to the least significant bit of the index) is applied to qubit with index $0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T03_BlockDiagonal \n",
    "\n",
    "operation BlockDiagonal (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    // We don't need to write out applying identity unitary, since it is a no-op\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-3.-Block-diagonal-matrix)"
   ]
  },
  {
   "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 = 3, 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",
    "### Solution\n",
    "\n",
    "We again break the given unitary transformation into a tensor product of smaller matrices.\n",
    "\n",
    "For the illustrative $N=3$ case we can break it into\n",
    "$$\\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} \\otimes \n",
    "\\begin{bmatrix} x & x & x & x \\\\ x & x & x & x \\\\ x & x & x & x \\\\ x & x & x & x \\end{bmatrix} \n",
    "= \\begin{bmatrix} x & x & x & x & . & . & . & .\\\\\n",
    "x & x & x & x & . & . & . & .\\\\\n",
    "x & x & x & x & . & . & . & .\\\\\n",
    "x & x & x & x & . & . & . & .\\\\\n",
    ". & . & . & . & x & x & x & x\\\\\n",
    ". & . & . & . & x & x & x & x\\\\\n",
    ". & . & . & . & x & x & x & x\\\\\n",
    ". & . & . & . & x & x & x & x \\end{bmatrix} $$\n",
    "\n",
    "We can see that the second matrix is the same as what we saw in task 2 - a matrix with all non-zero elements. \n",
    "Hence we reach a general solution for $N\\gt2$: \n",
    "\n",
    "$$ U = I \\otimes H^{\\otimes N-1}$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T04_Quarters \n",
    "\n",
    "operation Quarters (qs : Qubit[]) : Unit {\n",
    "    // Same as in previous task, the little endian encoding of indices means that \n",
    "    // the leftmost unitary (identity) is applied to the qubit with index N-1,\n",
    "    // so we need to apply H gates to all qubits except the last one.\n",
    "    ApplyToEach(H, qs[0 .. Length(qs)-2]); \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 4 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-4.-Quarters)"
   ]
  },
  {
   "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\n",
    "\n",
    "### Solution\n",
    "\n",
    "This is very similar to task 4, with just the order of matrices changed.\n",
    "We again break the given unitary transformation into tensor product of smaller matrices.\n",
    "\n",
    "For the illustrative $N=2$ case we can break it into\n",
    "$$\\begin{bmatrix} x & x \\\\ x & x \\end{bmatrix} \\otimes \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} \n",
    "= \\begin{bmatrix} x & . & x & . \\\\\n",
    ". & x & . & x \\\\\n",
    "x & . & x & . \\\\\n",
    ". & x & . & x \\end{bmatrix} $$\n",
    "\n",
    "We again pick the non-zero block matrix as $H$. \n",
    "Hence we get a general solution for $N$: \n",
    "\n",
    "$$ U = H^{\\otimes N-1} \\otimes I$$\n",
    "\n",
    "> Q# expression `qs[1 ...]` gets a sub-array of all elements of `qs` except the first one. You can read more about array slicing and inferred start/end values in the [Q# documentation](https://docs.microsoft.com/azure/quantum/user-guide/language/expressions/itemaccessexpressions)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T05_EvenChessPattern \n",
    "\n",
    "operation EvenChessPattern (qs : Qubit[]) : Unit {\n",
    "    // Same as in previous task, the little endian encoding of indices means that \n",
    "    // the rightmost unitary (identity) is applied to the qubit with index N-1,\n",
    "    // so we need to apply H gates to all qubits except the first one.\n",
    "    ApplyToEach(H, qs[1 ...]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 5 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-5.-Even-chessboard-pattern)"
   ]
  },
  {
   "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.\n",
    "\n",
    "### Solution\n",
    "\n",
    "The solution is very similar to task 5, but we need to switch the order of $0$ and $1$ elements in the $2 \\times 2$ matrix, so that `X` and `.` elements are swapped in the final result. To do this, we choose $X$ matrix instead of $I$. \n",
    "\n",
    "For the illustrative case $N=2$ this becomes \n",
    "$$\\begin{bmatrix} x & x \\\\ x & x \\end{bmatrix} \\otimes \\begin{bmatrix} 0 & 1 \\\\ 1 & 0 \\end{bmatrix} \n",
    "= \\begin{bmatrix} \n",
    ". & x & . & x \\\\\n",
    "x & . & x & . \\\\\n",
    ". & x & . & x \\\\\n",
    "x & . & x & . \\end{bmatrix} $$\n",
    "\n",
    "Thus the required transformation for any $N$ is \n",
    "\n",
    "$$ U = H^{\\otimes N-1} \\otimes X$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T06_OddChessPattern \n",
    "\n",
    "operation OddChessPattern (qs : Qubit[]) : Unit {\n",
    "    X(qs[0]);\n",
    "    ApplyToEach(H, qs[1 ...]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 6 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-6.-Odd-chessboard-pattern)"
   ]
  },
  {
   "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...\n",
    "\n",
    "### Solution\n",
    "\n",
    "Similarly to task 1, since the transformation has to be unitary, i.e., it must preserve the norm of the vectors it is applied to, all anti-diagonal elements have to have norm of $1$, i.e., be represented as complex numbers $e^{i\\alpha}$ for some real $\\alpha$. The easiest way to achieve this is to choose all anti-diagonal elements to be $1$.\n",
    "\n",
    "For $N=1$ the solution would be the Pauli $X$ gate.\n",
    "\n",
    "For $N=2$ we can again represent the matrix as a tensor product of smaller matrices: \n",
    "$$\\begin{bmatrix} 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 1 & 0 & 0 & 0 \\end{bmatrix} \n",
    "= \\begin{bmatrix} 0 & 1 \\\\ 1 & 0 \\end{bmatrix} \\otimes \\begin{bmatrix} 0 & 1 \\\\ 1 & 0 \\end{bmatrix}$$\n",
    "\n",
    "For a general $N$ the simplest such unitary is thus $X^{\\otimes N}$ - applying the $X$ gate to each qubit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T07_Antidiagonal \n",
    "\n",
    "operation Antidiagonal (qs : Qubit[]) : Unit {\n",
    "    ApplyToEach(X, qs); \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 7 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-7.-Anti-diagonal)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 8. 2 x 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\n",
    "\n",
    "### Solution\n",
    "\n",
    "This task is something between tasks 4 (a pattern of two large diagonal blocks) and 5 (a chessboard pattern of $1 \\times 1$ squares).\n",
    "Both of them are formed using only Hadamard gates, so it makes sense to try and see if the pattern in this task can be expressed this way as well.\n",
    "\n",
    "Consider the case of $N = 2$; the pattern you need to implement in this task is exactly the same as the pattern in task 4 (two large blocks),\n",
    "which you can obtain as $I \\otimes H$:\n",
    "\n",
    "$$I \\otimes H = \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} \\otimes \\begin{bmatrix} 1 & 1 \\\\ 1 & -1\\end{bmatrix} = \n",
    "\\begin{bmatrix} 1 & 1 & 0 & 0 \\\\ 1 & -1 & 0 & 0 \\\\ 0 & 0 & 1 & 1 \\\\ 0 & 0 & 1 & -1\\end{bmatrix}$$\n",
    "\n",
    "\n",
    "More formally, you can think about this task in terms of tensor products: \n",
    "* If you consider tensor product $H \\otimes A$, you effectively repeat the pattern of matrix $A$ 4 times (once in each of the quarters of the result);\n",
    "* If you consider tensor product $A \\otimes H$, you replace each zero element of $A$ with a block of 4 zeros, and each non-zero element with a block of non-zeros.\n",
    "\n",
    "The smallest block you need to repeat in the $2 \\times 2$ chessboard pattern is $I \\otimes H$ we've seen earlier.\n",
    "\n",
    "Now you can repeat it as many times as you need by multiplying H gates by it:\n",
    "$$H \\otimes (I \\otimes H) = \\begin{bmatrix} I \\otimes H & I \\otimes H \\\\ I \\otimes H & - I \\otimes H\\end{bmatrix} = \n",
    "\\begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\\\ 1 & -1 & 0 & 0 & 1 & -1 & 0 & 0 \\\\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\\\ 0 & 0 & 1 & -1 & 0 & 0 & 1 & -1 \\\\\n",
    "                1 & 1 & 0 & 0 & -1 & -1 & 0 & 0 \\\\ 1 & -1 & 0 & 0 & -1 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 1 & 0 & 0 & -1 & -1 \\\\ 0 & 0 & 1 & -1 & 0 & 0 & -1 & 1  \\end{bmatrix}$$\n",
    "                \n",
    "The unitary transformation is $H^{\\otimes N-2} \\otimes I \\otimes H$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T08_ChessPattern2x2 \n",
    "\n",
    "operation ChessPattern2x2 (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    I(qs[1]); // No-op added for the sake of completeness\n",
    "    ApplyToEach(H, qs[2 ...]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 8 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-8.-2-x-2-chessboard-pattern)"
   ]
  },
  {
   "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 7 in the top left quarter, \n",
    "* and an all-non-zero pattern from task 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\n",
    " \n",
    "### Solution\n",
    "\n",
    "This matrix can not be represented as a tensor product any longer, since the patterns in the top left block and the bottom right block are different.\n",
    "We need to figure out a different way to combine the patterns from task 7 and task 2. \n",
    "\n",
    "Let's label the given unitary transformation as $U$, the unitary that implements the anti-diagonal pattern from task 7 as $U_7$, and the unitary that implements the all-non-zero pattern from task 2 as $U_2$.\n",
    "\n",
    "The top left block of the matrix is the area where the most significant bit of both input and output indices equals $0$, and the effect of the unitary $U$ on $N$ qubits is defined as the effect of the unitary $U_7$ on the $N-1$ least significant bits. \n",
    "(Remember that with little endian encoding of the indices the most significant bit is stored in the last qubit.)\n",
    "\n",
    "$$U(|\\psi\\rangle \\otimes |0\\rangle) = U_7(|\\psi\\rangle) \\otimes |0\\rangle $$\n",
    "\n",
    "The left half of the matrix can be described as follows: if the last qubit of the input is in state $|0\\rangle$, \n",
    "leave that qubit unchanged and apply $U_7$ to the rest of the qubits. If we choose $U_7 = X^{\\otimes N-1}$, like we did in task 7, we'll get:\n",
    "\n",
    "$$U|\\psi\\rangle \\otimes |0\\rangle = \\big(X^{\\otimes N-1}|\\psi\\rangle \\big) \\otimes |0\\rangle $$\n",
    "\n",
    "Similarly, the bottom right block is the area where the most significant bit of input and output equals $1$,\n",
    "$$U|\\phi\\rangle \\otimes |1\\rangle = U_2(|\\phi\\rangle) \\otimes |1\\rangle $$\n",
    "\n",
    "The right half of the matrix can be described as follows: if the last qubit of the input is in state $|1\\rangle$,\n",
    "leave that qubit unchanged and apply $U_2$ to the rest of the qubits. If we choose $U_2 = H^{\\otimes N-1}$, like we did in task 2, we'll get \n",
    "\n",
    "$$U|\\phi\\rangle \\otimes |1\\rangle = \\big(H^{\\otimes N-1}|\\phi\\rangle \\big) \\otimes |1\\rangle $$\n",
    "\n",
    "Combining these descriptions, we can implement the unitary $U$ in 2 parts:\n",
    "\n",
    "1. Apply controlled version of $H^{\\otimes N-1}$ with last qubit as control and remaining qubits as target.  \n",
    "   This is the same as applying $N-1$ individual gates, each of them a controlled version of $H$, with each of the remaining qubits as targets.\n",
    "2. Apply a zero-controlled version of $H^{\\otimes N-1}$ with last qubit as control and remaining qubits as target.\n",
    "\n",
    "For $N=2$ we have\n",
    "\n",
    "$$\\begin{bmatrix} 0 & 1 & 0 & 0 \\\\ \n",
    "    1 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\ \n",
    "    0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}}\\end{bmatrix}$$\n",
    "\n",
    "and for $N=3$ we have\n",
    "\n",
    "$$\\begin{bmatrix} \n",
    "    0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\ \n",
    "    0 & 0 & 0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} \\\\ \n",
    "    0 & 0 & 0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} \\\\ \n",
    "    0 & 0 & 0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\ \n",
    "    \\end{bmatrix}$$\n",
    "\n",
    "> We'll use Q# library operations from the `Microsoft.Quantum.Arrays` namespace: [Tail](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.arrays.tail) which returns the last element of the array and [Most](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.arrays.most) which returns all elements except the last one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T09_TwoPatterns \n",
    "\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation TwoPatterns (qs : Qubit[]) : Unit {\n",
    "    ApplyToEach(Controlled H([Tail(qs)], _), Most(qs));\n",
    "    ApplyToEach((ControlledOnInt(0, X))([Tail(qs)], _), Most(qs));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 9 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-9.-Two-patterns)"
   ]
  },
  {
   "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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "This task builds up on the task 9 in which matrices which are composed of smaller blocks but can't be represented as a tensor product. If we represent this unitary transformation for a given $N$ as $U_N$, then we see the following pattern:\n",
    "\n",
    "The bottom right block is the area where the most significant bit of input and output equals $1$, and similarly to the task 9 we can represent it as follows:\n",
    "\n",
    "$$U_N \\big(|\\phi\\rangle \\otimes |1\\rangle\\big) = \\big(H^{\\otimes N-1}|\\phi\\rangle \\big) \\otimes |1\\rangle$$\n",
    "\n",
    "The top left block is the area where the most significant bit of both input and output indices equals $0$, and it matches the pattern of the same unitary for the smaller number of qubits. \n",
    "The left half of the matrix can be described as follows: if the last qubit of the input is in state $|0\\rangle$, \n",
    "leave that qubit unchanged and apply an $U_{N-1}$ gate to remaining qubits. \n",
    "\n",
    "(Remember that with little endian encoding of the indices this bit is stored in the last qubit.)\n",
    "$$U_{N}|\\psi\\rangle \\otimes |0\\rangle = \\big(U_{N-1}|\\psi\\rangle \\big) \\otimes |0\\rangle $$\n",
    "\n",
    "This allows us to define the solution recursively, if we define the base of recursion as $U_1=I$:\n",
    "\n",
    "1. Apply controlled version of $H^{\\otimes N-1}$ with last qubit as control and remaining qubits as target. \n",
    "2. Apply a zero-controlled version of $U_{N-1}$ with last qubit as control and remaining qubits as target.\n",
    "\n",
    "> Q# allows us to express recursion without unrolling it, if we add a definition of controlled variant to our operation. We can do it automatically if we modify the signature of the task to include `is Adj+Ctl`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T10_IncreasingBlocks \n",
    "\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation IncreasingBlocks (qs : Qubit[]) : Unit is Adj + Ctl {\n",
    "    let N = Length(qs);\n",
    "    if N == 1 {\n",
    "        // for N = 1, we need an identity, which is equivalent to doing nothing\n",
    "    } else {\n",
    "        // Apply H to get bottom-right quarter right\n",
    "        ApplyToEachCA(Controlled H([Tail(qs)], _), Most(qs)); \n",
    "        // Apply the same operation recursively to get the top-left quarter right\n",
    "        (ControlledOnInt(0, IncreasingBlocks))([Tail(qs)], Most(qs));\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 10 of the Unitary Patterns kata.](./Workbook_UnitaryPatterns.ipynb#Task-10.-Increasing-blocks)"
   ]
  },
  {
   "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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "This transformation again cannot be broken into tensor product of smaller matrices. \n",
    "\n",
    "The columns of the unitary matrix tell us how the matrix acts on the computational basis states. First, we represent the computational basis states in little endian form: $|0\\rangle, |1\\rangle, ..., |2^{N}-2\\rangle, |2^{N}-1\\rangle$ for given $N$.\n",
    "Now we observe that for any $0\\leq i \\lt 2^N$, our unitary $U$ acts on a given computational basis state $|i\\rangle$ to convert it into a linear combination of $|i\\rangle$ and $|2^{N}-1-i\\rangle$:\n",
    "\n",
    "$$U|i\\rangle = \\alpha_i |i\\rangle + \\beta_i |2^{N}-1-i\\rangle$$\n",
    "\n",
    "Notice that both $|i\\rangle$ and $|2^{N}-1-i\\rangle$ will be transformed into some linear combination of $|i\\rangle$ and $|2^{N}-1-i\\rangle$. \n",
    "Hence to maintain orthogonality of these states (states which are orthogonal remain orthogonal under unitary transformations) we must pick coefficients $(\\alpha_i, \\beta_i)$ and $(\\alpha_{2^{N}-1-i}, \\beta_{2^{N}-1-i})$ such that the inner product of these states is \n",
    "\n",
    "$$\\langle i|U^\\dagger U|2^N-1-i\\rangle = \\langle i|2^N-1-i\\rangle = 0$$\n",
    "\n",
    "The simplest such coefficients are $\\big(\\frac{1}{\\sqrt{2}},\\frac{1}{\\sqrt{2}}\\big)$ and $\\big(\\frac{1}{\\sqrt{2}},\\frac{-1}{\\sqrt{2}}\\big)$. Our expression for defining the unitary becomes the following:\n",
    "\n",
    "$$U|i\\rangle = \\frac{1}{\\sqrt{2}} |i\\rangle + \\frac{1}{\\sqrt{2}} (-1)^{k} |2^{N}-1-i\\rangle$$\n",
    "\n",
    "Here $k$ is the most significant bit of the basis state $i$.\n",
    "\n",
    "We can simplify this expression further by observing that \n",
    "$|2^{N}-1-i\\rangle$ is the two's complement of $|i\\rangle$, i.e., $|2^{N}-1-i\\rangle= X^{\\otimes N}|i\\rangle$.\n",
    "Now we can describe the effect of the unitary on the basis states as follows:\n",
    "\n",
    "$$U|i\\rangle = \\frac{1}{\\sqrt{2}} |i\\rangle + (-1)^{k}\\frac{1}{\\sqrt{2}} X^{\\otimes N}|i\\rangle$$\n",
    "\n",
    "The dependence on the sign of the most significant bit hints towards using the $H$ gate: at some point we'll want to apply the $H$ gate to the most significant bit. \n",
    "\n",
    "This unitary can be constructed in 3 steps:\n",
    "\n",
    "1.  We use a series of CNOT gates with the most significant bit (MSB) acting as control and each of the remaining bits acting as target.\n",
    "    The gate will leave the MSB unchanged and flip the rest of the bits when in MSB is 1. \n",
    "    \n",
    "    > Let us take 2 examples for $N=3$ where the input states are $i=0$ and $i=6$. \n",
    "    > The states in little endian format would be $|000\\rangle$ and $|011\\rangle$. After step 1 these would become\n",
    "    > $|000\\rangle$ and $|101\\rangle$, respectively.\n",
    "    \n",
    "    The unitary for step 1 when $N=3$ would be \n",
    "    $$\\begin{bmatrix} \n",
    "    1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\end{bmatrix}$$\n",
    "\n",
    "2. We apply the Hadamard gate on the MSB. This will give us the necessary coefficients: \n",
    "    if MSB is 0 or 1, the coefficients would be $\\big(\\frac{1}{\\sqrt{2}},\\frac{1}{\\sqrt{2}}\\big)$ and \n",
    "    $\\big(\\frac{1}{\\sqrt{2}},\\frac{-1}{\\sqrt{2}}\\big)$, respectively. \n",
    "    \n",
    "    > After step 2 our examples would become\n",
    "    > $|00\\rangle \\otimes H|0\\rangle=\\frac{1}{\\sqrt{2}}|000\\rangle + \\frac{1}{\\sqrt{2}}|001\\rangle$ and \n",
    "    > $|10\\rangle \\otimes H|1\\rangle=\\frac{1}{\\sqrt{2}}|100\\rangle - \\frac{1}{\\sqrt{2}}|101\\rangle$. \n",
    "    \n",
    "    The unitary for step 2 is \n",
    "    $$\\frac{1}{\\sqrt{2}}\\begin{bmatrix} \n",
    "    1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \\end{bmatrix}$$\n",
    "\n",
    "3. Now we have the necessary coefficients, and one of the basis states in superposition matches the starting state $|i\\rangle$, but the second basis state is not two's complement of $|i\\rangle$. \n",
    "    To fix this, we repeat step 1 again. \n",
    "    \n",
    "    > After step 3 our examples would become\n",
    "    > $\\frac{1}{\\sqrt{2}}|000\\rangle + \\frac{1}{\\sqrt{2}}|111\\rangle$ and \n",
    "    > $\\frac{1}{\\sqrt{2}}|100\\rangle - \\frac{1}{\\sqrt{2}}|011\\rangle$. \n",
    "    \n",
    "    The unitary for step 3 is same as step 1. \n",
    "    \n",
    "If we multiply all 3 unitaries, we get the required unitary. \n",
    "    \n",
    "$$U =\n",
    "    \\begin{bmatrix} \n",
    "    1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\end{bmatrix} \\times \n",
    "    \\frac{1}{\\sqrt{2}}\\begin{bmatrix} \n",
    "    1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \\end{bmatrix} \\times\n",
    "    \\begin{bmatrix} \n",
    "    1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\end{bmatrix}\n",
    "= \\frac{1}{\\sqrt{2}}\\begin{bmatrix} \n",
    "    1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\ \n",
    "    0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\\\ \n",
    "    0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 1 & -1 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 \\\\ \n",
    "    0 & 1 & 0 & 0 & 0 & 0 & -1 & 0 \\\\ \n",
    "    1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \\end{bmatrix}$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_XWing_Fighter \n",
    "\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation XWing_Fighter (qs : Qubit[]) : Unit {\n",
    "    ApplyToEach(CNOT(Tail(qs), _), Most(qs));\n",
    "    H(Tail(qs));\n",
    "    ApplyToEach(CNOT(Tail(qs), _), Most(qs));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 11 of the Unitary Patterns kata.](./Workbook_UnitaryPatterns.ipynb#Task-11.-X-Wing-fighter)"
   ]
  },
  {
   "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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Task 12 is very similar to task 11: we will get this unitary transformation if we swap the left and right halves of the unitary matrix we implemented in task 11. \n",
    "This can be done by applying the $X$ gate on the most significant bit.\n",
    "\n",
    "Thus for the case $N=3$, the matrix would be \n",
    "$$\\frac{1}{\\sqrt{2}}\\begin{bmatrix} \n",
    "    0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\\\ \n",
    "    0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\\\ \n",
    "    0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\\\ \n",
    "    1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n",
    "    1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \\\\ \n",
    "    0 & 1 & 0 & 0 & 0 & 0 & -1 & 0 \\\\ \n",
    "    0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 \\\\ \n",
    "    0 & 0 & 0 & 1 & -1 & 0 & 0 & 0 \\end{bmatrix}$$\n",
    "\n",
    "> We can check this using the same examples as we used in task 11:\n",
    "> * The starting states in little endian format are $|000\\rangle$ and $|011\\rangle$;\n",
    "> * After applying the unitary transformation from task 11 we get \n",
    "$\\frac{1}{\\sqrt{2}}|000\\rangle + \\frac{1}{\\sqrt{2}}|111\\rangle$ and \n",
    "$\\frac{1}{\\sqrt{2}}|100\\rangle - \\frac{1}{\\sqrt{2}}|011\\rangle$ respectively;\n",
    ">\n",
    "> * We apply the $X$ gate on the MSB of the result to get $\\frac{1}{\\sqrt{2}}|001\\rangle + \\frac{1}{\\sqrt{2}}|110\\rangle$ and \n",
    "$\\frac{1}{\\sqrt{2}}|101\\rangle - \\frac{1}{\\sqrt{2}}|010\\rangle$. \n",
    ">\n",
    "> This is the exactly the same output as predicted by the unitary matrix above. \n",
    "\n",
    "Therefore, the implementation is simply applying the steps from task 11, followed by applying the $X$ gate on the MSB."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_Rhombus \n",
    "\n",
    "operation Rhombus (qs : Qubit[]) : Unit {\n",
    "    XWing_Fighter(qs);\n",
    "    X(qs[Length(qs) - 1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 12 of the Unitary Patterns kata.](./Workbook_UnitaryPatterns.ipynb#Task-12.-Rhombus)"
   ]
  },
  {
   "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..\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "For $N=3$ the top right corner of the required unitary in matrix form is \n",
    "$\\begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 1 & 0 & 0 & 0 \\end{bmatrix}$.\n",
    "\n",
    "This unitary is $\\sigma_{N-1} = \\sum_{i=0}^{2^{N-1}-1} |{i-1}\\rangle\\langle{i}|$ (indices are computed modulo $2^{N-1}$). \n",
    "It decrements the input state (in little endian format), i.e., maps $\\sigma_{N-1}|{i}\\rangle=|(i-1)$ mod $2^{N-1}\\rangle$.\n",
    "It can be implemented using cascading series of controlled $NOT$ gates (here the top wire denotes the least significant bit):\n",
    "\n",
    "<img src=\"./img/decrement.png\"/>\n",
    "\n",
    "We can arrive at one possible solution to this problem using $\\sigma_{N-1}$ and $\\Pi_X = X^{\\otimes N-1}$:\n",
    "\n",
    "$$U = \\frac{1}{\\sqrt{2}}\\left(\\begin{array}{cc}\n",
    "\\sigma_{N-1} \\Pi_X & \\sigma_{N-1} \\\\\n",
    "\\Pi_X \\sigma_{N-1} \\Pi_X & -\\Pi_X \\sigma_{N-1}\n",
    "\\end{array}\\right)$$\n",
    "\n",
    "Using properties of tensor product $\\otimes$, we can rewrite the above expression as\n",
    "\n",
    "$$U \n",
    "= \\frac{1}{\\sqrt{2}}\\left(\\begin{array}{cc}\n",
    "\\sigma_{N-1} \\Pi_X & \\sigma_{N-1} = \\\\\n",
    "\\Pi_X \\sigma_{N-1} \\Pi_X & -\\Pi_X \\sigma_{N-1}\n",
    "\\end{array}\\right) = \\\\\n",
    "= \\frac{1}{\\sqrt{2}}\\left(\\begin{array}{cc}\n",
    "\\Pi_I \\sigma_{N-1} \\Pi_X & \\Pi_I \\sigma_{N-1} \\Pi_I\\\\\n",
    "\\Pi_X \\sigma_{N-1} \\Pi_X & -\\Pi_X \\sigma_{N-1} \\Pi_I \\end{array}\\right) = \\\\\n",
    "= \\left(\\begin{array}{cc} \\Pi_I & 0 \\\\ 0 & \\Pi_X \\end{array}\\right)\n",
    "\\frac{1}{\\sqrt{2}}\\left(\\begin{array}{cc} \\sigma_{N-1} & \\sigma_{N-1} \\\\ \\sigma_{N-1} & -\\sigma_{N-1} \\end{array}\\right)\n",
    "\\left(\\begin{array}{cc} \\Pi_X & 0 \\\\ 0 & \\Pi_I \\end{array}\\right)\n",
    "$$\n",
    "\n",
    "The rightmost unitary $\\left(\\begin{array}{cc} \\Pi_X & 0 \\\\ 0 & \\Pi_I \\end{array}\\right)$ is actually a zero-controlled $X^{\\otimes N-1}$ gate; to make it a regular controlled $X$ gate we apply $X$ on the least significant qubit before and after transformation:\n",
    "\n",
    "$$U = \\left(\\begin{array}{cc} \\Pi_I & 0 \\\\ 0 & \\Pi_X \\end{array}\\right)\n",
    "\\frac{1}{\\sqrt{2}}\\left(\\begin{array}{cc} \\sigma_{N-1} & \\sigma_{N-1} \\\\ \\sigma_{N-1} & -\\sigma_{N-1} \\end{array}\\right)\n",
    "(X \\otimes I_{N-1}) \\left(\\begin{array}{cc} \\Pi_I & 0 \\\\ 0 & \\Pi_X \\end{array}\\right) (X \\otimes I_{N-1})$$\n",
    "\n",
    "We can rewrite the middle unitary $U'$ as\n",
    "\n",
    "$$U'=\\frac{1}{\\sqrt{2}}\\left(\\begin{array}{cc} \\sigma_{N-1} & \\sigma_{N-1} \\\\ \\sigma_{N-1} & -\\sigma_{N-1} \\end{array}\\right) = H \\otimes \\sigma_{N-1}$$\n",
    "\n",
    "Thus \n",
    "\n",
    "$$U=(CX^{\\otimes N-1})(H \\otimes \\sigma_{N-1})(X \\otimes I_{N-1})(CX^{\\otimes N-1})(X \\otimes I_{N-1})$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_TIE_Fighter \n",
    "\n",
    "operation TIE_Fighter (qs : Qubit[]) : Unit {\n",
    "    let n = Length(qs);\n",
    "    // the rightmost unitary: zero-controlled X gate\n",
    "    X(qs[n-1]);\n",
    "    ApplyToEach(CNOT(qs[n-1], _), qs[0..n-2]);\n",
    "    X(qs[n-1]);\n",
    "    // decrement operation\n",
    "    X(qs[0]);\n",
    "    for i in 1..Length(qs)-2 {\n",
    "        Controlled X (qs[0..i-1], qs[i]);\n",
    "    }\n",
    "    H(qs[n-1]);\n",
    "    // the leftmost unitary: controlled X gate\n",
    "    ApplyToEach(CNOT(qs[n-1], _), qs[0..n-2]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 13 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-13**.-TIE-fighter)"
   ]
  },
  {
   "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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> *There are shorter, more efficient methods for generating the required pattern. \n",
    "However, this method assumes minimum prior knowledge except the tasks in the workbook.*\n",
    "\n",
    "To create the \"Creeper\" unitary $U$, we start with \n",
    "$U'=\\begin{bmatrix} \n",
    "x & x & . & . & . & . & x & x \\\\\n",
    "x & x & . & . & . & . & x & x \\\\\n",
    ". & . & x & . & . & x & . & . \\\\\n",
    ". & . & . & x & x & . & . & . \\\\\n",
    ". & . & . & x & x & . & . & . \\\\\n",
    ". & . & x & . & . & x & . & . \\\\\n",
    "x & x & . & . & . & . & x & x \\\\\n",
    "x & x & . & . & . & . & x & x \\end{bmatrix} $.\n",
    "\n",
    "$U'$ has the same symmetry as task 13, which we can exploit to simplify $U'$. \n",
    "\n",
    "We label the bottom-right quarter of $U'$ as $V = \\begin{bmatrix} x & . & . & . \\\\ . & x & . & . \\\\ . & . & x & x \\\\ . & . & x & x \\end{bmatrix} $. \n",
    "We can implement the $V$ gate as the controlled $H$ gate. \n",
    "\n",
    "$$U'=\\left(\\begin{array}{cc} \\Pi_X & 0 \\\\ 0 & \\Pi_I \\end{array}\\right)\n",
    "\\frac{1}{\\sqrt{2}}\\left(\\begin{array}{cc} V & V \\\\ V & -V \\end{array}\\right)\n",
    "\\left(\\begin{array}{cc} \\Pi_X & 0 \\\\ 0 & \\Pi_I \\end{array}\\right) \n",
    "= (C^{-}X^{\\otimes 2})(H \\otimes V)(C^{-}X^{\\otimes 2})$$ \n",
    "\n",
    "The $C^{-}X^{\\otimes 2}$ means zero-controlled $X^{\\otimes 2}$ gate. \n",
    "\n",
    "After completing construction of the $U'$ gate, we now apply a cyclic rotation to the middle $4 \\times 4$ block:\n",
    "\n",
    "$$R'= \\begin{bmatrix} \n",
    "1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\end{bmatrix}$$\n",
    "\n",
    "$R'$ can be implemented using $3$ $X$ gates, $3$ $CNOT$ gates and $1$ $CCNOT$ gate. The transformation leaves outer $4$ computational states intact and shifts the inner $4$ computational states by 1.\n",
    "$$ R'U' = \\begin{bmatrix} \n",
    "1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\end{bmatrix}\n",
    "\\begin{bmatrix} \n",
    "\\frac{1}{2} & \\frac{1}{2} & 0 & 0 & 0 & 0 & \\frac{1}{2} & \\frac{1}{2} \\\\\n",
    "\\frac{1}{2} & \\frac{-1}{2} & 0 & 0 & 0 & 0 & \\frac{1}{2} & \\frac{-1}{2} \\\\\n",
    "0 & 0 & \\frac{1}{\\sqrt{2}} & 0 & 0 & \\frac{1}{\\sqrt{2}} & 0 & 0 \\\\\n",
    "0 & 0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} & 0 & 0 & 0 \\\\\n",
    "0 & 0 & \\frac{1}{\\sqrt{2}} & 0 & 0 & \\frac{-1}{\\sqrt{2}} & 0 & 0 \\\\\n",
    "\\frac{1}{2} & \\frac{1}{2} & 0 & 0 & 0 & 0 & \\frac{-1}{2} & \\frac{-1}{2} \\\\\n",
    "\\frac{1}{2} & \\frac{-1}{2} & 0 & 0 & 0 & 0 & \\frac{-1}{2} & \\frac{1}{2} \\end{bmatrix}\n",
    "= \\begin{bmatrix} \n",
    "\\frac{1}{2} & \\frac{1}{2} & 0 & 0 & 0 & 0 & \\frac{1}{2} & \\frac{1}{2} \\\\\n",
    "\\frac{1}{2} & \\frac{-1}{2} & 0 & 0 & 0 & 0 & \\frac{1}{2} & \\frac{-1}{2} \\\\\n",
    "0 & 0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} & 0 & 0 & 0 \\\\\n",
    "0 & 0 & \\frac{1}{\\sqrt{2}} & 0 & 0 & \\frac{-1}{\\sqrt{2}} & 0 & 0 \\\\\n",
    "0 & 0 & \\frac{1}{\\sqrt{2}} & 0 & 0 & \\frac{0}{\\sqrt{2}} & 0 & 0 \\\\\n",
    "\\frac{1}{2} & \\frac{1}{2} & 0 & 0 & 0 & 0 & \\frac{-1}{2} & \\frac{-1}{2} \\\\\n",
    "\\frac{1}{2} & \\frac{-1}{2} & 0 & 0 & 0 & 0 & \\frac{-1}{2} & \\frac{1}{2} \\end{bmatrix}$$\n",
    "\n",
    "We can see that $R'U'$ is the required pattern $U$: \n",
    "    $$U= R'U' = R'(C^{-}X^{\\otimes 2})(H \\otimes V)(C^{-}X^{\\otimes 2})$$\n",
    "     \n",
    "Now we have to implement $R'$\n",
    "\n",
    "$$R'= \\begin{bmatrix} \n",
    "1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\end{bmatrix}\n",
    "= \\begin{bmatrix} \n",
    "0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n",
    "1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\end{bmatrix}\n",
    "\\begin{bmatrix} \n",
    "1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n",
    "0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\end{bmatrix}\n",
    "\\begin{bmatrix} \n",
    "0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n",
    "1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\end{bmatrix} $$\n",
    "\n",
    "We observe that $R'$ is the product of 3 matrices, in which leftmost and rightmost are the adjoint of one-another. The matrix in the middle is a controlled \"increment by 1\" matrix. \n",
    "Let $W=\\begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 1 & 0 & 0 & 0 \\end{bmatrix}\n",
    "= \\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 \\end{bmatrix} \n",
    "\\begin{bmatrix} 0 & 1 & 0 & 0 \\\\ 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix}\n",
    "= CNOT'(I \\otimes X) $. \n",
    "Here the $CNOT'$ gate has least significant qubit as control and most significant qubit as target. \n",
    "\n",
    "Finally $R'= (W \\otimes I)(CW)(W \\otimes I)^{\\dagger}$, where $CW$ is the controlled version of the $W$ gate.\n",
    "\n",
    "> We'll need to use a separate cell to define two helper operations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// W unitary: decrements the basis states modulo 4\n",
    "operation W (qs : Qubit[]) : Unit is Adj + Ctl {\n",
    "    X(qs[0]);\n",
    "    CNOT(qs[0],qs[1]); // Control is LSB and Target is MSB \n",
    "}\n",
    "\n",
    "// R' unitary: performs rotation of the 4 middle basis vectors\n",
    "operation Rotation (qs : Qubit[]) : Unit {\n",
    "    Adjoint W(qs[1..2]);\n",
    "    Controlled W([qs[2]], qs[0..1]);\n",
    "    W(qs[1..2]);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_Creeper \n",
    "\n",
    "operation Creeper(qs : Qubit[]) : Unit {\n",
    "    X(qs[2]);\n",
    "    Controlled ApplyToEachCA([qs[2]], (X, qs[0 .. 1])); // Negatively Controlled Not Gates \n",
    "    X(qs[2]);\n",
    "    H(qs[2]);\n",
    "    Controlled H([qs[1]], qs[0]); // Central Transformation\n",
    "    X(qs[2]);\n",
    "    Controlled ApplyToEachCA([qs[2]], (X, qs[0 .. 1])); // Negatively Controlled Not Gates \n",
    "    X(qs[2]);\n",
    "    Rotation(qs); // Rotation\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 14 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-14**.-Creeper)"
   ]
  },
  {
   "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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "    \n",
    "Our strategy will be to implement a matrix with Hessenberg structure as a product of several unitary matrices that differ from the identity only in a $2\\times 2$ subblock. \n",
    "\n",
    "Let $i \\in \\{0, \\ldots, 2^n-2\\}$ denote an index. Consider operations of the form $T_N(i)$, where the $(i,i)$, $(i,i+1)$, $(i+1,i)$ and $(i+1,i+1)$ together form a $2 \\times 2$ square submatrix of non-zero entries (denoted by $*$):\n",
    "\n",
    "$$ T_N(i) = \\begin{bmatrix} \n",
    "1 &        &   &   &   &   &        &   \\\\\n",
    "  & \\ddots &   &   &   &   &        &   \\\\\n",
    "  &        & 1 &   &   &   &        &   \\\\\n",
    "  &        &   & * & * &   &        &   \\\\\n",
    "  &        &   & * & * &   &        &   \\\\\n",
    "  &        &   &   &   & 1 &        &   \\\\\n",
    "  &        &   &   &   &   & \\ddots &   \\\\\n",
    "  &        &   &   &   &   &        &   1 \\end{bmatrix}$$\n",
    "\n",
    "We can choose the Hadamard $H$ for creating the $2 \\times 2$ submatrix. \n",
    "\n",
    "> For example, for $N=3$ and $i=0$ we have \n",
    ">\n",
    ">$$ T_3(0) = \\begin{bmatrix} \n",
    "\\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "\\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\end{bmatrix}$$\n",
    "\n",
    "Such an operation can be mapped to a multiply-controlled gate by first permuting the rows and columns of the matrix. \n",
    "Specifically, we can map $i$ to the bit string $1 1 \\ldots 1 0$ and $i+1$ to the bit string $1 1 \\ldots 1 1 $. \n",
    "Then the resulting operation can be implemented by a multiply controlled $H$ gate with the last qubit as target and remaining qubits acting as controls.\n",
    "\n",
    "We now utilize the fact that a Hessenberg unitary $U_N$ can be factored as $ U_N = T_N(0) T_N(1) T_N(2) ... T_N(2^N-2)$. \n",
    "\n",
    "For the simple case of $N=2$, \n",
    "\n",
    "$$U_2 = T_2(0) T_2(1) T_2(2) = \\\\\n",
    "= \\begin{bmatrix} \n",
    "\\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} & 0 & 0 \\\\ \n",
    "\\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 \\\\ \n",
    "0 & 0 & 0 & 1 \\\\ \\end{bmatrix}\n",
    "\\begin{bmatrix} \n",
    "1 & 0 & 0 & 0 \\\\ \n",
    "0 & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} & 0 \\\\ \n",
    "0 & \\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} & 0 \\\\ \n",
    "0 & 0 & 0 & 1 \\\\\\end{bmatrix}\n",
    "\\begin{bmatrix} \n",
    "1 & 0 & 0 & 0 \\\\ \n",
    "0 & 1 & 0 & 0 \\\\ \n",
    "0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\ \n",
    "0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} \\\\ \\end{bmatrix} = \\\\\n",
    "= \\begin{bmatrix} \n",
    "\\frac{1}{\\sqrt{2}} & \\frac{1}{2} & \\frac{1}{2\\sqrt{2}} & \\frac{1}{2\\sqrt{2}} \\\\\n",
    "\\frac{1}{\\sqrt{2}} & \\frac{-1}{2} & \\frac{-1}{2\\sqrt{2}} & \\frac{-1}{2\\sqrt{2}} \\\\\n",
    "0 & \\frac{-1}{\\sqrt{2}} & \\frac{-1}{2} & \\frac{-1}{2} \\\\\n",
    "0 & 0 & \\frac{1}{\\sqrt{2}} & \\frac{-1}{\\sqrt{2}} \\end{bmatrix}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "// Performs a rotation to move basis states i to 111...10 and i+1 to 111...11 (in big endian notation)\n",
    "operation RotateToEnd (index: Int, qs : Qubit[]) : Unit is Adj{\n",
    "    let n = Length(qs);\n",
    "    let bits1 = IntAsBoolArray(index, n);\n",
    "    let bits2 = IntAsBoolArray(index + 1, n);\n",
    "    \n",
    "    let diff = 0; // The index of the first bit at which the bit strings are different is 0 (successive indexes)\n",
    "    // we care only about 2 inputs: basis state of bits1 and bits2\n",
    "    // make sure that the state corresponding to bits1 has qs[diff] set to 0\n",
    "    if bits1[diff] {\n",
    "        X(qs[diff]);\n",
    "    }\n",
    "    // iterate through the bit strings again, setting the final state of qubits\n",
    "    for i in 0 .. n-1 {\n",
    "        if bits1[i] == bits2[i] { // if two bits are the same, set both to 1 using X or nothing\n",
    "            if not bits1[i] {\n",
    "                X(qs[i]);\n",
    "            }\n",
    "        } else { // if two bits are different, set both to 1 using CNOT\n",
    "            if i > diff {\n",
    "                if not bits1[i] {\n",
    "                    X(qs[diff]);\n",
    "                    CNOT(qs[diff], qs[i]);\n",
    "                    X(qs[diff]);\n",
    "                }\n",
    "                if not bits2[i] {\n",
    "                    CNOT(qs[diff], qs[i]);\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    if diff < n-1 {\n",
    "        SWAP(qs[n-1], qs[diff]); // move the differing bit to the last qubit\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T15_Hessenberg_Matrix\n",
    "\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation Hessenberg_Matrix (qs : Qubit[]) : Unit {\n",
    "    let n = Length(qs);\n",
    "    for i in 2^n - 2 .. -1 .. 0{\n",
    "        RotateToEnd(i, qs);\n",
    "        (Controlled H)(Most(qs), Tail(qs));\n",
    "        (Adjoint RotateToEnd)(i, qs);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 15 of the Unitary Patterns kata.](./UnitaryPatterns.ipynb#Task-15**.-Hessenberg-matrices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "These exercises show you how to prepare certain unitary patterns using single-qubit and multi-qubit gates. These tricks, from representing larger matrices as tensor products of smaller matrices to permuting the rows and columns of matrices to make implementation easier, are widely used when implementing specific matrices required by more advanced algorithms."
   ]
  }
 ],
 "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
}