BasicGates/Workbook_BasicGates.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Basic Gates Kata Workbook\n",
    "\n",
    "**What is this workbook?** \n",
    "A workbook is a collection of problems, accompanied by solutions to them. 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 or for reinforcement. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n",
    "\n",
    "This workbook describes the solutions to the problems offered in the [Basic Gates Kata](./BasicGates.ipynb). \n",
    "Since the tasks are offered as programming problems, the explanations also cover some elements of Q# that might be non-obvious for a novitiate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**What you should know for this workbook**\n",
    "\n",
    "You should be familiar with the following concepts and associated techniques **prior to** beginning work on the Basic Gates Quantum Kata.\n",
    "\n",
    "1. [Complex numbers](../tutorials/ComplexArithmetic/ComplexArithmetic.ipynb).\n",
    "2. Basic linear algebra (multiplying column vectors by matrices), per the first part of [this tutorial](../tutorials/LinearAlgebra/LinearAlgebra.ipynb).\n",
    "3. [The concept of qubit and its properties](../tutorials/Qubit/Qubit.ipynb).\n",
    "4. [Single-qubit gates](../tutorials/SingleQubitGates/SingleQubitGates.ipynb).\n",
    "\n",
    "You can also consult the [complete Quantum Katas learning path](https://github.com/microsoft/QuantumKatas#learning-path)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1. Single-Qubit Gates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "## Task 1.1. State flip: $|0\\rangle$ to $|1\\rangle$ and vice versa\n",
    "\n",
    "**Input:** A qubit in state $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$.\n",
    "\n",
    "**Goal:**  Change the state of the qubit to $\\alpha |1\\rangle + \\beta |0\\rangle$.\n",
    "\n",
    "**Example:**\n",
    "\n",
    "If the qubit is in state $|0\\rangle$, change its state to $|1\\rangle$.\n",
    "\n",
    "If the qubit is in state $|1\\rangle$, change its state to $|0\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can recognize that the Pauli X gate will change the state $|0\\rangle$ to $|1\\rangle$ and vice versa, and $\\alpha |0\\rangle + \\beta |1\\rangle$ to $\\alpha |1\\rangle + \\beta |0\\rangle$.\n",
    "\n",
    "As a reminder, the Pauli X gate is defined by the following matrix:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "X = \n",
    "\\begin{bmatrix}\n",
    "   0 &  1\\\\\n",
    "  1 &  0\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "We can see how it affects, for example, the basis state $|0\\rangle$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$X|0\\rangle= \n",
    "\\begin{bmatrix}\n",
    "   0 &  1\\\\\n",
    "  1 &  0\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "   1\\\\\n",
    "   0\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "   0 \\cdot 1 + 1 \\cdot 0\\\\\n",
    "   1 \\cdot 1 + 0 \\cdot 0\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "   0\\\\\n",
    "   1\n",
    "\\end{bmatrix}\n",
    "=|1\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, we can consider the effect of the X gate on the superposition state $|\\psi\\rangle = 0.6|0\\rangle + 0.8|1\\rangle$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$X|\\psi\\rangle= \n",
    "\\begin{bmatrix}\n",
    "   0 &  1\\\\\n",
    "  1 &  0\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "   0.6\\\\\n",
    "   0.8\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "  0 \\cdot 0.6  + 1 \\cdot 0.8\\\\\n",
    "   1 \\cdot 0.6 + 0 \\cdot 0.8\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "   0.8\\\\\n",
    "   0.6\n",
    "\\end{bmatrix}\n",
    "=  0.8|0\\rangle + 0.6|1\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T101_StateFlip \n",
    "\n",
    "operation StateFlip (q : Qubit) : Unit is Adj+Ctl {\n",
    "    X(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.1 of the Basic Gates kata.](./BasicGates.ipynb#Task-1.1.-State-flip:-$|0\\rangle$-to-$|1\\rangle$-and-vice-versa)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Task 1.2. Basis change: $|0\\rangle$ to $|+\\rangle$ and $|1\\rangle$ to $|-\\rangle$ (and vice versa)\n",
    "\n",
    "**Input**: A qubit in state $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$.\n",
    "\n",
    "**Goal**:  Change the state of the qubit as follows:\n",
    "* If the qubit is in state $|0\\rangle$, change its state to $|+\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + |1\\rangle\\big)$.\n",
    "* If the qubit is in state $|1\\rangle$, change its state to $|-\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle - |1\\rangle\\big)$.\n",
    "* If the qubit is in superposition, change its state according to the effect on basis vectors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "We can recognize that the Hadamard gate changes states $|0\\rangle$ and $|1\\rangle$ to $|+\\rangle$ and $|-\\rangle$, respectively, and vice versa.\n",
    "\n",
    "As a reminder, the Hadamard gate is defined by the following matrix:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "$$\n",
    "\\frac{1}{\\sqrt{2}}\\begin{bmatrix}\n",
    "1 & 1 \\\\\n",
    "1 & -1\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "For example, we can work out $H|1\\rangle$ as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "$$\n",
    "H|1\\rangle=\n",
    "\\frac{1}{\\sqrt{2}}\\begin{bmatrix}\n",
    "   1 & 1 \\\\\n",
    "   1 & -1\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   0\\\\\n",
    "   1\\\\\n",
    "  \\end{bmatrix}\n",
    "=\n",
    "\\frac{1}{\\sqrt{2}}\\begin{bmatrix}\n",
    "   1 \\cdot 0 + 1 \\cdot 1 \\\\\n",
    "   1 \\cdot 0 + (-1) \\cdot 1\n",
    "  \\end{bmatrix}\n",
    "=\n",
    "  \\frac{1}{\\sqrt{2}}\\begin{bmatrix}\n",
    "   1\\\\\n",
    "   -1\n",
    "  \\end{bmatrix}\n",
    "= \\frac{1}{\\sqrt{2}} \\big(|0\\rangle - |1\\rangle\\big) = |-\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, we can consider the effect of the Hadamard gate on the superposition state $|\\psi\\rangle = 0.6|0\\rangle + 0.8|1\\rangle$ (rounding the numbers to 4 decimal places):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "H|\\psi⟩ = \n",
    "\\frac{1}{\\sqrt{2}}\\begin{bmatrix}\n",
    "   1 & 1 \\\\\n",
    "   1 & -1\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\beta\\\\\n",
    "  \\end{bmatrix}\n",
    " =\n",
    "\\frac{1}{\\sqrt{2}}\\begin{bmatrix}\n",
    "   \\alpha + \\beta\\\\\n",
    "   \\alpha - \\beta\\\\\n",
    "  \\end{bmatrix}\n",
    "= 0.7071\\begin{bmatrix}\n",
    "   1.4\\\\\n",
    "   -0.2\\\\\n",
    "  \\end{bmatrix}\n",
    "= \\begin{bmatrix}\n",
    "   0.98994\\\\\n",
    "   -0.14142\\\\\n",
    "  \\end{bmatrix}\n",
    "= 0.9899|0\\rangle - 0.1414|1\\rangle\n",
    " $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T102_BasisChange \n",
    "\n",
    "operation BasisChange (q : Qubit) : Unit is Adj+Ctl {\n",
    "    H(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.2 of the Basic Gates kata](./BasicGates.ipynb#Task-1.2.-Basis-change:-$|0\\rangle$-to-$|+\\rangle$-and-$|1\\rangle$-to-$|-\\rangle$-(and-vice-versa))."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1.3. Sign flip: $|+\\rangle$  to $|-\\rangle$  and vice versa.\n",
    "\n",
    "**Input**: A qubit in state $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$.\n",
    "\n",
    "**Goal** :  Change the qubit state to $\\alpha |0\\rangle - \\beta |1\\rangle$ (i.e. flip the sign of the $|1\\rangle$ component of the superposition).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The action of the Pauli Z gate is exactly what is required by this question.\n",
    "This gate leaves the sign of the $|0\\rangle$ component of the superposition unchanged but flips the sign of the $|1\\rangle$ component of the superposition.\n",
    "\n",
    "As a reminder, the Pauli Z gate is defined by the following matrix:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "Z = \n",
    " \\begin{bmatrix}\n",
    "   1 & 0\\\\\n",
    "   0 & -1\n",
    "  \\end{bmatrix}\n",
    " $$\n",
    " \n",
    "Let's see its effect on the only computational basis state that it changes, $|1\\rangle$:\n",
    "\n",
    "$$\n",
    "Z|1\\rangle =\n",
    " \\begin{bmatrix}\n",
    "   1 & 0\\\\\n",
    "   0 & -1\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   0\\\\\n",
    "   1\\\\\n",
    "  \\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "   1 \\cdot 0 + 0 \\cdot1\\\\\n",
    "   0 \\cdot 1 +  -1 \\cdot 1\\\\\n",
    "  \\end{bmatrix}\n",
    "=\n",
    " \\begin{bmatrix}\n",
    "   0\\\\\n",
    "   -1\\\\\n",
    "  \\end{bmatrix}\n",
    "=\n",
    " -\\begin{bmatrix}\n",
    "   0\\\\\n",
    "   1\\\\\n",
    "  \\end{bmatrix}\n",
    "= -|1\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general applying the Z gate to a single qubit superposition state $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$ gives"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "Z|\\psi\\rangle = \n",
    " \\begin{bmatrix}\n",
    "   1 & 0 \\\\\n",
    "   0 & -1\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\beta\\\\\n",
    "  \\end{bmatrix}\n",
    "  =\n",
    "\\begin{bmatrix}\n",
    "   1\\cdot\\alpha + 0\\cdot\\beta\\\\\n",
    "   0\\cdot\\alpha + -1\\cdot\\beta\\\\\n",
    "  \\end{bmatrix} \n",
    "  =\n",
    " \\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   -\\beta\\\\\n",
    "  \\end{bmatrix}  \n",
    "= \\alpha |0\\rangle -\\beta |1\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%kata T103_SignFlip\n",
    "\n",
    "operation SignFlip (q : Qubit) : Unit is Adj+Ctl {\n",
    "    Z(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.3 of the Basic Gates kata](./BasicGates.ipynb#Task-1.3.-Sign-flip:-$|+\\rangle$--to-$|-\\rangle$--and-vice-versa.)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Task 1.4. Amplitude change: $|0\\rangle$ to $\\cos{α} |0\\rangle + \\sin{α} |1\\rangle$.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. Angle α, in radians, represented as Double.\n",
    "2. A qubit in state $|\\psi\\rangle = \\beta |0\\rangle + \\gamma |1\\rangle$.\n",
    "\n",
    "**Goal:**  Change the state of the qubit as follows:\n",
    "- If the qubit is in state $|0\\rangle$, change its state to $\\cos{α} |0\\rangle + \\sin{α} |1\\rangle$.\n",
    "- If the qubit is in state $|1\\rangle$, change its state to $-\\sin{α} |0\\rangle + \\cos{α} |1\\rangle$.\n",
    "- If the qubit is in superposition, change its state according to the effect on basis vectors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can recognize that we need to use one of the rotation gates Rx, Ry, and Rz (named because they \"rotate\" the qubit state in the three dimensional space visualized as the Bloch sphere about the x, y, and z axes, respectively), since they involve angle parameters. Of these three gates, only Ry rotates the basis states $|0\\rangle$ and $|1\\rangle$ to have real amplitudes (the other two gates introduce complex coefficients).\n",
    "\n",
    "As a reminder, "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "R_{y}(\\theta) =\n",
    "\\begin{bmatrix}\n",
    "   \\cos \\frac{\\theta}{2} & -\\sin \\frac{\\theta}{2}\\\\\n",
    "   \\sin \\frac{\\theta}{2} & \\cos \\frac{\\theta}{2}\n",
    "  \\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see its effect on the $|0\\rangle$ state:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "R_y(\\theta)|0\\rangle =\n",
    "\\begin{bmatrix}\n",
    "   \\cos \\frac{\\theta}{2} & -\\sin \\frac{\\theta}{2}\\\\\n",
    "   \\sin \\frac{\\theta}{2} & \\cos \\frac{\\theta}{2}\n",
    "  \\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "   1\\\\\n",
    "   0\\\\\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "   \\cos \\frac{\\theta}{2}\\cdot1 - \\sin \\frac{\\theta}{2}\\cdot0\\\\\n",
    "   \\sin \\frac{\\theta}{2}\\cdot1 + \\cos \\frac{\\theta}{2}\\cdot0\n",
    "  \\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "   \\cos \\frac{\\theta}{2}\\\\\n",
    "   \\sin \\frac{\\theta}{2}\n",
    "  \\end{bmatrix}\n",
    "= \\cos\\frac{\\theta}{2} |0\\rangle + \\sin\\frac{\\theta}{2} |1\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that when applying a gate, you can tell what its matrix does to the basis states by looking at its columns: the first column of the matrix is the state into which it will transform the $|0\\rangle$ state, and the second column is the state into which it will transform the $|1\\rangle$ state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the example used by the testing harness we are given $\\beta = 0.6, \\gamma = 0.8$ and $\\alpha = 1.0471975511965976 = \\frac{\\pi}{3}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since $\\cos \\frac{\\pi}{3} = 0.5$  and $\\sin \\frac{\\pi}{3} = 0.8660$, working to 4 decimal places, we can compute:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "R_{y}(\\theta) |\\psi\\rangle\n",
    "=\n",
    " \\begin{bmatrix}\n",
    "   \\cos \\frac{\\theta}{2} & -\\sin \\frac{\\theta}{2}\\\\\n",
    "   \\sin \\frac{\\theta}{2} & \\cos \\frac{\\theta}{2}\n",
    "  \\end{bmatrix} \n",
    "  \\begin{bmatrix}\n",
    "   \\beta\\\\\n",
    "  \\gamma\n",
    " \\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "   cos \\frac{\\theta}{2}\\cdot\\beta - sin \\frac{\\theta}{2}\\cdot\\gamma\\\\\n",
    "   sin \\frac{\\theta}{2}\\cdot\\beta +cos \\frac{\\theta}{2}\\cdot\\gamma\n",
    "  \\end{bmatrix}\n",
    "=  \n",
    " \\begin{bmatrix}\n",
    "   0.6\\cdot\\cos \\frac{\\pi}{3} -0.8\\cdot\\sin \\frac{\\pi}{3}\\\\\n",
    "   0.6\\cdot\\sin \\frac{\\pi}{3} +0.8\\cdot\\cos \\frac{\\pi}{3}\n",
    "  \\end{bmatrix}\n",
    "=\n",
    " \\begin{bmatrix}\n",
    "   0.3 - 0.6928\\\\\n",
    "   0.5196 + 0.4\n",
    "  \\end{bmatrix}\n",
    "=\n",
    "  \\begin{bmatrix}\n",
    "   -0.3928\\\\\n",
    "    0.9196\n",
    "  \\end{bmatrix}\n",
    "$$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that we used $\\frac{\\theta}{2} = \\alpha$; this means that in the Q# code we need to pass the angle $\\theta = 2\\alpha$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T104_AmplitudeChange\n",
    "\n",
    "operation AmplitudeChange (alpha : Double, q : Qubit) : Unit is Adj+Ctl {\n",
    "    Ry(2.0 * alpha, q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.4 of the Basic Gates kata](./BasicGates.ipynb#Task-1.4.-Amplitude-change:-$|0\\rangle$-to-$\\cos{α}-|0\\rangle-+-\\sin{α}-|1\\rangle$.)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1.5. Phase flip\n",
    "\n",
    "**Input:** A qubit in state $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$.\n",
    "\n",
    "**Goal:** Change the qubit state to $\\alpha |0\\rangle + {\\color{red}i}\\beta |1\\rangle$ (add a relative phase $i$ to $|1\\rangle$ component of the superposition).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We can recognize that the S gate performs this particular relative phase addition to the $|1\\rangle$ basis state. As a reminder,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "S = \n",
    " \\begin{bmatrix}\n",
    "   1 & 0\\\\\n",
    "   0 & i\n",
    "  \\end{bmatrix}\n",
    " $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see the effect of this gate on the general superposition $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    " \\begin{bmatrix}\n",
    "   1 & 0 \\\\\n",
    "   0 & i\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\beta\\\\\n",
    "  \\end{bmatrix}\n",
    "  =\n",
    "\\begin{bmatrix}\n",
    "   1\\cdot\\alpha + 0\\cdot\\beta\\\\\n",
    "   0\\cdot\\alpha + i\\cdot\\beta\n",
    "  \\end{bmatrix} \n",
    "  =\n",
    " \\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   i\\beta\\\\\n",
    "  \\end{bmatrix}  \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is therefore easy to see that when $|\\psi\\rangle = 0.6|0\\rangle +  0.8|1\\rangle, S|\\psi\\rangle =  0.6|0\\rangle + 0.8i|1\\rangle$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T105_PhaseFlip\n",
    "\n",
    "operation PhaseFlip (q : Qubit) : Unit is Adj+Ctl {\n",
    "    S(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution 2\n",
    "\n",
    "See the next task, Phase Change, for an explanation of using R1 gate to implement the same transformation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T105_PhaseFlip\n",
    "\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation PhaseFlip (q : Qubit) : Unit is Adj+Ctl {\n",
    "    R1(0.5 * PI(), q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.5 of the Basic Gates kata](./BasicGates.ipynb#Task-1.5.-Phase-flip)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1.6. Phase change\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. Angle α, in radians, represented as Double.\n",
    "2. A qubit in state $|\\psi\\rangle = \\beta |0\\rangle + \\gamma |1\\rangle$.\n",
    "\n",
    "**Goal:**  Change the state of the qubit as follows:\n",
    "- If the qubit is in state $|0\\rangle$, don't change its state.\n",
    "- If the qubit is in state $|1\\rangle$, change its state to $e^{i\\alpha} |1\\rangle$.\n",
    "- If the qubit is in superposition, change its state according to the effect on basis vectors: $\\beta |0\\rangle + {\\color{red}{e^{i\\alpha}}} \\gamma |1\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "We know that:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "R1(\\alpha)\n",
    "= \n",
    " \\begin{bmatrix}\n",
    "   1 & 0\\\\\n",
    "   0 & \\color{red}{e^{i\\alpha}}\n",
    "  \\end{bmatrix}\n",
    " $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we have:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "R1(\\beta |0\\rangle + \\gamma |1\\rangle) = \n",
    " \\begin{bmatrix}\n",
    "   1 & 0 \\\\\n",
    "   0 & \\color{red}{e^{i\\alpha}}\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   \\beta\\\\\n",
    "   \\gamma\\\\\n",
    "  \\end{bmatrix}\n",
    "  =\n",
    "\\begin{bmatrix}\n",
    "   1.\\beta + 0.\\gamma\\\\\n",
    "   0.\\beta + {\\color{red}{e^{i\\alpha}}}\\gamma\n",
    "  \\end{bmatrix} \n",
    "  =\n",
    " \\begin{bmatrix}\n",
    "   \\beta\\\\\n",
    "   {\\color{red}{e^{i\\alpha}}}\\gamma\n",
    "  \\end{bmatrix}  \n",
    "  = \\beta |0\\rangle + {\\color{red}{e^{i\\alpha}}} \\gamma |1\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Note that the results produced by the test harness can be unexpected.\n",
    "If you run the kata several times and examine the output, you'll notice that success is signaled even though the corresponding amplitudes of the desired and actual states look very different.\n",
    ">\n",
    "> So what's going on? The full state simulator used in these tests performs the computations \"up to a global phase\", that is, sometimes the resulting state acquires a global phase that doesn't affect the computations or the measurement outcomes, but shows up in DumpMachine output. (You can read more about the global phase in the [Qubit tutorial](../tutorials/Qubit/Qubit.ipynb#Relative-and-Global-Phase).)\n",
    ">\n",
    "> For example, in one run you can get the desired state $(0.6000 + 0000i)|0\\rangle + (-0.1389 +0.7878i)|1\\rangle$ and the actual state $(-0.1042 + 0.5909i)|0\\rangle + (-0.7518 -0.2736i)|1\\rangle$.\n",
    "You can verify that the ratios of amplitudes of the respective basis states are equal: $\\frac{-0.1042 + 0.5909i}{0.6} = -0.173667 +0.984833 i = \\frac{-0.7518 -0.2736i}{-0.1389 +0.7878i}$, so the global phase acquired by the state is (-0.173667 +0.984833 i). \n",
    "You can also check that the absolute value of this multiplier is approximately 1, so it doesn't impact the measurement probabilities.\n",
    ">\n",
    "> The testing harness for this and the rest of the tasks checks that your solution implements the required transformation exactly, without introducing any global phase, so it shows up only in the helper output and does not affect the verification of your solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T106_PhaseChange\n",
    "\n",
    "operation PhaseChange (alpha : Double, q : Qubit) : Unit is Adj+Ctl {\n",
    "   R1(alpha, q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose now that $\\alpha = \\frac{\\pi}{2}$.\n",
    "Then $e^{i\\alpha}= \\cos\\frac{\\pi}{2} + i\\sin\\frac{\\pi}{2}$.\n",
    "And, since $\\cos\\frac{\\pi}{2}= 0$ and $\\sin\\frac{\\pi}{2} = 1$, then we have that $\\cos\\frac{\\pi}{2} + i \\sin\\frac{\\pi}{2} = i$, and  \n",
    "$R1(\\frac{\\pi}{2}) = S$, which we used in the second solution to task 1.5, above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.6 of the Basic Gates kata](./BasicGates.ipynb#Task-1.6.-Phase-Change)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1.7. Global phase change\n",
    "**Input:** A qubit in state $|\\psi\\rangle = \\beta |0\\rangle + \\gamma |1\\rangle$.\n",
    "\n",
    "**Goal**: Change the state of the qubit to $- \\beta |0\\rangle - \\gamma |1\\rangle$.\n",
    "\n",
    "> Note: this change on its own is not observable - there is no experiment you can do on a standalone qubit to figure out whether it acquired the global phase or not. \n",
    "> However, you can use a controlled version of this operation to observe the global phase it introduces. \n",
    "> This is used in later katas as part of more complicated tasks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We recognize that a global phase change can be accomplished by using the R rotation gate with the PauliI (identity) gate.\n",
    "As a reminder, the R gate is defined as $R_{\\mu}(\\theta) = \\exp(\\frac{\\theta}{2}i\\cdot\\sigma_{\\mu})$, where $\\sigma_{\\mu}$ is one of the Pauli gates I, X, Y or Z.  \n",
    "\n",
    "> Note that a global phase is not detectable and has no physical meaning - it disappears when you take a measurement of the state.  \n",
    "> You can read more about this in the [Single-qubit measurements tutorial](../tutorials/SingleQubitSystemMeasurements/SingleQubitSystemMeasurements.ipynb#Measurements-in-arbitrary-orthogonal-bases)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the problem at hand, we'll use the rotation gate $R_{\\mu}(\\theta) = \\exp(\\frac{\\theta}{2}i\\cdot\\sigma_{\\mu})$ with $\\sigma_{\\mu} = I$.  \n",
    "\n",
    "$R(PauliI, 2\\pi) = \\exp(\\frac{2\\pi}{2} iI) = \\exp(i\\pi) I = (\\cos\\pi + i\\sin\\pi) I$ and, since $\\cos\\pi = -1$   and   $\\sin\\pi = 0$, we have that $R(PauliI, 2\\pi) = -I$:   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "R(\\beta |0\\rangle + \\gamma |1\\rangle) \n",
    "=\n",
    " -1\\begin{bmatrix}\n",
    "   1 & 0 \\\\\n",
    "   0 & 1\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   \\beta\\\\\n",
    "   \\gamma\\\\\n",
    "  \\end{bmatrix}\n",
    "=\n",
    " \\begin{bmatrix}\n",
    "   -1 & 0 \\\\\n",
    "   0 & -1\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   \\beta\\\\\n",
    "   \\gamma\\\\\n",
    "  \\end{bmatrix} \n",
    "=\n",
    " \\begin{bmatrix}\n",
    "   -1\\cdot\\beta + 0\\cdot\\gamma\\\\\n",
    "    0\\cdot\\beta +  -1\\cdot\\gamma \\\\\n",
    "  \\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "   -\\beta\\\\\n",
    "   -\\gamma\\\\\n",
    "  \\end{bmatrix}\n",
    "=\n",
    "- \\beta |0\\rangle - \\gamma |1\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The test harness for this test shows the result of applying the *controlled* variant of your solution to be able to detect the phase change."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T107_GlobalPhaseChange\n",
    "\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation GlobalPhaseChange (q : Qubit) : Unit is Adj+Ctl {\n",
    "    R(PauliI, 2.0 * PI(), q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.7 of the Basic Gates kata](./BasicGates.ipynb#Task-1.7.-Global-phase-change)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1.8. Bell state change - 1\n",
    "\n",
    "**Input:** Two entangled qubits in Bell state $|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|00\\rangle + |11\\rangle\\big)$.\n",
    "\n",
    "**Goal:**  Change the two-qubit state to $|\\Phi^{-}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|00\\rangle - |11\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We recognize that the goal is another Bell state. In fact, it is one of the four Bell states.\n",
    "\n",
    "We remember from Task 1.3 that the Pauli Z gate will change the state of the $|0\\rangle$ basis state of a single qubit, so this gate seems like a good candidate for what we want to achieve. This gate leaves the sign of the $|0\\rangle$ basis state of a superposition unchanged, but flips the sign of the $|1\\rangle$ basis state of the superposition.  \n",
    "\n",
    "Don't forget that the Z gate acts on only a single qubit, and we have two here.\n",
    "Lets also remember how the Bell state is made up from its individual qubits.\n",
    "\n",
    "If the two qubits are A and B, where A is `qs[0]` and B is `qs[1]`, we can write that\n",
    "$|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0_{A}0_{B}\\rangle + |1_{A}1_{B}\\rangle\\big)$,  and also remember that this is a superposition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we apply the Z gate to the qubit A, it will flip the phase of the basis state $|1_A\\rangle$. As this phase is in a sense spread across the entangled state, with $|1_A\\rangle$ basis state being part of the second half of the superposition, this  application has the effect of flipping the sign of the whole basis state $|1_A1_B\\rangle$, as you can see by running the solution below.  \n",
    "\n",
    "> If you run the solution below several times, you will notice that you get the state $\\frac{1}{\\sqrt{2}} \\big(-|00\\rangle + |11\\rangle\\big)$ at a guess as frequently as the goal state. Here is why.  \n",
    "> \n",
    "> We can write this second state as   $-\\frac{1}{\\sqrt{2}} \\big(|00\\rangle -|11\\rangle\\big)$ = $(-1)\\frac{1}{\\sqrt{2}} \\big(|00\\rangle - |11\\rangle\\big)$. \n",
    "This state is the same as our goal state $|\\Phi^{-}\\rangle$ with an unmeasurable global phase of $-1$.\n",
    "\n",
    "The exact same calculations can be done if we apply Z to the qubit B, so that's another possible solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T108_BellStateChange1\n",
    "\n",
    "operation BellStateChange1 (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    Z(qs[0]); // or Z(qs[1]); \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.8 of the Basic Gates kata](./BasicGates.ipynb#Task-1.8.-Bell-state-change---1)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1.9. Bell state change - 2\n",
    "\n",
    "**Input:** Two entangled qubits in Bell state $|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|00\\rangle + |11\\rangle\\big)$.\n",
    "\n",
    "**Goal:**  Change the two-qubit state to $|\\Psi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|01\\rangle + |10\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution ##\n",
    "We have seen in Task 1.1 that the Pauli X gate flips $|0\\rangle$ to $|1\\rangle$ and vice versa, and as we seem to need some flipping of states, perhaps this gate may be of use. (Bearing in mind, of course, that the X gate operates on a single qubit). \n",
    "\n",
    "Let's compare the starting state $\\frac{1}{\\sqrt{2}} \\big(|0_A0_B\\rangle + |1_A1_B\\rangle\\big)$ with the goal state $\\frac{1}{\\sqrt{2}} \\big(1_A0_B\\rangle + |0_A1_B\\rangle\\big)$ term by term and see how we need to transform it to reach the goal.\n",
    "\n",
    "Using our nomenclature from Task 1.8, we can now see by comparing terms that $|0_{A}\\rangle$ has flipped to $|1_A\\rangle$ to get the first term, and $|1_{A}\\rangle$ has flipped to $|0\\rangle$ to get the second term. This allows us to say that the correct gate to use is Pauli X, applied to `qs[0]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T109_BellStateChange2\n",
    "\n",
    "operation BellStateChange2 (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    X(qs[0]); // or X(qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.9 of the Basic Gates kata](./BasicGates.ipynb#Task-1.9.-Bell-state-change---2)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1.10. Bell state change - 3\n",
    "\n",
    "**Input:** Two entangled qubits in Bell state $|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|00\\rangle + |11\\rangle\\big)$.\n",
    "\n",
    "**Goal:**  Change the two-qubit state, without adding a global phase, to $|\\Psi^{-}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|01\\rangle - |10\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution ##\n",
    "We remember from Task 1.3 that the Pauli-Z gate leaves the sign of the $|0\\rangle$ component of the single qubit superposition unchanged but flips the sign of the $|1\\rangle$ component of the superposition. We have also just seen in Task 1.9 how to change our input state to the state $\\frac{1}{\\sqrt{2}} \\big(|01\\rangle + |10\\rangle\\big)$, which is almost our goal state (disregarding the phase change for the moment). So it would seem that a combination of these two gates will be what we need here. The remaining question is in what order to apply them, and to which qubit.\n",
    "\n",
    "First of all, which qubit? Looking back at Task 1.9, it seems clear that we need to use qubit `qs[0]`, like we did there.\n",
    "\n",
    "Second, in what order should we apply the gates? Remember that the Pauli-Z gate flips the phase of the $|1\\rangle$ component of the superposition and leaves the $|0\\rangle$ component alone.   \n",
    "Let's experiment with applying X to `qs[0]` first. Looking at our \"halfway answer\" state $\\frac{1}{\\sqrt{2}} \\big(|01\\rangle + |10\\rangle\\big)$, we can see that if we apply the Z gate to `qs[0]`, it will leave the $|0_{A}\\rangle$ alone but flip the phase of $|1_{A}\\rangle$ to $-|1_{A}\\rangle$, thus flipping the phase of the $|11\\rangle$ component of our  Bell state.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T110_BellStateChange3\n",
    "\n",
    "operation BellStateChange3 (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    X(qs[0]);\n",
    "    Z(qs[0]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 1.10 of the Basic Gates kata](./BasicGates.ipynb#Task-1.10.-Bell-state-change---3)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part II. Multi-Qubit Gates\n",
    "\n",
    "## Task 2.1. Two-qubit gate - 1\n",
    "\n",
    "**Input:** Two unentangled qubits (stored in an array of length 2).\n",
    "The first qubit will be in state $|\\psi\\rangle = \\alpha |0\\rangle + \\beta |1\\rangle$, the second - in state $|0\\rangle$\n",
    "(this can be written as two-qubit state  $\\big(\\alpha |0\\rangle + \\beta |1\\rangle \\big) \\otimes |0\\rangle = \\alpha |00\\rangle + \\beta |10\\rangle$.\n",
    "\n",
    "**Goal:**  Change the two-qubit state to $\\alpha |00\\rangle + \\beta |11\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "Let's denote the first qubit in state $\\alpha |0\\rangle + \\beta |1\\rangle$ as A and the second qubit in state $|0\\rangle$ as B.\n",
    "\n",
    "Compare our input state $\\alpha |0_A0_B\\rangle + \\beta |1_A0_B\\rangle$ with the goal state $\\alpha |0_A0_B\\rangle + \\beta |1_A1_B\\rangle$. \n",
    "We want to pass our input qubit through a gate or gates (to be decided) that do the following. If qubit A is in the $|0\\rangle$ state, then we want to leave qubit B alone (the first term of the superposition). \n",
    "However, if A is in the $|1\\rangle$ state, we want to flip qubit B from $|0\\rangle$ into $|1\\rangle$ state. In other words, the state of B is to be made contingent upon the state of A. \n",
    "This gate exists and is called a CNOT (controlled-not) gate. Depending upon the state of the **control** qubit (A in our case), the value of the controlled or **target** qubit (B in our case) is inverted or unchanged.  Thus we get the goal state $\\alpha |00\\rangle + \\beta |11\\rangle$.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T201_TwoQubitGate1\n",
    "\n",
    "operation TwoQubitGate1 (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    CNOT(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.1 of the Basic Gates kata](./BasicGates.ipynb#Task-2.1.-Two-qubit-gate---1)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2.2. Two-qubit gate - 2\n",
    "\n",
    "**Input:** Two unentangled qubits (stored in an array of length 2) in state $|+\\rangle \\otimes |+\\rangle = \\frac{1}{2} \\big( |00\\rangle + |01\\rangle + |10\\rangle {\\color{blue}+} |11\\rangle \\big)$.\n",
    "\n",
    "\n",
    "**Goal:**  Change the two-qubit state to $\\frac{1}{2} \\big( |00\\rangle + |01\\rangle + |10\\rangle {\\color{red}-} |11\\rangle \\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "Firstly we notice that we are dealing with an unentangled pair of qubits. In vector form this is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In vector form the transformation we need is \n",
    "$$\\frac{1}{2}\n",
    "\\begin{bmatrix}\n",
    "   1\\\\\n",
    "   1\\\\\n",
    "   1\\\\\n",
    "   1\\\\\n",
    "\\end{bmatrix} \\rightarrow \n",
    "\\frac{1}{2}\n",
    "\\begin{bmatrix}\n",
    "   1\\\\\n",
    "   1\\\\\n",
    "   1\\\\\n",
    "   -1\\\\\n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All that needs to happen to change the input into the goal is that the $|11\\rangle$ basis state needs to have its sign flipped. \n",
    "\n",
    "We remember that the Pauli Z gate flips signs in the single qubit case, so we need to investigate if there is a 2-qubit version of this gate that we can use here. We can also recall task 1.6 which dealt with phase shifts and, remembering that $e^{i\\cdot\\pi} = -1$, we can think of the transformation we're looking for as a phase shift.\n",
    "It can be useful to investigate a general case and then use it to perform a specific state change, so let's look for a 2-qubit variant of the phase shift. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly to task 2.1, the phase shift only occurs on one of the basis states, so this suggests it might be a conditional shift. If we could have our phase shift applied to `qs[1]` conditional on `qs[0]` being in the state $|1\\rangle$, then we would have a description of our gate. If we now look though a list of gates in the [Single-qubit gates tutorial](../tutorials/SingleQubitGates/SingleQubitGates.ipynb), we'll find the R1 phase shift gate with angle parameter $\\theta$ (radians), defined as\n",
    "\n",
    "$$\n",
    "R1(\\alpha)\n",
    "= \n",
    " \\begin{bmatrix}\n",
    "   1 & 0\\\\\n",
    "   0 & \\color{red}{e^{i\\alpha}}\n",
    "  \\end{bmatrix}\n",
    " $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The controlled variant of this gate will look like this:\n",
    "$$\n",
    "CR1(\\alpha) = \n",
    " \\begin{bmatrix}\n",
    "   1 & 0 & 0 & 0\\\\\n",
    "   0 & 1 & 0 & 0\\\\\n",
    "   0 & 0 & 1 & 0\\\\\n",
    "   0 & 0 & 0 &\\color{red}{e^{i\\alpha}}\n",
    "  \\end{bmatrix}\n",
    " $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This gate is almost Pauli I, the identity gate, with the different in just the last column, showing what will happen to the $|11\\rangle$ basis state. Applying it to our input state for $\\alpha = \\pi$, we'll get:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\frac{1}{2}\n",
    " \\begin{bmatrix}\n",
    "   1 & 0 & 0 & 0\\\\\n",
    "   0 & 1 & 0 & 0\\\\\n",
    "   0 & 0 & 1 & 0\\\\\n",
    "   0 & 0 & 0 &\\color{red}{e^{i\\alpha}}\n",
    "  \\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "   1\\\\\n",
    "   1\\\\\n",
    "   1\\\\\n",
    "   1\\\\\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\frac{1}{2}\n",
    "\\begin{bmatrix}\n",
    "   1\\\\\n",
    "   1\\\\\n",
    "   1\\\\\n",
    "   1\\cdot\\color{red}{e^{i\\alpha}}\\\\\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\frac{1}{2} \\big( |00\\rangle + |01\\rangle + |10\\rangle {\\color{red}-} |11\\rangle \\big)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The last thing we notice if we look through the [list of operations in the Microsoft.Quantum.Canon namespace](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.canon) is the CZ (Controlled Z) gate, a special case of CR1 that implements exactly this gate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%kata T202_TwoQubitGate2\n",
    "\n",
    "operation TwoQubitGate2 (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    CZ(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, we can express this gate using the intrinsic gate Z and its controlled variant using the Controlled functor:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T202_TwoQubitGate2\n",
    "\n",
    "operation TwoQubitGate2 (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    Controlled Z([qs[0]], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.2 of the Basic Gates kata](./BasicGates.ipynb#Task-2.2.-Two-qubit-gate---2)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2.3. Two-qubit gate - 3\n",
    "\n",
    "**Input:** Two qubits (stored in an array of length 2) in an arbitrary two-qubit state $\\alpha |00\\rangle + {\\color{blue}\\beta} |01\\rangle + {\\color{blue}\\gamma} |10\\rangle + \\delta |11\\rangle$.\n",
    "\n",
    "\n",
    "**Goal:**  Change the two-qubit state to $\\alpha |00\\rangle + {\\color{red}\\gamma} |01\\rangle + {\\color{red}\\beta} |10\\rangle + \\delta |11\\rangle$.\n",
    "\n",
    "> This task can be solved using one intrinsic gate; as an exercise, try to express the solution using several (possibly controlled) Pauli gates."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "A visual comparison of the two states easily reveals that the amplitudes of the $|01\\rangle$ and the $|01\\rangle$ components of the state have been swapped. This suggests that we might look for a swap gate that operates on 2 qubits, by changing the components of the 2 qubits to which the amplitudes are 'attached'.\n",
    "\n",
    "Let's investigate the first possibility. There is a swap gate that might fit the bill; its matrix representation is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "SWAP = \n",
    " \\begin{bmatrix}\n",
    "   1 & 0 & 0 & 0\\\\\n",
    "   0 & 0 & 1 & 0\\\\\n",
    "   0 & 1 & 0 & 0\\\\\n",
    "   0 & 0 & 0 & 1\\\\\n",
    "  \\end{bmatrix}\n",
    " $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and our input state vector is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\beta\\\\\n",
    "   \\gamma\\\\\n",
    "   \\delta\\\\\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So operating on our input state vector with the SWAP gate gives us"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    " \\begin{bmatrix}\n",
    "   1 & 0 & 0 & 0\\\\\n",
    "   0 & 0 & 1 & 0\\\\\n",
    "   0 & 1 & 0 & 0\\\\\n",
    "   0 & 0 & 0 & 1\\\\\n",
    "  \\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\color{blue}\\beta\\\\\n",
    "   \\color{blue}\\gamma\\\\\n",
    "   \\delta\\\\\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\color{red}\\gamma\\\\\n",
    "   \\color{red}\\beta\\\\\n",
    "   \\delta\\\\\n",
    "\\end{bmatrix}\n",
    "=\n",
    "|00\\rangle + {\\color{red}\\gamma} |01\\rangle + {\\color{red}\\beta} |10\\rangle + \\delta |11\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and we can confirm this with the task solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T203_TwoQubitGate3\n",
    "\n",
    "operation TwoQubitGate3 (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    SWAP(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> If you run this solution a few times you might see an apparent anomaly. The test harness uses an input state that has positive values of $\\alpha$ and $\\delta$ and negative values of $\\beta$ and $\\gamma$, while\n",
    "the \"actual state\" reported (the state prepared by your solution) can come out with negative values of $\\alpha$ and $\\delta$ and positive values of $\\beta$ and $\\gamma$. \n",
    "We have seen this before in the previous tasks: we can write the apparently anomalous state as $(-1)(\\alpha|00\\rangle + \\beta |01\\rangle + \\gamma |10\\rangle + \\delta |11\\rangle)$ and see that it differs from the goal state by a global phase of $\\pi$ (remember that $e^{i\\pi}=-1$). This doesn't mean that your implementation introduced this phase; sometimes the full state simulator used in the test harness produces a global phase in its calculations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now  follow the hint in the question and try to express the solution using several (possibly controlled) Pauli gates.\n",
    "\n",
    "If we look at the available cotrolled gates, CR and its special case CZ produce rotations, and that's not really what we want. So perhaps we are being pointed towards CNOT? If we carefully compare the input with the goal state, we see that the bits in the two basis states of the two qubits are being flipped, which results in a swap. What we need to do is to turn $|01\\rangle$ into $|10\\rangle$ and $|10\\rangle$ into $|01\\rangle$ while leaving the other two basis states unchanged.\n",
    "\n",
    "With some experimentation with sequences of CNOT gates we can arrive at the following sequence of transformations:\n",
    "\n",
    "<table>\n",
    "  <col width=\"150\"/>\n",
    "  <col width=\"150\"/>\n",
    "  <col width=\"150\"/>\n",
    "  <col width=\"150\"/>\n",
    "  <tr>\n",
    "    <th style=\"text-align:center\">Starting state</th>\n",
    "    <th style=\"text-align:center\">After CNOT$_{01}$</th>\n",
    "    <th style=\"text-align:center\">After CNOT$_{10}$</th>\n",
    "    <th style=\"text-align:center\">After CNOT$_{01}$</th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|00\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|00\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|00\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|00\\rangle$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|01\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|01\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|11\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|10\\rangle$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|10\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|11\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|01\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|01\\rangle$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|11\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|10\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|10\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|11\\rangle$</td>\n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T203_TwoQubitGate3\n",
    "\n",
    "operation TwoQubitGate3 (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    CNOT(qs[0], qs[1]);\n",
    "    CNOT(qs[1], qs[0]);\n",
    "    CNOT(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.3 of the Basic Gates kata](./BasicGates.ipynb#Task-2.3.-Two-qubit-gate---3)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2.4. Two-qubit gate - 4\n",
    "\n",
    "**Input:** Two qubits (stored in an array of length 2) in an arbitrary two-qubit state ${\\color{blue}\\alpha} |00\\rangle + {\\color{blue}\\beta} |01\\rangle + \\gamma |10\\rangle + \\delta |11\\rangle$.\n",
    "\n",
    "\n",
    "**Goal:**  Change the two-qubit state to ${\\color{red}\\beta} |00\\rangle + {\\color{red}\\alpha} |01\\rangle + \\gamma |10\\rangle + \\delta |11\\rangle$.\n",
    "\n",
    "> This task can be solved using one library function; as an exercise, try to express the solution using several (possibly controlled) Pauli gates.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution 1 - using intrinsic gates\n",
    "\n",
    "In vector form the transformation we need is:\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "   \\color{blue}\\alpha\\\\\n",
    "   \\color{blue}\\beta\\\\\n",
    "   \\gamma\\\\\n",
    "   \\delta\\\\\n",
    "\\end{bmatrix}\n",
    "\\rightarrow\n",
    "\\begin{bmatrix}\n",
    "   \\color{red}\\beta\\\\\n",
    "   \\color{red}\\alpha\\\\\n",
    "   \\gamma\\\\\n",
    "   \\delta\\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "This can be represented by a matrix:\n",
    "$$\n",
    "U = \\begin{bmatrix}\n",
    "   0 & 1 & 0 & 0\\\\\n",
    "   1 & 0 & 0 & 0\\\\\n",
    "   0 & 0 & 1 & 0\\\\\n",
    "   0 & 0 & 0 & 1\\\\\n",
    "  \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "We remember a two-qubit gate with a similar matrix representation - the CNOT gate:\n",
    "\n",
    "$$\n",
    "\\text{CNOT} = \n",
    " \\begin{bmatrix}\n",
    "   1 & 0 & 0 & 0\\\\\n",
    "   0 & 1 & 0 & 0\\\\\n",
    "   0 & 0 & 0 & 1\\\\\n",
    "   0 & 0 & 1 & 0\\\\\n",
    " \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "We need a way to transform the $\\text{CNOT}$ gate into the unitary transformation represented by $U$.   \n",
    "We remember that the Pauli X gate flips the state in the single-qubit case. Here we need to use a 2-qubit version of this gate, which would affect only the second qubit. We conclude, that the idenity gate needs to be used on the first qubit. In the end, the required gate is a tensor product: $I \\otimes X$.\n",
    "\n",
    "We validate that composition of $I \\otimes X$ and the $\\text{CNOT}$ gate produces the required unitary transformation represented by $U$. \n",
    "\n",
    "$$\n",
    " (I \\otimes X)\\cdot \\text{CNOT} =  \\left(\\begin{bmatrix}\n",
    "   1 & 0 \\\\\n",
    "   0 & 1 \\\\\n",
    "  \\end{bmatrix}\n",
    "  \\otimes\n",
    "   \\begin{bmatrix}\n",
    "   0 & 1 \\\\\n",
    "   1 & 0 \\\\\n",
    "  \\end{bmatrix}\\right) \\cdot\n",
    "  \\begin{bmatrix}\n",
    "   1 & 0 & 0 & 0\\\\\n",
    "   0 & 1 & 0 & 0\\\\\n",
    "   0 & 0 & 0 & 1\\\\\n",
    "   0 & 0 & 1 & 0\\\\\n",
    "  \\end{bmatrix}\n",
    "  =\n",
    "  \\begin{bmatrix}\n",
    "   0 & 1 & 0 & 0\\\\\n",
    "   1 & 0 & 0 & 0\\\\\n",
    "   0 & 0 & 0 & 1\\\\\n",
    "   0 & 0 & 1 & 0\\\\\n",
    "  \\end{bmatrix}\n",
    "  \\begin{bmatrix}\n",
    "   1 & 0 & 0 & 0\\\\\n",
    "   0 & 1 & 0 & 0\\\\\n",
    "   0 & 0 & 0 & 1\\\\\n",
    "   0 & 0 & 1 & 0\\\\\n",
    "  \\end{bmatrix}\n",
    "  =\n",
    " \\begin{bmatrix}\n",
    "   0 & 1 & 0 & 0\\\\\n",
    "   1 & 0 & 0 & 0\\\\\n",
    "   0 & 0 & 1 & 0\\\\\n",
    "   0 & 0 & 0 & 1\\\\\n",
    "  \\end{bmatrix} = U\n",
    "$$\n",
    "\n",
    "> Note that the order in which the gates $I \\otimes X$ and $\\text{CNOT}$ are applied doesn't matter in this case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T204_TwoQubitGate4\n",
    "\n",
    "operation TwoQubitGate4 (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    X(qs[1]);\n",
    "    CNOT(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution 2 - using a library function\n",
    "\n",
    "We observe that the task requires application of a Pauli X gate on the second qubit when the first qubit is in the $|0\\rangle$ state. This can be achieved with [`ControlledOnInt`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint) library function.\n",
    "\n",
    "> Notice that the `ControlledOnInt` function creates a gate controlled by a register - not by a single qubit. A similar function `ControlledOnBitString` is introduced in the [Multi-Qubit Gates tutorial](../tutorials/MultiQubitGates/MultiQubitGates.ipynb#Other-Types-of-Controlled-Gates)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T204_TwoQubitGate4\n",
    "\n",
    "operation TwoQubitGate4 (qs : Qubit[]) : Unit is Adj+Ctl {    \n",
    "    ControlledOnInt(0, X)([qs[0]], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.4 of the Basic Gates kata](./BasicGates.ipynb#Task-2.4.-Two-qubit-gate---4)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2.5. Toffoli gate\n",
    "\n",
    "**Input:** Three qubits (stored in an array of length 3) in an arbitrary three-qubit state \n",
    "$\\alpha |000\\rangle + \\beta |001\\rangle + \\gamma |010\\rangle + \\delta |011\\rangle + \\epsilon |100\\rangle + \\zeta|101\\rangle + {\\color{blue}\\eta}|110\\rangle + {\\color{blue}\\theta}|111\\rangle$.\n",
    "\n",
    "**Goal:** Flip the state of the third qubit if the state of the first two is $|11\\rangle$, i.e., change the three-qubit state to $\\alpha |000\\rangle + \\beta |001\\rangle + \\gamma |010\\rangle + \\delta |011\\rangle + \\epsilon |100\\rangle + \\zeta|101\\rangle + {\\color{red}\\theta}|110\\rangle + {\\color{red}\\eta}|111\\rangle$.\n",
    "\n",
    "### Solution\n",
    "\n",
    "This is essentially bookwork, because there is only one gate that performs this state change (and the task title already gave it away!) The Toffoli gate is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\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 & 1 & 0 & 0 & 0\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\\\\n",
    "  \\end{bmatrix}\n",
    " $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and our initial state is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\beta\\\\\n",
    "   \\gamma\\\\\n",
    "   \\delta\\\\\n",
    "   \\epsilon\\\\\n",
    "   \\zeta\\\\\n",
    "   \\eta\\\\\n",
    "   \\theta\\\\       \n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we have:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\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 & 1 & 0 & 0 & 0\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\\\\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\beta\\\\\n",
    "   \\gamma\\\\\n",
    "   \\delta\\\\\n",
    "   \\epsilon\\\\\n",
    "   \\zeta\\\\\n",
    "   \\color{blue}\\eta\\\\\n",
    "   \\color{blue}\\theta\\\\       \n",
    "\\end{bmatrix}\n",
    "=\n",
    " \\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\beta\\\\\n",
    "   \\gamma\\\\\n",
    "   \\delta\\\\\n",
    "   \\epsilon\\\\\n",
    "   \\zeta\\\\\n",
    "   \\color{red}\\theta\\\\\n",
    "   \\color{red}\\eta\\\\       \n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\alpha |000\\rangle + \\beta |001\\rangle + \\gamma |010\\rangle + \\delta |011\\rangle + \\epsilon |100\\rangle + \\zeta|101\\rangle + {\\color{red}\\theta}|110\\rangle + {\\color{red}\\eta}|111\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T205_ToffoliGate\n",
    "\n",
    "operation ToffoliGate (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    CCNOT(qs[0], qs[1], qs[2]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.5 of the Basic Gates kata](./BasicGates.ipynb#Task-2.5.-Toffoli-gate)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2.6. Fredkin gate\n",
    "\n",
    "**Input:** Three qubits (stored in an array of length 3) in an arbitrary three-qubit state \n",
    "$\\alpha |000\\rangle + \\beta |001\\rangle + \\gamma |010\\rangle + \\delta |011\\rangle + \\epsilon |100\\rangle + {\\color{blue}\\zeta}|101\\rangle + {\\color{blue}\\eta}|110\\rangle + \\theta|111\\rangle$.\n",
    "\n",
    "**Goal:** Swap the states of second and third qubit if and only if the state of the first qubit is $|1\\rangle$, i.e., change the three-qubit state to $\\alpha |000\\rangle + \\beta |001\\rangle + \\gamma |010\\rangle + \\delta |011\\rangle + \\epsilon |100\\rangle + {\\color{red}\\eta}|101\\rangle + {\\color{red}\\zeta}|110\\rangle + \\theta|111\\rangle$.\n",
    "\n",
    "\n",
    "### Solution\n",
    "\n",
    "Again this is essentially bookwork, because there is only one gate that performs this state change (and the task title already gave it away!)  \n",
    "The Fredkin gate is also known as the controlled swap gate (Controlled SWAP):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\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 & 1 & 0 & 0 & 0\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\\\\n",
    "  \\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and our initial state is:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\beta\\\\\n",
    "   \\gamma\\\\\n",
    "   \\delta\\\\\n",
    "   \\epsilon\\\\\n",
    "   \\zeta\\\\\n",
    "   \\eta\\\\\n",
    "   \\theta\\\\       \n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we have:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\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 & 1 & 0 & 0 & 0\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\\\\n",
    "  \\end{bmatrix}\n",
    " \\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\beta\\\\\n",
    "   \\gamma\\\\\n",
    "   \\delta\\\\\n",
    "   \\epsilon\\\\\n",
    "  \\color{blue} \\zeta\\\\\n",
    "  \\color{blue} \\eta\\\\\n",
    "   \\theta\\\\       \n",
    "\\end{bmatrix}\n",
    "=\n",
    " \\begin{bmatrix}\n",
    "   \\alpha\\\\\n",
    "   \\beta\\\\\n",
    "   \\gamma\\\\\n",
    "   \\delta\\\\\n",
    "   \\epsilon\\\\\n",
    "  \\color{red} \\eta\\\\\n",
    "  \\color{red} \\zeta\\\\\n",
    "   \\theta\\\\       \n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\alpha |000\\rangle + \\beta |001\\rangle + \\gamma |010\\rangle + \\delta |011\\rangle + \\epsilon |100\\rangle + {\\color{red}\\eta}|101\\rangle + {\\color{red}\\zeta}|110\\rangle + \\theta|111\\rangle\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice carefully how the qubits are passed to the gate: `[qs[0]], (qs[1], [qs[2])`. The `Controlled` functor produces an operation that takes two parameters: the first one is an array of control qubits (in this case a single-element array consisting of the first qubit), and the second parameter is a tuple of all parameters you'd pass to the original gate (in this gate two single-qubit parameters that would be arguments to a SWAP gate)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T206_FredkinGate\n",
    "\n",
    "operation FredkinGate (qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    Controlled SWAP([qs[0]], (qs[1], qs[2]));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to Task 2.6 of the Basic Gates kata](./BasicGates.ipynb#Task-2.6.-Fredkin-gate)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.24"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}