Superposition/Workbook_Superposition.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Superposition Kata Workbook\n",
    "\n",
    "**What is this workbook?**\n",
    "A workbook is a collection of problems, accompanied by solutions to them. \n",
    "The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required. \n",
    "\n",
    "Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n",
    "\n",
    "This workbook describes the solutions to the problems offered in the [Superposition kata](./Superposition.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 first-time user.\n",
    "\n",
    "**What you should know for this workbook**\n",
    "\n",
    "You should be familiar with the following concepts before tackling the Superposition kata (and this workbook):\n",
    "1. Basic linear algebra\n",
    "2. The concept of qubit and multi-qubit systems\n",
    "3. Single-qubit and multi-qubit quantum 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.12.20070124"
   ]
  },
  {
   "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": [
    "## <a name=\"plus-state\"></a> Task 1.1. Plus state.\n",
    "\n",
    "**Input:** A qubit in the $|0\\rangle$ state.\n",
    "\n",
    "**Goal:**  Change the state of the qubit to $|+\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + |1\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Look up any list of quantum gates, for example, [Quantum logic gate @ Wikipedia](https://en.wikipedia.org/wiki/Quantum_gate). Typically one of the first gates described will be the [Hadamard gate](https://en.wikipedia.org/wiki/Quantum_logic_gate#Hadamard_(H)_gate): \n",
    "\n",
    "$$H = \\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix}$$\n",
    "\n",
    "This gate converts $|0\\rangle$ into $|+\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + |1\\rangle\\big)$ and $|1\\rangle$ into $|−\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle - |1\\rangle\\big)$.  The first of these transformations is exactly the one we're looking for!\n",
    "\n",
    "To implement this operation in Q#, look at the list of [intrinsic gates](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic) available in Q#. \n",
    "[Hadamard gate](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.h) is one of them. \n",
    "`Microsoft.Quantum.Intrinsic` namespace is open in Notebooks by default, so you can use the gates in the code right away. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T101_PlusState_Test \n",
    "\n",
    "operation PlusState (q : Qubit) : Unit {\n",
    "    H(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.1 of the Superposition kata.](./Superposition.ipynb#plus-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"minus-state\"></a> Task 1.2. Minus State.\n",
    "\n",
    "**Input:** A qubit in the $|0\\rangle$ state.\n",
    "\n",
    "**Goal:**  Change the state of the qubit to $|-\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle - |1\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "As we've seen in the previous task, the Hadamard gate maps the basis state $|0\\rangle$ to $\\frac{1}{\\sqrt2}\\big(|0\\rangle + |1\\rangle\\big)$ and $|1\\rangle$ to $\\frac{1}{\\sqrt2}\\big(|0\\rangle - |1\\rangle\\big)$. \n",
    "If our qubit was already in the $|1\\rangle$ state, we would simply apply the Hadamard gate to prepare the required $|-\\rangle$ state. \n",
    "However, there is another operation we can use to change the state $|0\\rangle$ to $|1\\rangle$, namely the [X gate](https://en.wikipedia.org/wiki/Quantum_logic_gate#Pauli-X_gate):\n",
    "\n",
    "$$X = \\begin{bmatrix} 0 & 1 \\\\ 1 & 0 \\end{bmatrix}$$\n",
    "\n",
    "This gate transforms $|0\\rangle \\longmapsto |1\\rangle$ and $|1\\rangle \\longmapsto |0\\rangle$.\n",
    "\n",
    "Here is the sequence of the steps to arrive to the solution:\n",
    "\n",
    "<table style=\"background-color: white; border:1px solid; tr  { background-color:transparent; }\">\n",
    "    <col width=400>\n",
    "    <col width=300>\n",
    "    <col width=300>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Description of operation</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Notation</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Circuit</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:left; border:1px solid\">Apply the X gate to $|0\\rangle$ to get $|1\\rangle$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$X|0\\rangle = |1\\rangle$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/testcircuit.png\"/></td>    \n",
    "      </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:left; border:1px solid\">Apply the Hadamard gate to $|1\\rangle$ to get $\\frac{1}{\\sqrt2}\\big(|0\\rangle - |1\\rangle\\big)$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$H|1\\rangle = \\frac{1}{\\sqrt2}\\big(|0\\rangle - |1\\rangle\\big)$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/singlehadamard.png\"/></td>       \n",
    "    </tr>   \n",
    "</table>\n",
    "\n",
    "In Q#, each gate is applied to the qubit sequentially, transforming its internal state. [X gate](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.x) is another gate in the `Microsoft.Quantum.Intrinsic` namespace."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T102_MinusState_Test \n",
    "\n",
    "operation MinusState (q : Qubit) : Unit {\n",
    "    X(q);\n",
    "    H(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.2 of the Superposition kata.](./Superposition.ipynb#minus-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"superposition-of-all-basis-vectors-on-two-qubits\"></a>Task 1.3. Superposition of all basis vectors on two qubits.\n",
    "\n",
    "**Input:** Two qubits in the $|00\\rangle$ state (stored in an array of length 2).\n",
    "\n",
    "**Goal:** Change the state of the qubits to $|+\\rangle \\otimes |+\\rangle = \\frac{1}{2} \\big(|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We know that the Hadamard gate maps the basis state $|0\\rangle$ to $\\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)$, so it is a logical starting point for solving this problem. \n",
    "\n",
    "Next, we see that the final state has a $\\frac{1}{2}$ term hinting that we might be applying two operations involving a $\\frac{1}{\\sqrt{2}}$ term. \n",
    "\n",
    "Now, how do we get the $|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle$ expression? Let's see what does multiplying the expression $|0\\rangle + |1\\rangle$ by itself look like:\n",
    "\n",
    "$$\\big(|0\\rangle + |1\\rangle\\big) \\otimes \\big(|0\\rangle + |1\\rangle\\big) = |0\\rangle|0\\rangle + |0\\rangle|1\\rangle + |1\\rangle|0\\rangle + |1\\rangle|1\\rangle = \\\\\n",
    "= |00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle$$\n",
    "\n",
    "Thus, applying the Hadamard gate to each qubit in isolation will deliver the desired final result:\n",
    "\n",
    "$$H|0\\rangle \\otimes H|0\\rangle = \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) \\otimes \\frac{1}{\\sqrt2}\\big(|0\\rangle + |1\\rangle\\big) = \\\\\n",
    "= \\frac{1}{2} (|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle)$$\n",
    "\n",
    "Q# arrays are similar to arrays in other languages: you can access the $i$-th element of the array `qs` as `qs[i]` (indices are 0-based)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T103_AllBasisVectors_TwoQubits_Test\n",
    "\n",
    "operation AllBasisVectors_TwoQubits (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    H(qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.3 of the Superposition kata.](./Superposition.ipynb#superposition-of-all-basis-vectors-on-two-qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"superposition-of-basis-vectors-with-phase-flip\"></a>Task 1.4. Superposition of basis vectors with phase flip.\n",
    "\n",
    "**Input:** Two qubits in the $|00\\rangle$ sate (stored in an array of length 2).\n",
    "\n",
    "**Goal:** Change the state of the qubits to $\\frac{1}{2}\\big(|00\\rangle+|01\\rangle+|10\\rangle-|11\\rangle \\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Here we start with the end state of the previous task $\\frac{1}{2} \\big(|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle\\big)$. Looking at the desired state, the phase of the $|11\\rangle$ state is flipped ($+$ changed to a $-$).\n",
    "\n",
    "A regular phase flip on one qubit can be done using a [Z gate](../tutorials/SingleQubitGates/SingleQubitGates.ipynb#Pauli-Gates):\n",
    "$$\\begin{bmatrix} 1 & 0 \\\\ 0 & -1 \\end{bmatrix}$$\n",
    "This gate will perform a phase flip only on the $|1\\rangle$ state:\n",
    "\n",
    "$$Z(\\alpha|0\\rangle + \\beta|1\\rangle) = \\alpha|0\\rangle - \\beta|1\\rangle$$\n",
    "\n",
    "In our case we only want to flip the phase of the $|11\\rangle$ state and not the $|01\\rangle$ state. To accomplish this, we can use a controlled Z gate; this will make sure that the $Z$ gate is only applied if the control bit is in the $|1\\rangle$ state, and the $|01\\rangle$ state will not change.\n",
    "\n",
    "> In Q# we can apply a controlled gate by using the `Controlled` keyword before the gate. The controlled gate will take two parameters; the first parameter is an array of control qubits (you can have multiple qubits used as a control), and the second parameter is a tuple of parameters passed to the original gate (in this case it's just the qubit to which you want to apply the gate if the control bit is $|1\\rangle$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T104_AllBasisVectorWithPhaseFlip_TwoQubits_Test\n",
    "\n",
    "operation AllBasisVectorWithPhaseFlip_TwoQubits (qs : Qubit[]) : Unit {\n",
    "    AllBasisVectors_TwoQubits(qs);\n",
    "    Controlled Z ([qs[0]], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 4 of the Superposition kata.](./Superposition.ipynb#superposition-of-basis-vectors-with-phase-flip)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"superposition-of-basis-vectors-with-phases\"></a>Task 1.5. Superposition of basis vectors with phases.\n",
    "\n",
    "**Input:** Two qubits in the $|00\\rangle$ state (stored in an array of length 2).\n",
    "\n",
    "**Goal:** Change the state of the qubits to $\\frac{1}{2} \\big(|00\\rangle + i|01\\rangle - |10\\rangle - i|11\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We will start approaching the problem from the desired end result. Let’s see if we can factor any expressions out of $\\big(|00\\rangle + i|01\\rangle - |10\\rangle - i|11\\rangle\\big)$:\n",
    "\n",
    "\\begin{equation}\n",
    "|00\\rangle + i|01\\rangle - |10\\rangle - i|11\\rangle\n",
    "= |00\\rangle + \\big(|0\\rangle - |1\\rangle\\big) i|1\\rangle - |10\\rangle = \\\\\n",
    "= \\big(|0\\rangle - |1\\rangle\\big) |0\\rangle + \\big(|0\\rangle - |1\\rangle\\big) i|1\\rangle\n",
    "= \\big(|0\\rangle - |1\\rangle\\big) \\otimes \\big(|0\\rangle + i|1\\rangle\\big)\n",
    "\\label{5.1} \\tag{5.1}\n",
    "\\end{equation}\n",
    "\n",
    "The fact that we were able to factor out the state into a tensor product of two terms means the state is separable.\n",
    "\n",
    "This is looking promising.  Now let’s try to approach the problem from the other end, i.e. from the starting state of $|00\\rangle$. \n",
    "As we've seen in the previous task, applying a Hadamard operation to each $|0\\rangle$ gets us closer to the factored-out expression:\n",
    "\n",
    "\\begin{equation}\n",
    "H|0\\rangle \\otimes H|0\\rangle = \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) \\otimes \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big)\n",
    "=\\frac{1}{2} \\big(|0\\rangle + |1\\rangle\\big) \\otimes \\big(|0\\rangle + |1\\rangle\\big) \n",
    "\\label{5.2} \\tag{5.2}\n",
    "\\end{equation}\n",
    "\n",
    "If we compare equations 5.1 and 5.2 (while ignoring the $\\frac{1}{2}$ term in equation 5.2), we end up with the following transformations that we need to perform on the individual qubits:\n",
    "\n",
    "\\begin{equation}\n",
    "|0\\rangle + |1\\rangle \\overset{???}\\rightarrow |0\\rangle - |1\\rangle\n",
    "\\label{5.3} \\tag{5.3}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "|0\\rangle + |1\\rangle \\overset{???}\\rightarrow |0\\rangle + i|1\\rangle\n",
    "\\label{5.4} \\tag{5.4}\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "Next lets take a look at our basic gates, in particular the <a href=\"https://en.wikipedia.org/wiki/Quantum_logic_gate#Pauli-Z_(%7F'%22%60UNIQ--postMath-00000021-QINU%60%22'%7F)_gate\">Pauli Z gate</a>:\n",
    "\n",
    "$$Z = \\begin{bmatrix} 1 & 0 \\\\ 0 & -1 \\end{bmatrix}$$\n",
    "\n",
    "If it is applied to the state $\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big)$, it will leave the basis state $|0\\rangle$ unchanged and will map $|1\\rangle$ to $-|1\\rangle$. Thus, \n",
    "\n",
    "$$Z\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) = \\frac{1}{\\sqrt2} \\big(|0\\rangle - |1\\rangle\\big)$$\n",
    "\n",
    "So the Z gate is the answers to the question of how to do the conversion 5.3. \n",
    "\n",
    "Looking for another gate to address the conversion 5.4, we find the <a href=\"https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.s\">S gate</a>:\n",
    "\n",
    "$$S = \\begin{bmatrix} 1 & 0 \\\\ 0 & i \\end{bmatrix}$$ \n",
    "\n",
    "If it is applied to the state $\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big)$, it will leave the basis state $|0\\rangle$ unchanged and will map $|1\\rangle$ to $i|1\\rangle$. Thus, \n",
    "\n",
    "$$S\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) = \\frac{1}{\\sqrt2} \\big(|0\\rangle + i|1\\rangle\\big)$$\n",
    "\n",
    "So the S gate now answers the question of how to do the conversion 5.4.\n",
    "\n",
    "To summarize, the state we need to prepare can be represented as follows:\n",
    "$$ZH|0\\rangle \\otimes SH|0\\rangle$$\n",
    "\n",
    "Remember that in Q# the gates have to be applied in reverse order compared to the mathematical notation - the gate closest to the ket symbol is applied first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T105_AllBasisVectorsWithPhases_TwoQubits_Test\n",
    "\n",
    "operation AllBasisVectorsWithPhases_TwoQubits (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    Z(qs[0]);\n",
    "\n",
    "    H(qs[1]);\n",
    "    S(qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.5 of the Superposition kata.](./Superposition.ipynb#superposition-of-basis-vectors-with-phases)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"bell-state\"></a> Task 1.6. Bell state $|\\Phi^{+}\\rangle$.\n",
    "\n",
    "**Input:** Two qubits in the $|00\\rangle$ state (stored in an array of length 2).\n",
    "\n",
    "**Goal:**  Change the state of the qubits to $|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|00\\rangle + |11\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The first thing we notice is that, unlike in the previous task, we cannot represent this state as a tensor product of two individual qubit states - this goal state is NOT separable. \n",
    "\n",
    "> How can we see this? Let's assume that this state can be represented as a tensor product of two qubit states: \n",
    ">\n",
    "> $$|\\psi_1\\rangle \\otimes |\\psi_2\\rangle = (\\alpha_1|0\\rangle + \\beta_1|1\\rangle) \\otimes (\\alpha_2|0\\rangle + \\beta_2|1\\rangle) = \\alpha_1\\alpha_2|00\\rangle + \\alpha_1\\beta_2|01\\rangle + \\beta_1\\alpha_2|10\\rangle + \\beta_1\\beta_2|11\\rangle$$ \n",
    ">\n",
    ">In order for this state to be equal to $\\frac{1}{\\sqrt2}\\big(|00\\rangle + |11\\rangle\\big)$, we need to have $\\alpha_1\\alpha_2 = \\beta_1\\beta_2 = \\frac{1}{\\sqrt2}$ and at the same time $\\alpha_1\\beta_2 = \\beta_1\\alpha_2 = 0$, which is impossible.\n",
    ">\n",
    ">This is the first time we encounter the phenomena called **entanglement**, in which the states of the qubits are linked together and can not be considered individually.  \n",
    "\n",
    "Let's see what steps we can take to prepare this state without factoring it into states of individual qubits.\n",
    "\n",
    "---\n",
    "\n",
    "First, we notice that we should end with a superposition of two of the four computational basis for two qubits: $|00\\rangle, |01\\rangle, |10\\rangle, |11\\rangle$.\n",
    "\n",
    "This gives us a hint that we should start by preparing a superposition on at least one of the qubits. Let’s try creating a superposition on the first qubit with a Hadamard gate: \n",
    "\n",
    "$$H|0\\rangle \\otimes |0\\rangle = \\frac{1}{\\sqrt2} (|0\\rangle + |1\\rangle) \\otimes |0\\rangle = \\frac{1}{\\sqrt2} (|00\\rangle + |10\\rangle)$$\n",
    "\n",
    "Well, we got pretty close, except we need to transform the $|10\\rangle$ state to $|11\\rangle$.\n",
    "How can we do this? \n",
    "\n",
    "We can take advantage of controlled gates, specifically the [controlled NOT gate](https://en.wikipedia.org/wiki/Controlled_NOT_gate), also referred to as CNOT. This gate acts on two qubits, hence it is represented as a $4 \\times 4$ unitary matrix. The CNOT gate changes the target qubit from state $|0\\rangle$ to $|1\\rangle$ and vice versa when the control qubit is $|1\\rangle$ and does nothing to the target qubit when the control qubit is $|0\\rangle$. The control qubit always remains unchanged. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table style=\"background-color: white; border:1px solid; tr  { background-color:transparent; }\">\n",
    "    <col width=300>\n",
    "    <col width=300>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Matrix</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Circuit</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\text{CNOT} = \\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\"><img src=\"./img/CNOTGateCircuit.png\"/></td>    \n",
    "      </tr>      \n",
    "</table> <br>\n",
    "<center>The matrix and circuit representation of CNOT</center><br>\n",
    "\n",
    "If we apply the CNOT gate to the state $\\frac{1}{\\sqrt2} (|00\\rangle + |10\\rangle)$, taking the first qubit as the control and the second one as target, we'll get exactly the desired goal state. \n",
    "<img src=\"./img/Task6OutputHadamardasControl.png\" width=\"200\"/>\n",
    " \n",
    "<table style=\"background-color: white; border:1px solid; tr  { background-color:transparent; }\">\n",
    "    <col width=500>\n",
    "    <col width=300>\n",
    "    <col width=300>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Steps required to reach goal state</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Notation</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Circuit</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:left; border:1px solid\">1. Apply a Hadamard gate to the first qubit. <br/> 2. Applying a CNOT with first qubit as control and second qubit as target.</td>\n",
    "        <td style=\"text-align:center; border:1px solid; font-bold; font-size: 16px; \">$\\frac{1}{\\sqrt2} (|00\\rangle + |11\\rangle)$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/Task6HadamardCNOTCircuit.png\"/></td>\n",
    "      </tr>      \n",
    "</table>\n",
    "\n",
    "In matrix representation we can represent this operation as a product of two $4 \\times 4$ matrices, with the matrix corresponding to the first step being the tensor product of a Hadamard gate on the first qubit and identity gate on the second qubit.\n",
    "\n",
    "$$H \\otimes I = \\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 1  \\\\ 1 & -1 \\end{bmatrix} \\otimes \\begin{bmatrix} 1 & 0  \\\\ 0 & 1 \\end{bmatrix} = \n",
    "\\frac{1}{\\sqrt2}\\begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 1 & 0 & -1 & 0 \\\\ 0 & 1 & 0 & -1 \\end{bmatrix}$$\n",
    "\n",
    "$$\\underset{\\text{CNOT}}{\\underbrace{\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix}}} \n",
    "\\cdot \n",
    "\\underset{H \\otimes I}{\\underbrace{\\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 1 & 0 & -1 & 0 \\\\ 0 & 1 & 0 & -1 \\end{bmatrix}}}\n",
    "\\cdot\n",
    "\\underset{|0\\rangle}{\\underbrace{ \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}}}\n",
    "= \\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 1 & 0 & -1 \\\\ 1 & 0 & -1 & 0 \\end{bmatrix}\n",
    "\\cdot\n",
    "\\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}\n",
    "= \\underset{goal}{\\underbrace{ \\frac{1}{\\sqrt2} \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix}}}\n",
    "\\label{6.1} \\tag{6.1}\n",
    "$$\n",
    "\n",
    "Note that in the matrix representation and in Dirac notation the gates are applied from right to left (the rightmost operation happens firts), while in circuit notation the operations are applied from left to right (the leftmost operation happens first)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T106_BellState_Test\n",
    "\n",
    "operation BellState (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    CNOT(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.6 of the Superposition kata.](./Superposition.ipynb#bell-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"all-bell-states\"></a> Task 1.7. All Bell states.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. Two qubits in the $|00\\rangle$ state (stored in an array of length 2).\n",
    "2. An integer `index`.\n",
    "\n",
    "**Goal:**  Change the state of the qubits to one of the Bell states, based on the value of index:\n",
    "\n",
    "<table>\n",
    "  <col width=\"50\"/>\n",
    "  <col width=\"200\"/>\n",
    "  <tr>\n",
    "    <th style=\"text-align:center\">Index</th>\n",
    "    <th style=\"text-align:center\">State</th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">0</td>\n",
    "    <td style=\"text-align:center\">$|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|00\\rangle + |11\\rangle\\big)$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">1</td>\n",
    "    <td style=\"text-align:center\">$|\\Phi^{-}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|00\\rangle - |11\\rangle\\big)$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">2</td>\n",
    "    <td style=\"text-align:center\">$|\\Psi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|01\\rangle + |10\\rangle\\big)$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">3</td>\n",
    "    <td style=\"text-align:center\">$|\\Psi^{-}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|01\\rangle - |10\\rangle\\big)$</td>\n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solutions\n",
    "\n",
    "> The [Bell states](https://en.wikipedia.org/wiki/Bell_state) form an orthonormal basis in the 4-dimensional space that describes the states of a 2-qubit system. \n",
    "You can check that the norm of each of these states is 1, and their inner product of each pair of states is 0.\n",
    "\n",
    "The goal is to transform the $|00\\rangle$ basis state into one of the Bell basis states, depending on the value of `index` given as an input.\n",
    "\n",
    "We will describe two solutions, one of which will be based on the previous task, and the second one will help us understand the unitary transformation that converts the computational basis into the Bell basis.\n",
    "\n",
    "#### Solution 1\n",
    "\n",
    "Let's use the first Bell state we prepared in the previous task and transform it according to the value of `index`.\n",
    "\n",
    "<table>\n",
    "    <col width=300>\n",
    "    <col width=50>\n",
    "    <col width=300>\n",
    "    <tr bgcolor=\"white\">\n",
    "        <td bgcolor=\"white\" style=\"text-align:center\"><img src=\"./img/Task6HadamardCNOTCircuit.png\"/></td>\n",
    "        <td bgcolor=\"white\" style=\"text-align:center;font-size: 30px\">$\\Longrightarrow$</td>\n",
    "        <td bgcolor=\"white\" style=\"text-align:center;font-size: 20px\">$\\frac{1}{\\sqrt2} \\big(|00\\rangle + |11\\rangle\\big)$</td>\n",
    "      </tr>      \n",
    "</table>\n",
    "\n",
    "What transformation do we need to apply to get to the final state?\n",
    "\n",
    "* If `index = 0`, we do nothing - the prepared state is already $|\\Phi^{+}\\rangle$.\n",
    "\n",
    "* If `index = 1`, we need to add a relative phase of $-1$ to the $|11\\rangle$ term. Remember that Z gate does exactly that with a qubit:\n",
    "  \n",
    "  $$Z(H|0\\rangle) \\otimes |0\\rangle = \\frac{1}{\\sqrt2} \\big(|0\\rangle - |1\\rangle\\big) \\otimes |0\\rangle = \\frac{1}{\\sqrt2} \\big(|00\\rangle - |10\\rangle\\big)$$\n",
    "  \n",
    "  If we now apply the CNOT as before, we will have:\n",
    "\n",
    "  $$\\frac{1}{\\sqrt2} \\big(|00\\rangle - |\\overset{\\curvearrowright}{10}\\rangle\\big) \\underset{\\text{CNOT}}{\\Longrightarrow} \\frac{1}{\\sqrt2} \\big(|00\\rangle - |11\\rangle\\big) = |\\Phi^{-}\\rangle$$\n",
    "\n",
    "* If `index = 2`, we need to change the second qubit in both $|00\\rangle$ and $|11\\rangle$ terms, which can be done applying an X gate:\n",
    "  \n",
    "  $$H|0\\rangle \\otimes X|0\\rangle = H|0\\rangle \\otimes |1\\rangle = \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) \\otimes |1\\rangle = \\frac{1}{\\sqrt2} \\big(|01\\rangle + |11\\rangle\\big)$$\n",
    "  \n",
    "  If we now apply the CNOT as before, we will have:\n",
    "  \n",
    "  $$\\frac{1}{\\sqrt2} \\big(|01\\rangle + |\\overset{\\curvearrowright}{11}\\rangle\\big) \\underset{\\text{CNOT}}{\\Longrightarrow} \\frac{1}{\\sqrt2} \\big(|01\\rangle + |10\\rangle\\big) = |\\Psi^{+}\\rangle$$\n",
    "\n",
    "* If `index = 3`, we use the same logic to realize that we need to apply both the Z and X corrections to get $|\\Psi^{-}\\rangle$ state.\n",
    "\n",
    "The final sequence of steps is as follows:\n",
    "1. Apply the H gate to the first qubit. \n",
    "2. Apply the Z gate to the first qubit if `index = 1` or `index == 3`.\n",
    "3. Apply the X gate to the second qubit if `index = 2` or `index == 3`.\n",
    "4. Apply the CNOT gate with the first qubit as control and the second qubit as target.\n",
    "\n",
    "<table style=\"background-color: white; border:1px solid; tr  { background-color:transparent; }\">\n",
    "    <col width=200>\n",
    "    <col width=200>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Index 0</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Index 1</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/Task7.Index0.png\"/></td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/Task7.Index1.png\"/></td>    \n",
    "     </tr>        \n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Index 2</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Index 3</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/Task7.Index2.png\"/></td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/Task7.Index3.png\"/></td>    \n",
    "     </tr>      \n",
    "</table>\n",
    "<center>Circuits to be applied to prepare the four Bell States</center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T107_AllBellStates_Test\n",
    "\n",
    "operation AllBellStates (qs : Qubit[], index : Int) : Unit {\n",
    "    H(qs[0]);\n",
    "    \n",
    "    if (index == 1) {\n",
    "        Z(qs[0]);\n",
    "    }\n",
    "    if (index == 2) {\n",
    "        X(qs[1]);\n",
    "    }\n",
    "    if (index == 3) {\n",
    "        Z(qs[0]);\n",
    "        X(qs[1]);\n",
    "    }\n",
    "    \n",
    "    CNOT(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution 2\n",
    "\n",
    "Let's take a closer look at the unitary transformation $\\text{CNOT}\\cdot(H \\otimes I)$ discussed in task 6 (see equation 6.1).\n",
    "\n",
    "<table>\n",
    "    <col width=300>\n",
    "    <col width=50>\n",
    "    <col width=300>\n",
    "    <tr bgcolor=\"white\">\n",
    "        <td bgcolor=\"#FFFFFF\" style=\"text-align:center\"><img src=\"./img/Task6HadamardCNOTCircuit.PNG\"/></td>\n",
    "        <td bgcolor=\"#FFFFFF\" style=\"text-align:center;font-size: 30px\">$\\Leftrightarrow$</td>\n",
    "        <td bgcolor=\"#FFFFFF\" style=\"text-align:center;font-size: 20px\">$\\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 1 & 0 & -1 \\\\ \\underset{|\\Phi^{+}\\rangle}{\\underbrace{1}} & \\underset{|\\Psi^{+}\\rangle}{\\underbrace{0}} & \\underset{|\\Phi^{-}\\rangle}{\\underbrace{-1}} & \\underset{|\\Psi^{-}\\rangle}{\\underbrace{0}} \\end{bmatrix}$</td>\n",
    "      </tr>      \n",
    "</table>\n",
    "\n",
    "Notice that each of the columns in the unitary matrix corresponds to one of the Bell States.\n",
    "This unitary transformation transforms the computational basis into the Bell basis, which is exactly what the task asks us to do.\n",
    "\n",
    "We see that this transformation converts $|00\\rangle$ into the first Bell state, $|01\\rangle$ into the second Bell state, etc. \n",
    "We just need to make sure we set the qubits to the correct state before applying this transformation, using X gates to change the initial $|0\\rangle$ states to $|1\\rangle$ if needed. \n",
    "\n",
    "In Q#, we can use the <a href=\"https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.convert.intasboolarray\">IntAsBoolArray</a> function to convert the input `index` to the right bit pattern."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T107_AllBellStates_Test\n",
    "   \n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation AllBellStates (qs : Qubit[], index : Int) : Unit {\n",
    "    let bitmask = IntAsBoolArray(index, 2);\n",
    "    \n",
    "    if (bitmask[0]) {\n",
    "        X(qs[0]);\n",
    "    }\n",
    "\n",
    "    if (bitmask[1]) {\n",
    "        X(qs[1]);\n",
    "    }\n",
    "\n",
    "    H(qs[0]);\n",
    "    CNOT(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.7 of the Superposition kata.](./Superposition.ipynb#all-bell-states)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solutions to the rest of the tasks are included in the [Superposition Kata Workbook, Part 2](./Workbook_Superposition_Part2.ipynb)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}