tutorials/MultiQubitGates/MultiQubitGates.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multi-Qubit Gates\n",
    "\n",
    "This tutorial continues the introduction to quantum gates started in [this tutorial](../SingleQubitGates/SingleQubitGates.ipynb), focusing on applying quantum gates to multi-qubit systems. \n",
    "\n",
    "If you need a refresher on the representation of multi-qubit systems, we recommend you to review the [relevant tutorial](../MultiQubitSystems/MultiQubitSystems.ipynb).\n",
    "\n",
    "This tutorial covers the following topics:\n",
    "\n",
    "- Applying quantum gates to a part of the system\n",
    "- $\\text{CNOT}$ and $\\text{SWAP}$ gates\n",
    "- Controlled gates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Basics\n",
    "\n",
    "As a reminder, single-qubit gates are represented by $2\\times2$ [unitary matrices](../LinearAlgebra/LinearAlgebra.ipynb#Unitary-Matrices). \n",
    "The effect of a gate applied to a qubit can be calculated by multiplying the corresponding matrix by the state vector of the qubit to get the resulting state vector. \n",
    "\n",
    "Multi-qubit gates are represented by $2^N\\times2^N$ matrices, where $N$ is the number of qubits the gate operates on. To apply this gate, you multiply the matrix by the state vector of the $N$-qubit quantum system.\n",
    "\n",
    "> In Q# you can use the `DumpOperation` command to see the matrix that an operation implements. You can find more info and a demo in [this tutorial](../VisualizationTools/VisualizationTools.ipynb#Display-the-matrix-implemented-by-the-operation)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Applying Gates to a Part of the System\n",
    "\n",
    "The simplest thing we can do with multi-qubit systems is to apply gates to only a subset of qubits in the system. \n",
    "Similar to how it is sometimes possible to represent the state of a multi-qubit systems as a tensor product of single-qubit states, \n",
    "you can construct gates that modify the state of a multi-qubit system as tensor products of gates that affect parts of the system. \n",
    "\n",
    "Let's consider an example of applying single-qubit gates to one of the qubits of a two-qubit system.\n",
    "If you want to apply an $X$ gate to the first qubit of the system and do nothing to the second qubit,\n",
    "the resulting gate will be represented as a tensor product of an $X$ gate and the identity gate $I$ which corresponds to doing nothing:\n",
    "\n",
    "$$X \\otimes I =\n",
    "\\begin{bmatrix} 0 & 1 \\\\ 1 & 0 \\end{bmatrix} \\otimes \\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} =\n",
    "\\begin{bmatrix}\n",
    "    0 & 0 & 1 & 0 \\\\\n",
    "    0 & 0 & 0 & 1 \\\\\n",
    "    1 & 0 & 0 & 0 \\\\\n",
    "    0 & 1 & 0 & 0\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "You can use the same approach when applying several gates to independent parts of the system at the same time.\n",
    "For example, applying the $X$ gate to the first qubit and the $H$ gate to the second qubit would be represented as follows:\n",
    "\n",
    "$$X \\otimes H =\n",
    "\\begin{bmatrix} 0 & 1 \\\\ 1 & 0 \\end{bmatrix} \\otimes \\frac{1}{\\sqrt{2}}\\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix} =\n",
    "\\frac{1}{\\sqrt{2}}\\begin{bmatrix}\n",
    "    0 & 0 & 1 & 1 \\\\\n",
    "    0 & 0 & 1 & -1 \\\\\n",
    "    1 & 1 & 0 & 0 \\\\\n",
    "    1 & -1 & 0 & 0\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "> Note that we can use [mixed-multiplication property of tensor product](../LinearAlgebra/LinearAlgebra.ipynb#Tensor-Product) to see that this is equivalent to applying $X$ gate to the first qubit and applying $H$ gate to the second qubit, in either order:\n",
    ">\n",
    "> $$X \\otimes H = (I X) \\otimes (H I) = (I \\otimes H) (X \\otimes I)$$\n",
    "> $$X \\otimes H = (X I) \\otimes (I H) = (X \\otimes I) (I \\otimes H)$$\n",
    "\n",
    "This approach can be generalized to larger systems and gates that act on multiple qubits as well. \n",
    "It can be less straightforward if a multi-qubit gate is applied to a subset of qubits that are not \"adjacent\" to each other in the tensor product; we'll see an example later in this tutorial."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 1</span>: Compound Gate\n",
    "\n",
    "**Inputs:** $3$ qubits in an arbitrary superposition state $|\\psi\\rangle$, stored in an array of length 3.\n",
    "\n",
    "**Goal:** Apply the following matrix to the system. This matrix can be represented as applying $3$ single-qubit gates.\n",
    "\n",
    "$$Q = \\begin{bmatrix}\n",
    "    0 & -i & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    i & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & -i & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & i & 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & -1 & 0\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "> We recommend to keep a list of common quantum gates on hand, such as [this tutorial](../SingleQubitGates/SingleQubitGates.ipynb).\n",
    "\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "Start by noticing that the top right and bottom left quadrants of the matrix are filled with $0$s, and the bottom right quadrant equals to the top left one, multiplied by $i$. Does this look like a tensor product of a 1-qubit and 2-qubit matrices? Which ones?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T1_CompoundGate\n",
    "\n",
    "operation CompoundGate (qs : Qubit[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Multi-Qubit Gates Workbook](./Workbook_MultiQubitGates.ipynb#Exercise-1:-Compound-Gate).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CNOT Gate\n",
    "\n",
    "Our first proper multi-qubit gate is the $\\text{CNOT}$ (\"controlled NOT\") gate. \n",
    "The $\\text{CNOT}$ gate is a two-qubit gate, the first qubit is referred to as the **control** qubit, and the second as the **target** qubit. \n",
    "$\\text{CNOT}$ acts as a conditional gate of sorts: if the control qubit is in state $|1\\rangle$, it applies the $X$ gate to the target qubit, otherwise it does nothing. \n",
    "\n",
    "> If the system is in a superposition of several basis states, the effects of the gate will be a linear combination of the effects of it acting separately on each of the basis states. \n",
    "> This will be the case for all quantum gates you'll encounter later that are specified in terms of basis states: since all unitary gates are linear, it is sufficient to define their effect on the basis states, and use linearity to figure out their effect on any state.\n",
    "\n",
    "<table>\n",
    "    <col width=50>\n",
    "    <col width=50>\n",
    "    <col width=300>\n",
    "    <col width=150>\n",
    "    <col width=50>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Gate</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Matrix</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Applying to $|\\psi\\rangle = \\alpha|00\\rangle + \\beta|01\\rangle + \\gamma|10\\rangle + \\delta|11\\rangle$</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Applying to basis states</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Q# Documentation</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\text{CNOT}$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix}$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\text{CNOT}|\\psi\\rangle = \\alpha|00\\rangle + \\beta|01\\rangle + {\\color{red}\\delta}|10\\rangle + {\\color{red}\\gamma}|11\\rangle$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\text{CNOT}|00\\rangle = |00\\rangle$<br>\n",
    "        $\\text{CNOT}|01\\rangle = |01\\rangle$<br>\n",
    "        $\\text{CNOT}|10\\rangle = |11\\rangle$<br>\n",
    "        $\\text{CNOT}|11\\rangle = |10\\rangle$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><a href=\"https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.cnot\">CNOT</a></td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The $\\text{CNOT}$ gate is particularly useful for preparing entangled states. Consider the following separable state:\n",
    "\n",
    "$$\\big(\\alpha|0\\rangle + \\beta|1\\rangle\\big) \\otimes |0\\rangle = \\alpha|00\\rangle + \\beta|10\\rangle$$\n",
    "\n",
    "If we apply the $\\text{CNOT}$ gate to it, with the first qubit as the control, and the second as the target, we get the following state, which is not separable any longer:\n",
    "\n",
    "$$\\alpha|00\\rangle + \\beta|11\\rangle$$\n",
    "\n",
    "The $\\text{CNOT}$ gate is self-adjoint: applying it for the second time reverses its effect."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 2</span>: Preparing a Bell state\n",
    "\n",
    "**Input:** Two qubits in state $|00\\rangle$, stored in an array of length 2.\n",
    "\n",
    "**Goal:** Transform the system into the Bell state $\\Phi^+ = \\frac{1}{\\sqrt{2}}\\big(|00\\rangle + |11\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T2_BellState\n",
    "\n",
    "operation BellState (qs : Qubit[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Multi-Qubit Gates Workbook](./Workbook_MultiQubitGates.ipynb#Exercise-2:-Preparing-a-Bell-state).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ket-bra Representation\n",
    "\n",
    "Same as in the case of single-qubit gates, we can represent multi-qubit gates using Dirac notation.\n",
    "\n",
    "> Recall that kets represent column vectors and bras represent row vectors. For any ket $|\\psi\\rangle$, the corresponding bra is its adjoint (conjugate transpose): $\\langle\\psi| = |\\psi\\rangle^\\dagger$.\n",
    "> \n",
    "> Kets and bras are used to express [inner](../LinearAlgebra/LinearAlgebra.ipynb#Inner-Product) and [outer](../LinearAlgebra/LinearAlgebra.ipynb#Outer-Product) products. The inner product of $|\\phi\\rangle$ and $|\\psi\\rangle$ is the matrix product of $\\langle\\phi|$ and $|\\psi\\rangle$, denoted as $\\langle\\phi|\\psi\\rangle$, and their outer product is the matrix product of $|\\phi\\rangle$ and $\\langle\\psi|$, denoted as $|\\phi\\rangle\\langle\\psi|$. \n",
    ">\n",
    "> As we've seen in the [single-qubit gates tutorial](../SingleQubitGates/SingleQubitGates.ipynb#Ket-bra-Representation), kets and bras can be used to represent matrices. The outer product of two vectors of the same size produces a square matrix. We can use a linear combination of several outer products of simple vectors (such as basis vectors) to express any square matrix. \n",
    "\n",
    "Let's consider ket-bra representation of the $\\text{CNOT}$ gate:\n",
    "\n",
    "$$\\text{CNOT} = |00\\rangle\\langle00| + |01\\rangle\\langle01| + |10\\rangle\\langle11| + |11\\rangle\\langle10| =$$\n",
    "$$= \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}\\begin{bmatrix} 1 & 0 & 0 & 0 \\end{bmatrix} +\n",
    "\\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix}\\begin{bmatrix} 0 & 1 & 0 & 0 \\end{bmatrix} +\n",
    "\\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix}\\begin{bmatrix} 0 & 0 & 0 & 1 \\end{bmatrix} +\n",
    "\\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix}\\begin{bmatrix} 0 & 0 & 1 & 0 \\end{bmatrix} =$$ \n",
    "$$=\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ \\end{bmatrix} + \n",
    "\\begin{bmatrix} 0 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ \\end{bmatrix} + \n",
    "\\begin{bmatrix} 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 0 & 0 \\\\ \\end{bmatrix} + \n",
    "\\begin{bmatrix} 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ \\end{bmatrix} =\n",
    "\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\\\ \\end{bmatrix}$$\n",
    "\n",
    "This representation can be used to carry out calculations in Dirac notation without ever switching back to matrix representation:\n",
    "\n",
    "$$\\text{CNOT}|10\\rangle \n",
    "= \\big(|00\\rangle\\langle00| + |01\\rangle\\langle01| + |10\\rangle\\langle11| + |11\\rangle\\langle10|\\big)|10\\rangle =$$\n",
    "$$= |00\\rangle\\langle00|10\\rangle + |01\\rangle\\langle01|10\\rangle + |10\\rangle\\langle11|10\\rangle + |11\\rangle\\langle10|10\\rangle =$$\n",
    "$$= |00\\rangle\\big(\\langle00|10\\rangle\\big) + |01\\rangle\\big(\\langle01|10\\rangle\\big) + |10\\rangle\\big(\\langle11|10\\rangle\\big) + |11\\rangle\\big(\\langle10|10\\rangle\\big) =$$\n",
    "$$= |00\\rangle(0) + |01\\rangle(0) + |10\\rangle(0) + |11\\rangle(1) = |11\\rangle$$\n",
    "\n",
    "> Notice how a lot of the inner product terms turn out to equal 0, and our expression is easily simplified. We have expressed the CNOT gate in terms of outer product of computational basis states, which are orthonormal, and apply it to another computational basis state, so the individual inner products are going to always be 0 or 1. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general case, a $4\\times4$ matrix that describes a 2-qubit gate\n",
    "$$A = \\begin{bmatrix} a_{00} & a_{01} & a_{02} & a_{03} \\\\ \n",
    "a_{10} & a_{11} & a_{12} & a_{13} \\\\ \n",
    "a_{20} & a_{21} & a_{22} & a_{23} \\\\ \n",
    "a_{30} & a_{31} & a_{32} & a_{33} \\\\ \\end{bmatrix}$$\n",
    "will have the following ket-bra representation:\n",
    "$$A = a_{00} |00\\rangle\\langle00| + a_{01} |00\\rangle\\langle01| + a_{02} |00\\rangle\\langle10| + a_{03} |00\\rangle\\langle11| +$$\n",
    "$$+ a_{10} |01\\rangle\\langle00| + a_{11} |01\\rangle\\langle01| + a_{12} |01\\rangle\\langle10| + a_{13} |01\\rangle\\langle11| +$$\n",
    "$$+ a_{20} |10\\rangle\\langle00| + a_{21} |10\\rangle\\langle01| + a_{22} |10\\rangle\\langle10| + a_{23} |10\\rangle\\langle11| +$$\n",
    "$$+ a_{30} |11\\rangle\\langle00| + a_{31} |11\\rangle\\langle01| + a_{32} |11\\rangle\\langle10| + a_{33} |11\\rangle\\langle11| \n",
    "$$\n",
    "\n",
    "A similar expression can be extended for matrices that describe $N$-qubit gates, where $N > 2$:\n",
    "\n",
    "$$A = \\sum_{i=0}^{2^N-1} \\sum_{j=0}^{2^N-1} a_{ij} |i\\rangle\\langle j|$$\n",
    "\n",
    "Dirac notation is particularly useful for expressing sparse matrices - matrices that have few non-zero elements. Indeed, consider the $\\text{CNOT}$ gate again: it is a $4 \\times 4$ matrix described with 16 elements, but its Dirac notation has only 4 terms, one for each non-zero element of the matrix.\n",
    "\n",
    "With enough practice you'll be able to perform computations in Dirac notation without spelling out all the bra-ket terms explicitly!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> ## Ket-bra decomposition\n",
    ">\n",
    "> This section describes a more formal process of finding the ket-bra decompositions of multi-qubit quantum gates. \n",
    "> This section is not necessary to start working with quantum gates, so feel free to skip it for now, and come back to it later.\n",
    ">\n",
    "> You can use the properties of [eigenvalues and eigenvectors](../LinearAlgebra/LinearAlgebra.ipynb#Part-III:-Eigenvalues-and-Eigenvectors) to find the ket-bra decomposition of any gate. Consider an $N$-qubit gate $A$; the matrix representation of the gate is a square matrix of size $2^N$. Therefore it also has $2^N$ orthogonal eigenvectors $|\\psi_i\\rangle$: \n",
    ">\n",
    "> $$A|\\psi_i\\rangle = x_i|\\psi_i\\rangle, 0 \\leq i \\leq 2^N -1$$\n",
    ">\n",
    "> Then its ket-bra decomposition is:\n",
    ">\n",
    "> $$A = \\sum_{i=0}^{2^N-1} x_i|\\psi_i\\rangle\\langle\\psi_i|$$\n",
    ">\n",
    "> Let's use our $\\text{CNOT}$ gate as a simple example. \n",
    "> The $\\text{CNOT}$ gate has four eigenvectors. \n",
    "> * Two, as we can clearly see, are computational basis states $|00\\rangle$ and $|01\\rangle$ with eigen values $1$ and $1$, respectively (the basis states that are not affected by the gate). \n",
    "> * The other two are $|1\\rangle \\otimes |+\\rangle = \\frac{1}{\\sqrt{2}}\\big(|10\\rangle + |11\\rangle\\big)$ and $|1\\rangle \\otimes |-\\rangle = \\frac{1}{\\sqrt{2}}\\big(|10\\rangle - |11\\rangle\\big)$ with eigenvalues $1$ and $-1$, respectively:\n",
    ">\n",
    "> $$\\text{CNOT}|0\\rangle \\otimes |0\\rangle = |0\\rangle \\otimes |0\\rangle$$\n",
    "> $$\\text{CNOT}|0\\rangle \\otimes |1\\rangle = |0\\rangle \\otimes |1\\rangle$$\n",
    "> $$\\text{CNOT}|1\\rangle \\otimes |+\\rangle = |1\\rangle \\otimes |+\\rangle$$\n",
    "> $$\\text{CNOT}|1\\rangle \\otimes |-\\rangle = -|1\\rangle \\otimes |-\\rangle$$\n",
    ">\n",
    "> Here's what the decomposition looks like:\n",
    ">\n",
    "> $$\\text{CNOT} = |00\\rangle\\langle00| + |01\\rangle\\langle01| + \n",
    "|1\\rangle \\otimes |+\\rangle\\langle1| \\otimes \\langle +| - |1\\rangle \\otimes| -\\rangle\\langle1| \\otimes \\langle -| =$$\n",
    ">$$= |00\\rangle\\langle00| + |01\\rangle\\langle01| +  \n",
    "\\frac{1}{2}\\big[\\big(|10\\rangle + |11\\rangle\\big)\\big(\\langle10| + \\langle11|\\big) - \\big(|10\\rangle - |11\\rangle\\big)\\big(\\langle10| - \\langle11|\\big)\\big] =$$\n",
    ">$$= |00\\rangle\\langle00| + |01\\rangle\\langle01| +\n",
    "\\frac{1}{2}\\big({\\color{red}{|10\\rangle\\langle10|}} + |10\\rangle\\langle11| + |11\\rangle\\langle10| + {\\color{red}{|11\\rangle\\langle11|}} - {\\color{red}{|10\\rangle\\langle10|}} + |10\\rangle\\langle11| + |11\\rangle\\langle10| - {\\color{red}{|11\\rangle\\langle11|}}\\big) =$$\n",
    ">$$= |00\\rangle\\langle00| + |01\\rangle\\langle01| + \\frac{1}{2}\\big(2|10\\rangle\\langle11| + 2|11\\rangle\\langle10|\\big) =$$\n",
    ">$$= |00\\rangle\\langle00| + |01\\rangle\\langle01| + |10\\rangle\\langle11| + |11\\rangle\\langle10|$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SWAP Gate\n",
    "\n",
    "The $\\text{SWAP}$ gate acts on two qubits, and, as the name implies, swaps their quantum states.\n",
    "\n",
    "<table style=\"border:1px solid\">\n",
    "    <col width=50>\n",
    "    <col width=50>\n",
    "    <col width=300>\n",
    "    <col width=150>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Gate</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Matrix</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Applying to $|\\psi\\rangle = \\alpha|00\\rangle + \\beta|01\\rangle + \\gamma|10\\rangle + \\delta|11\\rangle$</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Applying to basis states</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Q# Documentation</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\text{SWAP}$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\end{bmatrix}$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\text{SWAP}|\\psi\\rangle = \\alpha|00\\rangle + {\\color{red}\\gamma}|01\\rangle + {\\color{red}\\beta}|10\\rangle + \\delta|11\\rangle$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\text{SWAP}|00\\rangle = |00\\rangle$<br>\n",
    "        $\\text{SWAP}|01\\rangle = |10\\rangle$<br>\n",
    "        $\\text{SWAP}|10\\rangle = |01\\rangle$<br>\n",
    "        $\\text{SWAP}|11\\rangle = |11\\rangle$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><a href=\"https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.swap\">SWAP</a></td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 3</span>: Swapping two qubits\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. $N$ qubits in an arbitrary state $|\\psi\\rangle$, stored in an array of length $N$.\n",
    "2. Integers `index1` and `index2` such that $0 \\le \\text{index1} < \\text{index2} \\le N - 1$.\n",
    "\n",
    "**Goal:** Swap the states of the qubits at the indices given."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T3_QubitSwap\n",
    "\n",
    "operation QubitSwap (qs : Qubit[], index1 : Int, index2 : Int) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Multi-Qubit Gates Workbook](./Workbook_MultiQubitGates.ipynb#Exercise-3:-Swapping-two-qubits).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Multi-Qubit Gates Acting on Non-Adjacent Qubits\n",
    "\n",
    "In the above examples the $\\text{CNOT}$ gate acted on two adjacent qubits. However, multi-qubit gates can act on non-adjacent qubits as well. Let's see how to work out the math of the system state change in this case.\n",
    "\n",
    "Take 3 qubits in an arbitrary state $|\\psi\\rangle = x_{000} |000\\rangle + x_{001}|001\\rangle + x_{010}|010\\rangle + x_{011}|011\\rangle + x_{100}|100\\rangle + x_{101}|101\\rangle + x_{110}|110\\rangle + x_{111}|111\\rangle $. \n",
    "\n",
    "We can apply the $\\text{CNOT}$ gate on 1st and 3rd qubits, with the 1st qubit as control and the 3rd qubit as target. Let's label the 3-qubit gate that describes the effect of this on the whole system as $\\text{CINOT}$. The $\\text{CINOT}$ ignores the 2nd qubit (leaves it unchanged) and applies the $\\text{CNOT}$ gate as specified above. \n",
    "\n",
    "#### Q# #\n",
    "\n",
    "In Q# we describe the operation as the sequence of gates that are applied to the qubits, regardless of whether the qubits are adjacent or not.\n",
    "\n",
    "```C#\n",
    "operation CINOT (qs: Qubit[]) : Unit {\n",
    "    CNOT(qs[0], qs[2]);       // Length of qs is assumed to be 3\n",
    "}\n",
    "```\n",
    "\n",
    "#### Dirac notation\n",
    "\n",
    "In Dirac notation we can consider the effect of the gate on each basis vector separately: each basis vector $|a_1a_2a_3\\rangle$ remains unchanged if $a_1 = 0$, and becomes $|a_1a_2(\\neg a_3)\\rangle$ if $a_1 = 1$. The full effect on the state becomes:\n",
    "\n",
    "$$\\text{CINOT}|\\psi\\rangle \n",
    "= x_{000} \\text{CINOT}|000\\rangle + x_{001} \\text{CINOT}|001\\rangle + x_{010} \\text{CINOT}|010\\rangle + x_{011} \\text{CINOT}|011\\rangle+$$\n",
    "$$+ {\\color{red}{x_{100}}} \\text{CINOT}|{\\color{red}{100}}\\rangle + {\\color{red}{x_{101}}} \\text{CINOT}|{\\color{red}{101}}\\rangle + {\\color{red}{x_{110}}} \\text{CINOT}|{\\color{red}{110}}\\rangle + {\\color{red}{x_{111}}} \\text{CINOT}|{\\color{red}{111}}\\rangle =$$\n",
    "$$= x_{000}|000\\rangle + x_{001}|001\\rangle + x_{010}|010\\rangle + x_{011}|011\\rangle + {\\color{red}{x_{101}}}|100\\rangle + {\\color{red}{x_{100}}}|101\\rangle +  {\\color{red}{x_{111}}}|110\\rangle + {\\color{red}{x_{110}}}|111\\rangle $$\n",
    "\n",
    "#### Matrix form\n",
    "\n",
    "$\\text{CINOT}$ can also be represented in matrix form as a $2^3 \\times 2^3$ matrix:\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 & \\color{blue} 0 & \\color{blue} 1 & \\color{blue} 0 & \\color{blue} 0 \\\\\n",
    "    0 & 0 & 0 & 0 & \\color{blue} 1 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 0 \\\\\n",
    "    0 & 0 & 0 & 0 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 1 \\\\\n",
    "    0 & 0 & 0 & 0 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 1 & \\color{blue} 0\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Applying $\\text{CINOT}$ to $|\\psi\\rangle$ gives us \n",
    "$$\n",
    "\\text{CINOT} \\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 & \\color{blue} 0 & \\color{blue} 1 & \\color{blue} 0 & \\color{blue} 0 \\\\\n",
    "    0 & 0 & 0 & 0 & \\color{blue} 1 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 0 \\\\\n",
    "    0 & 0 & 0 & 0 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 1 \\\\\n",
    "    0 & 0 & 0 & 0 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 1 & \\color{blue} 0\n",
    "\\end{bmatrix} \n",
    "\\begin{bmatrix} x_{000} \\\\ x_{001} \\\\ x_{010} \\\\ x_{011} \\\\ x_{100} \\\\ x_{101} \\\\ x_{110} \\\\ x_{111} \\end{bmatrix}\n",
    "= \\begin{bmatrix} x_{000} \\\\ x_{001} \\\\ x_{010} \\\\ x_{011} \\\\ \\color{blue}{x_{101}} \\\\ \\color{blue}{x_{100}} \\\\ \\color{blue}{x_{111}} \\\\ \\color{blue}{x_{110}} \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "However, as $N$ gets larger, creating a full size matrix can be extremely unwieldy. To express the matrix without spelling out its elements, we can use the following trick:\n",
    "\n",
    "1. Apply the $\\text{SWAP}$ gate on the 1st and 2nd qubits.  \n",
    "   This will bring the qubits on which the $\\text{CNOT}$ gate acts next to each other, without any extra qubits between them.\n",
    "2. Apply the $\\text{CNOT}$ on 2nd and 3rd qubits.\n",
    "   Since now the gate acts on adjacent qubits, this can be represented as a tensor product of the gate we're applying and $I$ gates.\n",
    "3. Apply the $\\text{SWAP}$ gate on the 1st and 2nd qubits again.\n",
    "\n",
    "These can be represented as applying the following gates on the 3 qubits. \n",
    "\n",
    "1. $\\text{SWAP} \\otimes I$\n",
    "$$x_{000}|000\\rangle + x_{001}|001\\rangle + {\\color{red}{x_{100}}}|010\\rangle + {\\color{red}{x_{101}}}|011\\rangle + \n",
    "{\\color{red}{x_{010}}}|100\\rangle + {\\color{red}{x_{011}}}|101\\rangle + x_{110}|110\\rangle + x_{111}|111\\rangle\n",
    "$$\n",
    "\n",
    "2. $I \\otimes \\text{CNOT}$\n",
    "$$\n",
    "x_{000}|000\\rangle + x_{001}|001\\rangle + {\\color{blue}{x_{101}}}|010\\rangle + {\\color{blue}{x_{100}}}|011\\rangle + \n",
    "{x_{010}}|100\\rangle + {x_{011}}|101\\rangle + {\\color{blue}{x_{111}}}|110\\rangle + {\\color{blue}{x_{110}}}|111\\rangle\n",
    "$$\n",
    "\n",
    "3. $\\text{SWAP} \\otimes I$\n",
    "$$\n",
    "x_{000}|000\\rangle + x_{001}|001\\rangle + {x_{010}}|010\\rangle + {x_{011}}|011\\rangle +\n",
    "{\\color{green}{x_{101}}}|100\\rangle + {\\color{green}{x_{100}}}|101\\rangle + {\\color{green}{x_{111}}}|110\\rangle + {\\color{green}{x_{110}}}|111\\rangle\n",
    "$$\n",
    "\n",
    "The result is the the $\\text{CINOT}$ gate as we intended; so we can write\n",
    "\n",
    "$$\\text{CINOT} = (\\text{SWAP} \\otimes I)(I \\otimes \\text{CNOT})(\\text{SWAP} \\otimes I)$$\n",
    "\n",
    "> Note that in matrix notation we always apply a gate to the complete system, so we must apply $\\text{SWAP} \\otimes I$, spelling the identity gate explicitly.\n",
    "> However, when implementing the unitary $\\text{SWAP} \\otimes I$ in Q#, we need only to call `SWAP(qs[0], qs[1])` - the remaining qubit `qs[2]` will not change, which is equivalent to applying an implicit identity gate. \n",
    ">\n",
    "> We can also spell out all gates applied explicitly (this makes for a much longer code, though):\n",
    "> ```C#\n",
    "operation CINOT (qs: Qubit[]) : Unit {\n",
    "    // First step\n",
    "    SWAP(qs[0], qs[1]);\n",
    "    I(qs[2]);\n",
    "    // Second step\n",
    "    I(qs[0]);\n",
    "    CNOT(qs[1], qs[2]);\n",
    "    // Third step\n",
    "    SWAP(qs[0], qs[1]);\n",
    "    I(qs[2]);\n",
    "}```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "    <summary><b>Click here for the full matrix representation of these three steps.</b></summary>\n",
    "    \n",
    "We can represent $|\\psi\\rangle$ in matrix form as a sum of tensor products of states of sub-systems, separating either the state of the last qubit:\n",
    "$$\\begin{bmatrix} x_{000} \\\\ x_{001} \\\\ x_{010} \\\\ x_{011} \\\\ x_{100} \\\\ x_{101} \\\\ x_{110} \\\\ x_{111} \\end{bmatrix}\n",
    "= \n",
    "  \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{000} \\\\ x_{001} \\end{bmatrix}\n",
    "+ \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{010} \\\\ x_{011} \\end{bmatrix} \n",
    "+ \\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{100} \\\\ x_{101} \\end{bmatrix} \n",
    "+ \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{110} \\\\ x_{111} \\end{bmatrix}  \n",
    "$$\n",
    "\n",
    "or the state of the first qubit:\n",
    "\n",
    "$$\n",
    "  \\begin{bmatrix} x_{000} \\\\ x_{100} \\end{bmatrix} \\otimes \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix} \n",
    "+ \\begin{bmatrix} x_{001} \\\\ x_{101} \\end{bmatrix} \\otimes \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} \n",
    "+ \\begin{bmatrix} x_{010} \\\\ x_{110} \\end{bmatrix} \\otimes \\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} \n",
    "+ \\begin{bmatrix} x_{011} \\\\ x_{111} \\end{bmatrix} \\otimes \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix}  \n",
    "$$\n",
    "\n",
    "\n",
    "Thus the 3 steps in matrix form would be:\n",
    "\n",
    "1. $\\text{SWAP}$ the 1st and the 2nd qubits.\n",
    "$$\n",
    "\\left(\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\end{bmatrix} \\otimes \n",
    "\\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix}\\right)\n",
    "\\begin{bmatrix} x_{000} \\\\ x_{001} \\\\ x_{010} \\\\ x_{011} \\\\ x_{100} \\\\ x_{101} \\\\ x_{110} \\\\ x_{111} \\end{bmatrix} =$$\n",
    "$$= \\left(\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\end{bmatrix} \\otimes \n",
    "\\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix}\\right)\n",
    "\\left( \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{000} \\\\ x_{001} \\end{bmatrix}\n",
    "+ \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{010} \\\\ x_{011} \\end{bmatrix} \n",
    "+ \\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{100} \\\\ x_{101} \\end{bmatrix} \n",
    "+ \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{110} \\\\ x_{111} \\end{bmatrix} \\right) =$$\n",
    "$$= \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{000} \\\\ x_{001} \\end{bmatrix}\n",
    "+ \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} \\otimes {\\color{red}{\\begin{bmatrix} x_{100} \\\\ x_{101} \\end{bmatrix}}} \n",
    "+ \\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} \\otimes {\\color{red}{\\begin{bmatrix} x_{010} \\\\ x_{011} \\end{bmatrix}}} \n",
    "+ \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{110} \\\\ x_{111} \\end{bmatrix} \n",
    "= \\begin{bmatrix} x_{000} \\\\ x_{001} \\\\ {\\color{red}{x_{100}}} \\\\ {\\color{red}{x_{101}}} \\\\ {\\color{red}{x_{010}}} \\\\ {\\color{red}{x_{011}}} \\\\ x_{110} \\\\ x_{111} \\end{bmatrix}\n",
    "$$\n",
    "\n",
    "2. $\\text{CNOT}$ 2nd and 3rd qubits.\n",
    "$$\n",
    "\\left(\\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} \\otimes \n",
    "\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix} \\right) \n",
    "\\begin{bmatrix} x_{000} \\\\ x_{001} \\\\ x_{100} \\\\ x_{101} \\\\ x_{010} \\\\ x_{011} \\\\ x_{110} \\\\ x_{111} \\end{bmatrix} =$$\n",
    "$$= \\left(\\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} \\otimes \n",
    "\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix}\\right)\n",
    "\\left( \\begin{bmatrix} x_{000} \\\\ x_{010} \\end{bmatrix} \\otimes \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix} \n",
    "+ \\begin{bmatrix} x_{001} \\\\ x_{011} \\end{bmatrix} \\otimes \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} \n",
    "+ \\begin{bmatrix} x_{100} \\\\ x_{110} \\end{bmatrix} \\otimes \\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} \n",
    "+ \\begin{bmatrix} x_{101} \\\\ x_{111} \\end{bmatrix} \\otimes \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix} \\right)\n",
    "=$$ \n",
    "$$= \\begin{bmatrix} x_{000} \\\\ x_{010} \\end{bmatrix} \\otimes \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix} \n",
    "+ \\begin{bmatrix} x_{001} \\\\ x_{011} \\end{bmatrix} \\otimes \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} \n",
    "+ {\\color{blue}{\\begin{bmatrix} x_{101} \\\\ x_{111} \\end{bmatrix}}} \\otimes \\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix}\n",
    "+ {\\color{blue}{\\begin{bmatrix} x_{100} \\\\ x_{110} \\end{bmatrix}}} \\otimes \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix} \n",
    "= \\begin{bmatrix} x_{000} \\\\ x_{001} \\\\ {\\color{blue}{x_{101}}} \\\\ {\\color{blue}{x_{100}}} \\\\ x_{010} \\\\ x_{011} \\\\ {\\color{blue}{x_{111}}} \\\\ {\\color{blue}{x_{110}}} \\end{bmatrix}$$\n",
    "\n",
    "3. $\\text{SWAP}$ 1st and 2nd qubits.\n",
    "$$\n",
    "\\left(\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\end{bmatrix} \\otimes \n",
    "\\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} \\right)\n",
    "\\begin{bmatrix} x_{000} \\\\ x_{001} \\\\ x_{101} \\\\ x_{100} \\\\ x_{010} \\\\ x_{011} \\\\ x_{111} \\\\ x_{110} \\end{bmatrix} =$$\n",
    "$$= \\left( \\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\end{bmatrix} \\otimes \n",
    "\\begin{bmatrix} 1 & 0 \\\\ 0 & 1 \\end{bmatrix} \\right) \n",
    "\\left( \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{000} \\\\ x_{001} \\end{bmatrix}\n",
    "+ \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{101} \\\\ x_{100} \\end{bmatrix} \n",
    "+ \\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{010} \\\\ x_{011} \\end{bmatrix} \n",
    "+ \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{111} \\\\ x_{110} \\end{bmatrix} \\right) =$$\n",
    "$$= \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{000} \\\\ x_{001} \\end{bmatrix}\n",
    "+ \\begin{bmatrix} 0 \\\\ 1 \\\\ 0 \\\\ 0 \\end{bmatrix} \\otimes {\\color{green}{\\begin{bmatrix} x_{010} \\\\ x_{011} \\end{bmatrix}}}\n",
    "+ \\begin{bmatrix} 0 \\\\ 0 \\\\ 1 \\\\ 0 \\end{bmatrix} \\otimes {\\color{green}{\\begin{bmatrix} x_{101} \\\\ x_{100} \\end{bmatrix}}} \n",
    "+ \\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix} \\otimes \\begin{bmatrix} x_{110} \\\\ x_{111} \\end{bmatrix}\n",
    "= \\begin{bmatrix} x_{000} \\\\ x_{001} \\\\ {\\color{green}{x_{010}}} \\\\ {\\color{green}{x_{011}}} \\\\ {\\color{green}{x_{101}}} \\\\ {\\color{green}{x_{100}}}\\\\ x_{110} \\\\ x_{111} \\end{bmatrix}\n",
    "$$\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Controlled Gates\n",
    "\n",
    "**Controlled gates** are a class of gates derived from other gates as follows: they act on a control qubit and a target qubit, just like the CNOT gate. \n",
    "A controlled-$U$ gate applies the $U$ gate to the target qubit if the control qubit is in state $|1\\rangle$, and does nothing otherwise.\n",
    "\n",
    "Given a gate $U = \\begin{bmatrix} \\alpha & \\beta \\\\ \\gamma & \\delta \\end{bmatrix}$, its controlled version looks like this:\n",
    "\n",
    "<table style=\"border:1px solid\">\n",
    "    <col width=50>\n",
    "    <col width=50>\n",
    "    <col width=150>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Gate</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Matrix</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Q# Documentation</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\text{Controlled U}$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\begin{bmatrix}\n",
    "        1 & 0 & 0 & 0 \\\\\n",
    "        0 & 1 & 0 & 0 \\\\\n",
    "        0 & 0 & \\alpha & \\beta \\\\\n",
    "        0 & 0 & \\gamma & \\delta\n",
    "        \\end{bmatrix}$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><a href=\"https://docs.microsoft.com/azure/quantum/user-guide/language/expressions/functorapplication#controlled-functor\">Controlled functor</a></td>\n",
    "    </tr>\n",
    "</table>\n",
    "\n",
    "> The CNOT gate is en example of a controlled gate, which is why it is also known as the controlled NOT or controlled $X$ gate.\n",
    "\n",
    "The concept of controlled gates can be generalized beyond controlling single-qubit gates. \n",
    "For any multi-qubit gate, its controlled version will have an identity matrix in the top left quadrant, the gate itself in the bottom right, and $0$ everywhere else. \n",
    "Here, for example, is the $\\text{Controlled SWAP}$, or **Fredkin gate**, with the identity matrix highlighted in red, and the $\\text{SWAP}$ gate in blue:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    \\color{red} 1 & \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    \\color{red} 0 & \\color{red} 1 & \\color{red} 0 & \\color{red} 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    \\color{red} 0 & \\color{red} 0 & \\color{red} 1 & \\color{red} 0 & 0 & 0 & 0 & 0 \\\\\n",
    "    \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & \\color{red} 1 & 0 & 0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & \\color{blue} 1 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 0 \\\\\n",
    "    0 & 0 & 0 & 0 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 1 & \\color{blue} 0 \\\\\n",
    "    0 & 0 & 0 & 0 & \\color{blue} 0 & \\color{blue} 1 & \\color{blue} 0 & \\color{blue} 0 \\\\\n",
    "    0 & 0 & 0 & 0 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 0 & \\color{blue} 1\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Q#, controlled gates are applied using the [`Controlled`](https://docs.microsoft.com/azure/quantum/user-guide/language/expressions/functorapplication#controlled-functor) functor. \n",
    "The controlled version of a gate accepts an array of control qubits (in this case an array of a single qubit), followed by the arguments to the original gate. \n",
    "For example, these two lines are equivalent:\n",
    "\n",
    "```C#\n",
    "Controlled X([control], target);\n",
    "CNOT(control, target);\n",
    "```\n",
    "\n",
    "If the original gate was implemented as an operation with multiple parameters, the controlled version of this gate will take those parameters as a tuple. For example, to apply Fredkin gate, you'd have to call:\n",
    "\n",
    "```C#\n",
    "Controlled SWAP([control], (q1, q2));\n",
    "```\n",
    "\n",
    "You can use the controlled version of a Q# operation only if that operation has a controlled version defined. \n",
    "The Q# compiler will often be able to generate a controlled version of the operation automatically if you put `is Ctl` after the operation's return type.\n",
    "In other cases, you'll need to define the controlled version of an operation manually."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 4</span>: Controlled Rotation\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "1. Two qubits in an arbitrary state $|\\phi\\rangle$, stored as an array of length 2.\n",
    "2. An angle $\\theta$: $-\\pi < \\theta \\leq \\pi$.\n",
    "\n",
    "**Goal:** Apply a controlled [$R_x$ gate](../SingleQubitGates/SingleQubitGates.ipynb#Rotation-Gates), using the first qubit as control and the second qubit as target, with $\\theta$ as the angle argument for the gate.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "    If you were to apply a regular version of $R_x$ gate, it would take two parameters - angle $theta$ as the first parameter and the target qubit as the second parameter.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T4_ControlledRotation\n",
    "\n",
    "operation ControlledRotation (qs : Qubit[], theta : Double) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Multi-Qubit Gates Workbook](./Workbook_MultiQubitGates.ipynb#Exercise-4:-Controlled-Rotation).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Multi-controlled Gates\n",
    "\n",
    "Controlled gates can have multiple control qubits; in this case the gate $U$ is applied only if all control qubits are in the $|1\\rangle$ states. \n",
    "You can think of it as constructing a controlled version of a gate that is already controlled. \n",
    "\n",
    "The simplest example of this is the **Toffoli gate**, or $\\text{CCNOT}$ (controlled controlled $\\text{NOT}$) gate, which applies the $X$ gate to the last qubit only if the first two qubits are in $|11\\rangle$ state:\n",
    "\n",
    "$$\\begin{bmatrix}\n",
    "    \\color{red} 1 & \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & 0 & 0 \\\\\n",
    "    \\color{red} 0 & \\color{red} 1 & \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & 0 & 0 \\\\\n",
    "    \\color{red} 0 & \\color{red} 0 & \\color{red} 1 & \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & 0 & 0 \\\\\n",
    "    \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & \\color{red} 1 & \\color{red} 0 & \\color{red} 0 & 0 & 0 \\\\\n",
    "    \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & \\color{red} 1 & \\color{red} 0 & 0 & 0 \\\\\n",
    "    \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & \\color{red} 0 & \\color{red} 1 & 0 & 0 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & \\color{blue} 0 & \\color{blue} 1 \\\\\n",
    "    0 & 0 & 0 & 0 & 0 & 0 & \\color{blue} 1 & \\color{blue} 0\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "To construct a multi-controlled version of an operation in Q#, you can use the Controlled functor as well, passing all control qubits as an array that is the first parameter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other Types of Controlled Gates\n",
    "\n",
    "Typically the term \"controlled $U$ gate\" refers to the type of gate we've described previously, which applies the gate $U$ only if the control qubit(s) are in the $|1\\rangle$ state. \n",
    "\n",
    "It is possible, however, to define variants of controlled gates that use different states as control states. \n",
    "For example, an **anti-controlled** $U$ gate (sometimes called **zero-controlled**) applies a gate only if the control qubit is in the $|0\\rangle$ state. \n",
    "It is also possible to define control conditions in other bases, for example, applying the gate if the control qubit is in the $|+\\rangle$ state.\n",
    "\n",
    "All the variants of controlled gates can be expressed in terms of the controls described in previous sections, using the following sequence of steps:\n",
    "* First, apply a transformation on control qubits that will transform the state you want to use as control into the $|1...1\\rangle$ state.\n",
    "* Apply the regular controlled version of the gate.\n",
    "* Finally, undo the transformation on control qubits from the first step using the adjoint version of it.\n",
    "\n",
    "> Why do we need this last step? Remember that controlled gates are defined in terms of their effect on the basis states:\n",
    "> we apply the gate on the target qubit if and only if the control qubit is in the state we want to control on, and we don't change the state of the control qubit at all.\n",
    "> If we don't undo the transformation we did on the first step, applying our gate to a basis state will modify not only the state of the target qubit but also the state of the control qubit, which is not what we're looking for.\n",
    "> \n",
    "> For example, consider an anti-controlled $X$ gate - a gate that should apply an $X$ gate to the second qubit if the first qubit is in the $|0\\rangle$ state.\n",
    "> Here is the effect we expect this gate to have on each of the 2-qubit basis states:\n",
    "> \n",
    "> <table>\n",
    "  <col width=\"200\"/>\n",
    "  <col width=\"200\"/>\n",
    "  <tr>\n",
    "    <th style=\"text-align:center\">Input state</th>\n",
    "    <th style=\"text-align:center\">Output state</th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|00\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|01\\rangle$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|01\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|00\\rangle$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|10\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|10\\rangle$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|11\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|11\\rangle$</td>\n",
    "  </tr>\n",
    "</table>\n",
    "\n",
    "> Let's apply the anti-controlled X gate to the $|00\\rangle$ state step by step:\n",
    "> 1. Transform the state of the control qubit to $|1\\rangle$: we can do that by applying the $X$ gate to the first qubit:\n",
    "> $$|00\\rangle \\rightarrow |10\\rangle$$\n",
    "> 2. Apply the regular $\\text{CNOT}$ gate:\n",
    "> $$|10\\rangle \\rightarrow |11\\rangle$$\n",
    "> 3. Now, if we don't undo the change we did on the first step, we'll end up with a gate that transforms $|00\\rangle$ into $|11\\rangle$, which is not the transformation we're trying to implement.\n",
    "> However, if we undo it by applying the $X$ gate to the first qubit again, we'll get the correct state:\n",
    "> $$|11\\rangle \\rightarrow |01\\rangle$$\n",
    "> \n",
    "> You can check that getting the right behavior of the operation on the rest of the basis states also requires that last step.\n",
    "\n",
    "Finally, let's take a look at a very useful operation [ControlledOnBitString](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring) provided by the Q# Standard library.\n",
    "It defines a variant of a gate controlled on a state specified by a bit mask; for example, bit mask `[true, false]` means that the gate should be applied only if the two control qubits are in the $|10\\rangle$ state.\n",
    " \n",
    "The sequence of steps that implement this variant are:\n",
    "1. Apply the $X$ gate to each control qubit that corresponds to a `false` element of the bit mask (in the example, that's just the second qubit). After this, if the control qubits started in the $|10\\rangle$ state, they'll end up in the $|11\\rangle$ state, and if they started in any other state, they'll end up in any state but $|11\\rangle$.\n",
    "2. Apply the regular controlled version of the gate.\n",
    "3. Apply the $X$ gate to the same qubits to return them to their original state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 5</span>: Arbitrary controls\n",
    "\n",
    "**Input:**\n",
    "\n",
    "1. `controls` - a register of $N$ qubits in an arbitrary state $|\\phi\\rangle$.\n",
    "2. `target` - a qubit in an arbitrary state $|\\psi\\rangle$.\n",
    "3. `controlBits` - an array of $N$ booleans, specifying what state each control qubit should be in order to apply the gate.\n",
    "\n",
    "**Goal:** Apply the controlled $X$ gate with the `controls` as control qubits and `target` as target, with the state specified by `controlBits` as controls. If the element of the array is `true`, the corresponding qubit is a regular control (should be in state $|1\\rangle$), and if it is `false`, the corresponding qubit is an anti-control (should be in state $|0\\rangle$).\n",
    "\n",
    "> For example, if `controlBits = [true, false, true]`, the controlled $X$ gate should only be applied if the control qubits are in state $|101\\rangle$.\n",
    "\n",
    "<details>\n",
    "    <summary><strong>Need a hint? Click here</strong></summary>\n",
    "Consider using a library operation for this task. If you want to do it without a library operations, don't forget to reset the qubits back to the state they were originally in.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T5_MultiControls\n",
    "\n",
    "operation MultiControls (controls : Qubit[], target : Qubit, controlBits : Bool[]) : Unit is Adj {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [Multi-Qubit Gates Workbook](./Workbook_MultiQubitGates.ipynb#Exercise-5:-Arbitrary-controls).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "Congratulations! You have completed the series of introductory tutorials and are ready to start solving the katas.\n",
    "You should start with the [Basic Gates](../../BasicGates/BasicGates.ipynb) and [Superposition](../../Superposition/Superposition.ipynb) katas."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.24"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}