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",
    "- CNOT and SWAP gates\n",
    "- Controlled gates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To begin, first prepare this notebook for execution (if you skip this step, you'll get \"Syntax does not match any known patterns\" error when you try to execute Q# code in the next cells):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%package Microsoft.Quantum.Katas::0.11.2003.3107"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The package versions in the output of the cell above should always match. If you are running the Notebooks locally and the versions do not match, please install the IQ# version that matches the version of the `Microsoft.Quantum.Katas` package.\n",
    "> <details>\n",
    "> <summary><u>How to install the right IQ# version</u></summary>\n",
    "> For example, if the version of `Microsoft.Quantum.Katas` package above is 0.1.2.3, the installation steps are as follows:\n",
    ">\n",
    "> 1. Stop the kernel.\n",
    "> 2. Uninstall the existing version of IQ#:\n",
    ">        dotnet tool uninstall microsoft.quantum.iqsharp -g\n",
    "> 3. Install the matching version:\n",
    ">        dotnet tool install microsoft.quantum.iqsharp -g --version 0.1.2.3\n",
    "> 4. Reinstall the kernel:\n",
    ">        dotnet iqsharp install\n",
    "> 5. Restart the Notebook.\n",
    "> </details>\n"
   ]
  },
  {
   "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."
   ]
  },
  {
   "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 first applying $X$ gate to the first qubit and then applying $H$ gate to the second qubit:\n",
    ">\n",
    "> $$X \\otimes H = (I X) \\otimes (H I) = (I \\otimes H) (X \\otimes I)$$\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_Test\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 \\\\\n",
    "        \\text{CNOT}|01\\rangle = |01\\rangle \\\\\n",
    "        \\text{CNOT}|10\\rangle = |11\\rangle \\\\\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_Test\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": [
    "## 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 \\\\\n",
    "        \\text{SWAP}|01\\rangle = |10\\rangle \\\\\n",
    "        \\text{SWAP}|10\\rangle = |01\\rangle \\\\\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_Test\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": [
    "## 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/quantum/language/type-model#controlled>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/quantum/language/type-model#controlled) 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_Test\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 (remember that the controlled operation should not modify the state of the control qubits).\n",
    "\n",
    "> Let's consider an operation [ControlledOnBitString](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring) provided by Q# 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 by $|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_Test\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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}