Measurements/Workbook_Measurements.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Measurement 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 [Measurement kata](./Measurements.ipynb). 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 Measurements kata (and this workbook):\n",
    "\n",
    "1.\tBasic linear algebra\n",
    "2.\tThe concept of qubit and multi-qubit systems\n",
    "3.\tSingle-qubit and multi-qubit quantum gates and using them to manipulate the state of the system"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Discriminating Orthogonal States"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. $|0\\rangle$ or $|1\\rangle$?\n",
    "\n",
    "**Input:** A qubit which is guaranteed to be in either the $|0\\rangle$ or the $|1\\rangle$ state.\n",
    "\n",
    "**Output:**  `true` if the qubit was in the $|1\\rangle$ state, or `false` if it was in the $|0\\rangle$ state. The state of the qubit at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The input qubit is guaranteed to be either in basis state $|0\\rangle$ or $|1\\rangle$. This means that when measuring the qubit in the Pauli $Z$ basis (the computational basis), the measurement will report the input state without any doubt.  \n",
    "\n",
    "In Q# the operation [`M()`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.m) can be used to measure a single qubit in the Pauli $Z$ basis. The measurement result is a value of type `Result`: the operation `M` will return `One` if the input qubit was in the $|1\\rangle$ state and `Zero` if the input qubit was in the $|0\\rangle$ state. Since we need to encode the first case as `true` and the second one as `false`, we can return the result of equality comparison between measurement result and `One`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T101_IsQubitOne \n",
    "\n",
    "operation IsQubitOne (q : Qubit) : Bool {\n",
    "    return M(q) == One;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.1 of the Measurements kata.](./Measurements.ipynb#Task-1.1.-$|0\\rangle$-or-$|1\\rangle$?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Set the qubit to the $|0\\rangle$ state.\n",
    "\n",
    "**Input:** A qubit in an arbitrary state.\n",
    "\n",
    "**Goal:**  Change the state of the qubit to $|0\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "A fundamental postulate of quantum computing says that when we measure a qubit in a possible superposition state, it will collapse to the state that corresponds to the outcome of the measurement. This means that regardless of the original qubit state, after we measure the qubit in the Pauli $Z$ basis, it will end up in the $|0\\rangle$ or $|1\\rangle$ state. \n",
    "\n",
    "After we use the operation `M()` to measure the input qubit in the Pauli $Z$ basis, there are two possibilities:\n",
    "1.\tThe qubit collapses to the state $|0\\rangle$ (measurement outcome `Zero`), and we don’t need to change anything.\n",
    "2.\tThe qubit collapses to the state $|1\\rangle$ (measurement outcome `One`), and we need to flip the state of the qubit. This can be done with the [**X** gate](../tutorials/SingleQubitGates/SingleQubitGates.ipynb#Pauli-Gates)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T102_InitializeQubit \n",
    "\n",
    "operation InitializeQubit (q : Qubit) : Unit {\n",
    "    if M(q) == One {\n",
    "        X(q);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.2 of the Measurements kata.](./Measurements.ipynb#Task-1.2.-Set-the-qubit-to-the-$|0\\rangle$-state.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.3. $|+\\rangle$ or $|-\\rangle$?\n",
    "\n",
    "**Input:** A qubit which is guaranteed to be in either the $|+\\rangle$ or the $|-\\rangle$ state. As a reminder, $|+\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + |1\\rangle\\big)$, $|-\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle - |1\\rangle\\big)$.\n",
    "\n",
    "**Output:** `true` if the qubit was in the $|+\\rangle$ state, or `false` if it was in the $|-\\rangle$ state. The state of the qubit at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Both input states are superposition states, with equal absolute values of amplitudes of both basis states. This means if the sate is measured in the Pauli $Z$ basis, like we did in the previous task, there is a 50-50 chance of measuring `One` or `Zero`, which won't give us the necessary information.  \n",
    "\n",
    "To determine in which state the input qubit is with certainty, we want to transform the qubit into a state where there is no superposition with respect to the basis in which we perform the measurement. \n",
    "\n",
    "Consider how we can prepare the input states, starting with basis states: $H|0\\rangle = |+\\rangle$ and $H|1\\rangle = |-\\rangle$. \n",
    "This transformation can also be undone by applying the **H** gate again (remember that the **H** gate is self-adjoint, i.e., it equals its own inverse): $H|+\\rangle = |0\\rangle$  and $H|-\\rangle = |1\\rangle$.\n",
    "\n",
    "Once we have the $|0\\rangle$ or $|1\\rangle$ state, we can use the same principle as in task 1.1 to measure the state and report the outcome. Note that in this task return value `true` corresponds to input state $|+\\rangle$, so we compare the measurement result with `Zero`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T103_IsQubitPlus \n",
    "\n",
    "operation IsQubitPlus (q : Qubit) : Bool {\n",
    "    H(q);\n",
    "    return M(q) == Zero;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another possible solution could be to measure in the Pauli $X$ basis (${|+\\rangle, |-\\rangle}$ basis), this means a transformation with the **H** gate before measurement is not needed. Again, measurement result `Zero` would correspond to state $|+\\rangle$.\n",
    "\n",
    "In Q#, measuring in another Pauli basis can be done with the [`Measure()`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.measure) operation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T103_IsQubitPlus \n",
    "\n",
    "operation IsQubitPlus (q : Qubit) : Bool {\n",
    "   return Measure([PauliX], [q]) == Zero;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.3 of the Measurements kata.](./Measurements.ipynb#Task-1.3.-$|+\\rangle$-or-$|-\\rangle$?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.4. $|A\\rangle$ or $|B\\rangle$?\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. Angle $\\alpha$, in radians, represented as a `Double`.\n",
    "2. A qubit which is guaranteed to be in either the $|A\\rangle$ or the $|B\\rangle$ state, where $|A\\rangle = \\cos \\alpha |0\\rangle + \\sin \\alpha |1\\rangle$ and $|B\\rangle = - \\sin \\alpha |0\\rangle + \\cos \\alpha |1\\rangle$.\n",
    "\n",
    "**Output:** `true` if the qubit was in the $|A\\rangle$ state, or `false` if it was in the $|B\\rangle$ state. The state of the qubit at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We take a similar approach to the previous task: figure out a way to prepare the input states from the basis states and apply adjoint of that preparation before measuring the qubit.\n",
    "\n",
    "To create the input states $|A\\rangle$ and $|B\\rangle$, a [**Ry**](../tutorials/SingleQubitGates/SingleQubitGates.ipynb#Rotation-Gates) gate with $\\theta= 2\\alpha$ was applied to the basis states $|0\\rangle$ and $|1\\rangle$. As a reminder, \n",
    "\n",
    "$$R_y = \\begin{bmatrix} \\cos\\frac{\\theta}{2} & - \\sin\\frac{\\theta}{2} \\\\ \\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\end{bmatrix}$$\n",
    "\n",
    "We can return the inputs state to the basis sates by applying **Ry** gate with $-2 \\alpha$ as the rotation angle parameter to the input qubit.\n",
    "\n",
    "The measurement in Pauli $Z$ basis gives two possibilities:\n",
    "1. The qubit is measured as $|1\\rangle$, the input state was $|B\\rangle$, we return `false`.\n",
    "2. The qubit is measured as $|0\\rangle$, the input state was $|A\\rangle$, we return `true`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T104_IsQubitA\n",
    "\n",
    "operation IsQubitA (alpha : Double, q : Qubit) : Bool {\n",
    "    Ry(-2.0 * alpha, q);\n",
    "    return M(q) == Zero;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.4 of the Measurements kata.](./Measurements.ipynb#Task-1.4.-$|A\\rangle$-or-$|B\\rangle$?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.5. $|00\\rangle$ or $|11\\rangle$?\n",
    "\n",
    "**Input:** Two qubits (stored in an array of length 2) which are guaranteed to be in either the $|00\\rangle$ or the $|11\\rangle$ state.\n",
    "\n",
    "**Output:** 0 if the qubits were in the $|00\\rangle$ state, or 1 if they were in the $|11\\rangle$ state. The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Both qubits in the input array are in the same state: for $|00\\rangle$ each individual qubit is in state $|0\\rangle$, for $|11\\rangle$ each individual qubit is in state $|1\\rangle$. Therefore, if we measure one qubit we will know the state of the other qubit.  \n",
    "In other words, if the first qubit measures as `One`, we know that the qubits in the input array are in state $|11\\rangle$, and if it measures as `Zero`, we know they are in state $|00\\rangle$.\n",
    "\n",
    "> `condition ? trueValue | falseValue` is Q#'s ternary operator: it returns `trueValue` if `condition` is true and `falseValue` otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T105_ZeroZeroOrOneOne\n",
    "\n",
    "operation ZeroZeroOrOneOne (qs : Qubit[]) : Int {\n",
    "    return M(qs[0]) == One ? 1 | 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.5 of the Measurements kata.](./Measurements.ipynb#Task-1.5.-$|00\\rangle$-or-$|11\\rangle$?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.6. Distinguish four basis states.\n",
    "\n",
    "**Input:** Two qubits (stored in an array of length 2) which are guaranteed to be in one of the four basis states ($|00\\rangle$, $|01\\rangle$, $|10\\rangle$, or $|11\\rangle$).\n",
    "\n",
    "**Output:**\n",
    "\n",
    "* 0 if the qubits were in the $|00\\rangle$ state,\n",
    "* 1 if they were in the $|01\\rangle$ state, \n",
    "* 2 if they were in the $|10\\rangle$ state, \n",
    "* 3 if they were in the $|11\\rangle$ state.\n",
    "\n",
    "In this task and the subsequent ones the order of qubit states in task description matches the order of qubits in the array (i.e., $|10\\rangle$ state corresponds to `qs[0]` in state $|1\\rangle$ and `qs[1]` in state $|0\\rangle$).\n",
    "\n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Unlike in the previous task, this time measuring the first qubit won't give us any information on the second qubit, so we need to measure both qubits.\n",
    "\n",
    "First, we measure both qubits in the input array and store the result in `m1` and `m2`. We can decode these results like this:  \n",
    "- `m1` is $|0\\rangle$ and `m2` is $|0\\rangle$: we return $0\\cdot2+0 = 0$\n",
    "- `m1` is $|0\\rangle$ and `m2` is $|1\\rangle$: we return $0\\cdot2+1 = 1$\n",
    "- `m1` is $|1\\rangle$ and `m2` is $|0\\rangle$: we return $1\\cdot2+0 = 2$\n",
    "- `m1` is $|1\\rangle$ and `m2` is $|1\\rangle$: we return $1\\cdot2+1 = 3$\n",
    "\n",
    "In other words, we treat the measurement results as the binary notation of the return value in [big endian notation](../tutorials/MultiQubitSystems/MultiQubitSystems.ipynb#Endianness)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T106_BasisStateMeasurement\n",
    "\n",
    "operation BasisStateMeasurement (qs : Qubit[]) : Int {\n",
    "    // Measurement on the first qubit gives the higher bit of the answer, on the second - the lower\n",
    "    let m1 = M(qs[0]) == Zero ? 0 | 1;\n",
    "    let m2 = M(qs[1]) == Zero ? 0 | 1;\n",
    "    return m1 * 2 + m2;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.6 of the Measurements kata.](./Measurements.ipynb#Task-1.6.-Distinguish-four-basis-states.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.7. Distinguish two basis states given by bit strings\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. $N$ qubits (stored in an array of length $N$) which are guaranteed to be in one of the two basis states described by the given bit strings.\n",
    "2. Two bit strings represented as `Bool[]`s.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "* 0 if the qubits were in the basis state described by the first bit string,\n",
    "* 1 if they were in the basis state described by the second bit string.\n",
    "\n",
    "Bit values `false` and `true` correspond to $|0\\rangle$ and $|1\\rangle$ states. You are guaranteed that both bit strings have the same length as the qubit array, and that the bit strings differ in at least one bit.\n",
    "\n",
    "**You can use exactly one measurement.** The state of the qubits at the end of the operation does not matter.\n",
    "\n",
    "> Example:  for bit strings `[false, true, false]` and `[false, false, true]` return 0 corresponds to state $|010\\rangle$, and return 1 corresponds to state $|001\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "To solve this task we will use two steps. Like many other programming languages, Q# allows you to write functions to make code more readable and reusable. \n",
    "\n",
    "The first step is to find first bit that differs between bit strings `bit1` and `bit2`. For that we define a function `FindFirstDiff()` which loops through both `Bool[]`s and returns the first index where the bit strings differ. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function FindFirstDiff (bits1 : Bool[], bits2 : Bool[]) : Int {\n",
    "    for i in 0 .. Length(bits1) - 1 {\n",
    "        if bits1[i] != bits2[i] {\n",
    "            return i;\n",
    "        }\n",
    "    }\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second step is implementing the main operation: once we have found the first different bit, we measure the qubit in the corresponding position to see whether it is in state $|0\\rangle$ or $|1\\rangle$. If it is in state $|0\\rangle$, `res` takes the value `false`, if it is in state $|1\\rangle$ it takes the value `true`. \n",
    "\n",
    "`res == bits1[firstDiff]` compares the measurement result with the bit of `bits1` in the differing position. This effectively checks if the qubits are in the basis state described by the first or by the second bit string. \n",
    "The two possible outcomes are: \n",
    "1. The qubits are in the state described by the first bit string; then `res` will be equal to `bits1[firstDiff]` and the method will return `0`. \n",
    "2. The qubits are in the state described by the second bit string; then `res` will be not equal to `bits1[firstDiff]` (we know it has to be equal to `bits2[firstDiff]` which does not equal `bits1[firstDiff]`), and the method will return `1`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T107_TwoBitstringsMeasurement\n",
    "\n",
    "operation TwoBitstringsMeasurement (qs : Qubit[], bits1 : Bool[], bits2 : Bool[]) : Int {\n",
    "    // find the first index at which the bit strings are different and measure it\n",
    "    let firstDiff = FindFirstDiff(bits1, bits2);\n",
    "    let res = M(qs[firstDiff]) == One;\n",
    "\n",
    "    return res == bits1[firstDiff] ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.7 of the Measurements kata.](./Measurements.ipynb#Task-1.7.-Distinguish-two-basis-states-given-by-bit-strings)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.8. Distinguish two superposition states given by two arrays of bit strings - 1 measurement\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. $N$ qubits (stored in an array of length $N$) which are guaranteed to be in one of the two superposition states described by the given arrays of bit strings.\n",
    "2. Two arrays of bit strings represented as `Bool[][]`s.  \n",
    "The arrays have dimensions $M_1 \\times N$ and $M_2 \\times N$ respectively, where $N$ is the number of qubits and $M_1$ and $M_2$ are the numbers of bit strings in each array. Note that in general $M_1 \\neq M_2$.  \n",
    "An array of bit strings `[b₁, ..., bₘ]` defines a state that is an equal superposition of all basis states defined by bit strings $b_1, ..., b_m$.  \n",
    "For example, an array of bit strings `[[false, true, false], [false, true, true]]` defines a superposition state $\\frac{1}{\\sqrt2}\\big(|010\\rangle + |011\\rangle\\big)$.\n",
    "\n",
    "You are guaranteed that there exists an index of a qubit Q for which: \n",
    " - all the bit strings in the first array have the same value in this position (all `bits1[j][Q]` are the same),\n",
    " - all the bit strings in the second array have the same value in this position (all `bits2[j][Q]` are the same),\n",
    " - these values are different for the first and the second arrays.\n",
    "\n",
    "> For example, for arrays `[[false, true, false], [false, true, true]]` and `[[true, false, true], [false, false, true]]` return 0 corresponds to state $\\frac{1}{\\sqrt2}\\big(|010\\rangle + |011\\rangle\\big)$, return 1 corresponds to state $\\frac{1}{\\sqrt2}\\big(|101\\rangle + |001\\rangle\\big)$, and you can distinguish these states perfectly by measuring the second qubit.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "* 0 if qubits were in the superposition state described by the first array,\n",
    "* 1 if they were in the superposition state described by the second array.\n",
    "\n",
    "**You are allowed to use exactly one measurement.** \n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Like in the previous solution, we are looking for the index Q where the two bit strings differ. \n",
    "Let's define a function `FindFirstSuperpositionDiff()` which searches for an index Q which has 2 properties:\n",
    "\n",
    "1. The value of all arrays in `bits1` at the index Q is either `true` or `false`, and the value of all arrays in `bits2` at the index Q is either `true` or `false`.\n",
    "If this is not the case, you cannot be sure that measuring the corresponding qubit will always return the same result. \n",
    "> For example, if you are given the state $\\frac{1}{\\sqrt2}\\big(|010\\rangle + |011\\rangle\\big)$, and if you measure the third qubit, $50\\%$ of the time you will get $0$ and $50\\%$ of the time $1$, therefore to get reliable information you want to measure one of the first two qubits.\n",
    "2. This value is different for `bits1` and `bits2`.  \n",
    "> Indeed, if you want to distinguish states $\\frac{1}{\\sqrt2}\\big(|010\\rangle + |011\\rangle\\big)$ and $\\frac{1}{\\sqrt2}\\big(|000\\rangle + |001\\rangle\\big)$, there are two qubits that will produce a fixed measurement result for each state - the first one and the second one. However, measuring the first qubit will give $0$ for both states, while measuring the second qubit will give $1$ for the first state and $0$ for the second state, allowing to distinguish the states.\n",
    "\n",
    "To do this, we will iterate over all qubit indices, and for each of them we'll calculate the number of 1s in that position in `bits1` and `bits2`. \n",
    "1. The first condition means that this count should equal 0 (if all bit strings have 0 bit in this position) or the length of the array of bit strings (if all bit strings have 1 bit in this position). \n",
    "2. The second condition means that this count is different for `bits1` and `bits2`, i.e., one of the counts should equal 0 and another one - the length of the corresponding array of bit strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function FindFirstSuperpositionDiff (bits1 : Bool[][], bits2 : Bool[][], nQubits : Int) : Int {\n",
    "    for i in 0 .. nQubits - 1 {\n",
    "        // count the number of 1s in i-th position in bit strings of both arrays\n",
    "        mutable val1 = 0;\n",
    "        mutable val2 = 0;\n",
    "        for j in 0 .. Length(bits1) - 1 {\n",
    "            if bits1[j][i] {\n",
    "                set val1 += 1;\n",
    "            }\n",
    "        }\n",
    "        for k in 0 .. Length(bits2) - 1 {\n",
    "            if bits2[k][i] {\n",
    "                set val2 += 1;\n",
    "            }\n",
    "        }\n",
    "        if ((val1 == Length(bits1) and val2 == 0) or (val1 == 0 and val2 == Length(bits2))) {\n",
    "            return i;\n",
    "        }\n",
    "    }\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second step is very similar to the previous exercise: given the index we just found, we measure the qubit on that position.  \n",
    "Here we use the library function `ResultAsBool(M(qs[diff]))` that returns `true` if the measurement result is `One` and `false` if the result is `Zero`; a call to this library function is equivalent to comparison `M(qs[diff]) == One` that was used in the previous task."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T108_SuperpositionOneMeasurement\n",
    "\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation SuperpositionOneMeasurement (qs : Qubit[], bits1 : Bool[][], bits2 : Bool[][]) : Int {\n",
    "    let diff = FindFirstSuperpositionDiff(bits1, bits2, Length(qs));\n",
    "\n",
    "    let res = ResultAsBool(M(qs[diff]));\n",
    "\n",
    "    if res == bits1[0][diff] {\n",
    "        return 0;\n",
    "    }\n",
    "    else {\n",
    "        return 1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.8 of the Measurements kata.](./Measurements.ipynb#Task-1.8.-Distinguish-two-superposition-states-given-by-two-arrays-of-bit-strings---1-measurement)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.9. Distinguish two superposition states given by two arrays of bit strings\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. $N$ qubits (stored in an array of length $N$) which are guaranteed to be in one of the two superposition states described by the given arrays of bit strings.\n",
    "2. Two arrays of bit strings represented as `Bool[][]`s.  \n",
    "The arrays describe the superposition states in the same way as in the previous task,\n",
    "i.e. they have dimensions $M_1 \\times N$ and $M_2 \\times N$ respectively, $N$ being the number of qubits.\n",
    "\n",
    "The only constraint on the bit strings is that **all bit strings in the two arrays are distinct**. \n",
    "\n",
    "> Example:  for bit strings `[[false, true, false], [false, false, true]]` and `[[true, true, true], [false, true, true]]` return 0 corresponds to state $\\frac{1}{\\sqrt2}\\big(|010\\rangle + |001\\rangle\\big)$, return 1 to state $\\frac{1}{\\sqrt2}\\big(|111\\rangle + |011\\rangle\\big)$.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "* 0 if qubits were in the superposition state described by the first array,\n",
    "* 1 if they were in the superposition state described by the second array.\n",
    "\n",
    "**You can use as many measurements as you wish.** \n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Because all the bit strings are guaranteed to be different and we are not limited in the number of measurements we can do, we can use a simpler solution then before. \n",
    "\n",
    "When we measure all qubits of a certain superposition state, it collapses to one of the basis vectors that comprised the superposition. We can do exactly that and compare the resulting state to the given bit strings to see which array it belongs to.\n",
    "\n",
    "We use three built-in library primitives. First, we measure all the qubits in the array using [`MultiM()`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.measurement.multim) operation that returns an array of `Result`. \n",
    "\n",
    "To make this array easier to compare to the input bit strings, we convert this array into an integer using the [`ResultArrayAsInt()`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.convert.resultarrayasint) function, and we convert each of the input bit strings to an integer using the [`BoolArrayAsInt()`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.convert.boolarrayasint) function. Both functions use little-endian encoding when converting bits to integers.\n",
    "\n",
    "Now that we have two integers, we can easily compare the measurement results to each of the bit strings in the first array to check whether they belong to it; if they do, we know we were given the first state, otherwise it was the second state. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T109_SuperpositionMeasurement\n",
    "\n",
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation SuperpositionMeasurement (qs : Qubit[], bits1 : Bool[][], bits2 : Bool[][]) : Int {\n",
    "    let measuredState = ResultArrayAsInt(MultiM(qs));\n",
    "    for s in bits1 {\n",
    "        if BoolArrayAsInt(s) == measuredState {\n",
    "            return 0;\n",
    "        }\n",
    "    }\n",
    "    return 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.9 of the Measurements kata.](./Measurements.ipynb#Task-1.9.-Distinguish-two-superposition-states-given-by-two-arrays-of-bit-strings)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.10. $|0...0\\rangle$ state or W state ?\n",
    "\n",
    "**Input:** $N$ qubits (stored in an array of length $N$) which are guaranteed to be either in the $|0...0\\rangle$ state or in the [W state](https://en.wikipedia.org/wiki/W_state) (an equal superposition of all basis states that have exactly one $|1\\rangle$ in them). \n",
    "\n",
    "**Output:**\n",
    "\n",
    "* 0 if the qubits were in the $|0...0\\rangle$ state,\n",
    "* 1 if they were in the W state.\n",
    "\n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Here is an example of the W state for $N = 3$: $\\frac{1}{\\sqrt{3}}(|001\\rangle+|010\\rangle+|100\\rangle)$. We can see that each basis state in this expression always has exactly one qubit in the $|1\\rangle$ state, while in the $|0...0\\rangle$ state all qubits are in the $|0\\rangle$ state. \n",
    "\n",
    "We can use this to arrive to the solution: we will count the number of qubits that were measured in `One` state; if this number equals 1, we had a W state, if it equals 0 we know it was the $|0..0\\rangle$ state.\n",
    "\n",
    "> Note the use of a mutable variable `countOnes` to store the number of qubits measured in `One` state, and the use of a ternary operator `condition ? trueValue | falseValue` to express the return value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T110_AllZerosOrWState\n",
    "\n",
    "operation AllZerosOrWState (qs : Qubit[]) : Int {\n",
    "    mutable countOnes = 0;\n",
    "\n",
    "    for q in qs {\n",
    "        if M(q) == One {\n",
    "            set countOnes += 1;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    return countOnes == 0 ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the previous task we used `MultiM()` and `ResultArrayAsInt()`; these can also be used in this task to make the solution shorter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T110_AllZerosOrWState\n",
    "\n",
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation AllZerosOrWState (qs : Qubit[]) : Int {\n",
    "    return ResultArrayAsInt(MultiM(qs)) == 0 ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.10 of the Measurements kata.](./Measurements.ipynb#Task-1.10.-$|0...0\\rangle$-state-or-W-state-?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.11. GHZ state or W state ?\n",
    "\n",
    "**Input:** $N \\ge 2$ qubits (stored in an array of length $N$) which are guaranteed to be either in the [GHZ state](https://en.wikipedia.org/wiki/Greenberger%E2%80%93Horne%E2%80%93Zeilinger_state) or in the [W state](https://en.wikipedia.org/wiki/W_state).\n",
    "\n",
    "**Output:** \n",
    "\n",
    "* 0 if the qubits were in the GHZ state,\n",
    "* 1 if they were in the W state.\n",
    "\n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Here is an example of the GHZ state for $N = 3$: $\\frac{1}{\\sqrt2}(|000\\rangle + |111\\rangle)$.  \n",
    "\n",
    "As we've seen in the previous task, each of the basis states that form the W state will have exactly one qubit in the $|1\\rangle$ state. Basis states that forms the GHZ state will either have all qubits in the $|1\\rangle$ state or all qubits in the $|0\\rangle$ state.  \n",
    "\n",
    "This means that if we count the number of qubits that were measured in the `One` state, we'll get 1 for the W state and 0 or $N$ for the GHZ state. The code ends up almost the same as in the previous task (in fact, you can use this exact code to solve the previous task)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T111_GHZOrWState\n",
    "\n",
    "operation GHZOrWState (qs : Qubit[]) : Int {\n",
    "    mutable countOnes = 0;\n",
    "\n",
    "    for q in qs {\n",
    "        if M(q) == One {\n",
    "            set countOnes += 1;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    return countOnes == 1 ? 1 | 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.11 of the Measurements kata.](./Measurements.ipynb#Task-1.11.-GHZ-state-or-W-state-?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.12. Distinguish four Bell states.\n",
    "\n",
    "**Input:** Two qubits (stored in an array of length 2) which are guaranteed to be in one of the four Bell states.\n",
    "\n",
    "**Output:**\n",
    "\n",
    "* 0 if they were in the state $|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|00\\rangle + |11\\rangle\\big)$,\n",
    "* 1 if they were in the state $|\\Phi^{-}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|00\\rangle - |11\\rangle\\big)$,\n",
    "* 2 if they were in the state $|\\Psi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|01\\rangle + |10\\rangle\\big)$,\n",
    "* 3 if they were in the state $|\\Psi^{-}\\rangle = \\frac{1}{\\sqrt{2}} \\big(|01\\rangle - |10\\rangle\\big)$.\n",
    "\n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "If the qubits are entangled in one of the Bell states, you can't simply measure individual qubits to distinguish the states: if you do, the first two states will both give you 00 or 11, and the last two - 01 or 10. We need to come up with a way to transform the original states to states that are easy to distinguish before measuring them.\n",
    "\n",
    "First, let's take a look at the preparation of the Bell states starting with the $|00\\rangle$ basis state. \n",
    "\n",
    "> A more detailed discussion of preparing all the Bell states can be found in the [task 7 of the Superposition kata](./../Superposition/Workbook_Superposition.ipynb#all-bell-states).\n",
    "\n",
    "The unitary transformation $\\text{CNOT}\\cdot(H \\otimes I)$ (which corresponds to applying the **H** gate to the first qubit, followed by applying the **CNOT** gate with the first qubit as control and the second qubit as target) transforms the 4 basis vectors of the computational basis into the 4 Bell states.\n",
    "\n",
    "$$\\text{CNOT}\\cdot(H \\otimes I) = \\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}$$\n",
    "\n",
    "To transform the Bell states back to the basis states, you can apply [adjoint](./../tutorials/SingleQubitGates/SingleQubitGates.ipynb#Matrix-Representation) of this transformation, which will undo its effects. \n",
    "In this case both gates used are self-adjoint, so the adjoint transformation will require applying the same gates in reverse order (first **CNOT**, then **H**).\n",
    "\n",
    "After this the original states will be transformed as follows:\n",
    "\n",
    "<table>\n",
    "  <col width=\"50\"/>\n",
    "  <col width=\"200\"/>\n",
    "  <col width=\"100\"/>\n",
    "  <tr>\n",
    "    <th style=\"text-align:center\">Return value</th>\n",
    "    <th style=\"text-align:center\">Original state</th>\n",
    "    <th style=\"text-align:center\">Maps to basis 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",
    "    <td style=\"text-align:center\">$|00\\rangle$</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",
    "    <td style=\"text-align:center\">$|10\\rangle$</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",
    "    <td style=\"text-align:center\">$|01\\rangle$</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",
    "    <td style=\"text-align:center\">$|11\\rangle$</td>\n",
    "  </tr>\n",
    "</table>\n",
    "\n",
    "These are the same four 2-qubit basis states we've seen in task 1.6, though in different order compared to that task, so mapping the measurement results to the return values will differ slightly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T112_BellState\n",
    "\n",
    "operation BellState (qs : Qubit[]) : Int {\n",
    "    CNOT(qs[0], qs[1]);\n",
    "    H(qs[0]);\n",
    "\n",
    "    let m1 = M(qs[0]) == Zero ? 0 | 1;\n",
    "    let m2 = M(qs[1]) == Zero ? 0 | 1;\n",
    "    return m2 * 2 + m1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.12 of the Measurements kata.](./Measurements.ipynb#Task-1.12.-Distinguish-four-Bell-states.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.13. Distinguish four orthogonal 2-qubit states.\n",
    "\n",
    "**Input:** Two qubits (stored in an array of length 2) which are guaranteed to be in one of the four orthogonal states.\n",
    "\n",
    "**Output:**\n",
    "\n",
    "* 0 if they were in the state $|S_0\\rangle = \\frac{1}{2} \\big(|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle\\big)$,\n",
    "* 1 if they were in the state $|S_1\\rangle = \\frac{1}{2} \\big(|00\\rangle - |01\\rangle + |10\\rangle - |11\\rangle\\big)$,\n",
    "* 2 if they were in the state $|S_2\\rangle = \\frac{1}{2} \\big(|00\\rangle + |01\\rangle - |10\\rangle - |11\\rangle\\big)$,\n",
    "* 3 if they were in the state $|S_3\\rangle = \\frac{1}{2} \\big(|00\\rangle - |01\\rangle - |10\\rangle + |11\\rangle\\big)$.\n",
    "\n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Similarly to the previous task, let's see whether these states can be converted back to the basis states from the [task 1.6](#Task-1.6.-Distinguish-four-basis-states.).  \n",
    "\n",
    "To find a transformation that would convert the basis states to $|S_0\\rangle, ... |S_3\\rangle$, let's write out the coefficients of these states as column vectors side by side, so that they form a matrix. \n",
    "\n",
    "$$\\frac12 \\begin{bmatrix} \n",
    "1 & 1 & 1 & 1 \\\\ 1 & -1 & 1 & -1 \\\\ 1 & 1 & -1 & -1 \\\\ \n",
    "\\underset{|S_0\\rangle}{\\underbrace{1}} & \\underset{|S_1\\rangle}{\\underbrace{-1}} & \\underset{|S_2\\rangle}{\\underbrace{-1}} & \\underset{|S_3\\rangle}{\\underbrace{1}} \\end{bmatrix}$$\n",
    "\n",
    "Applying this matrix to each of the basis states will produce the given states.\n",
    "You can check explicitly that applying this transformation to the basis sate $|00\\rangle$ gives:\n",
    "$$\\frac{1}{2} \\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & -1 & 1 & -1 \\\\ 1 & 1 & -1 & -1 \\\\ 1 & -1 & -1 & 1 \\end{bmatrix} \\cdot \\begin{bmatrix}1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix} = \\frac{1}{2}\\begin{bmatrix}1 \\\\ 1 \\\\ 1 \\\\ 1 \\end{bmatrix} = \\frac{1}{2} \\big(|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle\\big) = |S_0\\rangle$$\n",
    "\n",
    "and similarly for the rest of the states.\n",
    "\n",
    "Notice that the top left $2 \\times 2$ block of this matrix is the same as the top right and the bottom left, and the same as the bottom right block multiplied by $-1$. This means that we can represent this transformation as a tensor product of two **H** gates (for background on this check the [Multi-qubit tutorial workbook](../tutorials/MultiQubitGates/Workbook_MultiQubitGates.ipynb#Exercise-1:-Compound-Gate)):  \n",
    "$$ H \\otimes H = \\frac{1}{\\sqrt{2}} \\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix} \\otimes \\frac{1}{\\sqrt{2}} \\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix} = \\frac{1}{2} \\begin{bmatrix} 1 & 1 & 1 & 1 \\\\ 1 & -1 & 1 & -1 \\\\ 1 & 1 & -1 & -1 \\\\ 1 & -1 & -1 & 1 \\end{bmatrix}  $$\n",
    "\n",
    "Knowing how to prepare the given states, we can convert the input state back to the corresponding basis state, like we've done in the previous task, and measure both qubits to get the answer.  \n",
    "\n",
    "> We are leveraging the `BasisStateMeasurement()` operation which we have written in task 1.6, to reduce code duplication.  \n",
    "> If you get the error `No identifier with the name \"BasisStateMeasurement\" exists.`, remember to execute the cell with the solution to [task 1.6](#Task-1.6.-Distinguish-four-basis-states.), otherwise this operation will be undefined indeed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T113_TwoQubitState\n",
    "\n",
    "operation TwoQubitState (qs : Qubit[]) : Int {\n",
    "    H(qs[0]);\n",
    "    H(qs[1]);\n",
    "    return BasisStateMeasurement(qs);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.13 of the Measurements kata.](./Measurements.ipynb#Task-1.13.-Distinguish-four-orthogonal-2-qubit-states.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.14*. Distinguish four orthogonal 2-qubit states, part 2.\n",
    "\n",
    "**Input:** Two qubits (stored in an array of length 2) which are guaranteed to be in one of the four orthogonal states.\n",
    "\n",
    "**Output:**\n",
    "\n",
    "* 0 if they were in the state $|S_0\\rangle = \\frac{1}{2} \\big(+ |00\\rangle - |01\\rangle - |10\\rangle - |11\\rangle\\big)$,\n",
    "* 1 if they were in the state $|S_1\\rangle = \\frac{1}{2} \\big(- |00\\rangle + |01\\rangle - |10\\rangle - |11\\rangle\\big)$,\n",
    "* 2 if they were in the state $|S_2\\rangle = \\frac{1}{2} \\big(- |00\\rangle - |01\\rangle + |10\\rangle - |11\\rangle\\big)$,\n",
    "* 3 if they were in the state $|S_3\\rangle = \\frac{1}{2} \\big(- |00\\rangle - |01\\rangle - |10\\rangle + |11\\rangle\\big)$.\n",
    "\n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Here we can leverage the same method as used in the previous exercise: find a transformation that maps the basis states to the given states and apply its adjoint to the input state before measuring.\n",
    "\n",
    "It is a lot harder to recognize the necessary transformation, though. The coefficient $\\frac12$ hints that there are still two **H** gates involved, but this transformation is not a tensor product. After some experimentation you can find that the given states can be prepared by applying the **H** gate to the second qubit of the matching Bell states:\n",
    "\n",
    "<table>\n",
    "  <col width=\"100\"/>\n",
    "  <col width=\"200\"/>\n",
    "  <col width=\"300\"/>\n",
    "  <col width=\"50\"/>\n",
    "  <tr>\n",
    "    <th style=\"text-align:center\">Basis state</th>\n",
    "    <th style=\"text-align:center\">Bell state</th>\n",
    "    <th style=\"text-align:center\">Input state (after applying H gate <br/> to the second qubit)</th>\n",
    "    <th style=\"text-align:center\">Return value</th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|00\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|00\\rangle + |11\\rangle\\big)$</td>\n",
    "    <td style=\"text-align:center\">$\\frac12 \\big (|00\\rangle + |01\\rangle + |10\\rangle - |11\\rangle\\big) = -|S_3\\rangle$</td>\n",
    "    <td style=\"text-align:center\">3</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|10\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|\\Phi^{-}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|00\\rangle - |11\\rangle\\big)$</td>\n",
    "    <td style=\"text-align:center\">$\\frac12 \\big (|00\\rangle + |01\\rangle - |10\\rangle + |11\\rangle\\big) = -|S_2\\rangle$</td>\n",
    "    <td style=\"text-align:center\">2</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|01\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|\\Psi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|01\\rangle + |10\\rangle\\big)$</td>\n",
    "    <td style=\"text-align:center\">$\\frac12 \\big (|00\\rangle - |01\\rangle + |10\\rangle + |11\\rangle\\big) = -|S_1\\rangle$</td>\n",
    "    <td style=\"text-align:center\">1</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">$|11\\rangle$</td>\n",
    "    <td style=\"text-align:center\">$|\\Psi^{-}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|01\\rangle - |10\\rangle\\big)$</td>\n",
    "    <td style=\"text-align:center\">$\\frac12 \\big (|00\\rangle - |01\\rangle - |10\\rangle - |11\\rangle\\big) = |S_0\\rangle$</td>\n",
    "    <td style=\"text-align:center\">0</td>\n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T114_TwoQubitStatePartTwo\n",
    "\n",
    "operation TwoQubitStatePartTwo (qs : Qubit[]) : Int {\n",
    "    H(qs[1]);\n",
    "\n",
    "    CNOT(qs[0], qs[1]);\n",
    "    H(qs[0]);\n",
    "\n",
    "    let m1 = M(qs[0]) == One ? 0 | 1;\n",
    "    let m2 = M(qs[1]) == One ? 0 | 1;\n",
    "    return m2 * 2 + m1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.14 of the Measurements kata.](./Measurements.ipynb#Task-1.14*.-Distinguish-four-orthogonal-2-qubit-states,-part-2.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.15**. Distinguish two orthogonal states on three qubits.\n",
    "\n",
    "**Input:** Three qubits (stored in an array of length 3) which are guaranteed to be in one of the two orthogonal states.\n",
    "\n",
    "**Output:**\n",
    "\n",
    "* 0 if they were in the state $|S_0\\rangle = \\frac{1}{\\sqrt{3}} \\big(|100\\rangle + \\omega |010\\rangle + \\omega^2 |001\\rangle \\big)$,\n",
    "* 1 if they were in the state $|S_1\\rangle = \\frac{1}{\\sqrt{3}} \\big(|100\\rangle + \\omega^2 |010\\rangle + \\omega |001\\rangle \\big)$.\n",
    "\n",
    "Here $\\omega = e^{2i \\pi/ 3}$.\n",
    "\n",
    "The state of the qubits at the end of the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let's find a unitary transformation that converts the state $|S_0\\rangle$ to the basis state $|000\\rangle$. To do this, we first apply a unitary operation that maps the first state to the W state $\\frac{1}{\\sqrt{3}} \\big( |100\\rangle + |010\\rangle + |001\\rangle \\big ) $.\n",
    "\n",
    "> We will use a convenient [rotation gate](./../tutorials/SingleQubitGates/SingleQubitGates.ipynb#Rotation-Gates) $R_1$ which applies a relative phase to the $|1\\rangle$ state and doesn't change the $|0\\rangle$ state. In matrix form \n",
    "> $$R_1(\\theta) = \\begin{bmatrix} 1 & 0 \\\\ 0 & e^{i\\theta} \\end{bmatrix} $$\n",
    "\n",
    "This can be accomplished by a tensor product $I \\otimes R_1(-\\frac{2\\pi}{3}) \\otimes R_1(-\\frac{4\\pi}{3})$, where\n",
    "- $I$ is the identity gate applied to qubit 0,\n",
    "- $R_1(-\\frac{2\\pi}{3}) = \\begin{bmatrix} 1 & 0 \\\\ 0 & \\omega^{-1} \\end{bmatrix} $, applied to qubit 1,\n",
    "- $R_1(-\\frac{4\\pi}{3}) = \\begin{bmatrix} 1 & 0 \\\\ 0 & \\omega^{-2} \\end{bmatrix} $, applied to qubit 2.\n",
    "\n",
    "> Note that applying this operation to the state $|S_1\\rangle$ converts it to $ \\frac{1}{\\sqrt{3}} \\big ( |100\\rangle + \\omega |010\\rangle + \\omega^2 |001\\rangle \\big) $.\n",
    "\n",
    "Now we can use adjoint of the state preparation routine for W state (from [task 17](./../Superposition/Workbook_Superposition_Part2.ipynb#Task-17**.-W-state-on-an-arbitrary-number-of-qubits.) of the Superposition kata), \n",
    "which will map the W state to the state $|000\\rangle$ and the second state to some other state $|S'_1\\rangle$. \n",
    "\n",
    "We don't need to do the math to figure out the exact state $|S'_1\\rangle$ in which $|S_1\\rangle$ will end up after those two transformations. \n",
    "Remember that our transformations are unitary, i.e., they preserve the inner products of vectors.\n",
    "Since the states $|S_0\\rangle$ and $|S_1\\rangle$ were orthogonal, their inner product $\\langle S_0|S_1\\rangle = 0$ is preserved when applying unitary transformations, and the states after the transformation will remain orthogonal. \n",
    "\n",
    "The state $|S'_1\\rangle$ is guaranteed to be orthogonal to the state $|000\\rangle$, i.e., $|S_1\\rangle$ gets mapped to a superposition that does not include basis state $|000\\rangle$.\n",
    "To distinguish the states $|000\\rangle$ and $|S'_1\\rangle$, we measure all qubits; if all measurement results were 0, the state was $|000\\rangle$ and we return 0, otherwise we return 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Math;\n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation WState_Arbitrary (qs : Qubit[]) : Unit is Adj + Ctl {\n",
    "    let N = Length(qs);\n",
    "\n",
    "    if N == 1 {\n",
    "        // base case of recursion: |1⟩\n",
    "        X(qs[0]);\n",
    "    } else {\n",
    "        // |W_N⟩ = |0⟩|W_(N-1)⟩ + |1⟩|0...0⟩\n",
    "        // do a rotation on the first qubit to split it into |0⟩ and |1⟩ with proper weights\n",
    "        // |0⟩ -> sqrt((N-1)/N) |0⟩ + 1/sqrt(N) |1⟩\n",
    "        let theta = ArcSin(1.0 / Sqrt(IntAsDouble(N)));\n",
    "        Ry(2.0 * theta, qs[0]);\n",
    "\n",
    "        // do a zero-controlled W-state generation for qubits 1..N-1\n",
    "        X(qs[0]);\n",
    "        Controlled WState_Arbitrary(qs[0 .. 0], qs[1 .. N - 1]);\n",
    "        X(qs[0]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T115_ThreeQubitMeasurement\n",
    "\n",
    "open Microsoft.Quantum.Math;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "\n",
    "operation ThreeQubitMeasurement (qs : Qubit[]) : Int {\n",
    "    R1(-2.0 * PI() / 3.0, qs[1]);\n",
    "    R1(-4.0 * PI() / 3.0, qs[2]);\n",
    "\n",
    "    // Apply inverse state prep of 1/sqrt(3) ( |100⟩ + |010⟩ + |001⟩ )\n",
    "    Adjoint WState_Arbitrary(qs);\n",
    "\n",
    "    // measure all qubits: if all of them are 0, we have the first state,\n",
    "    // if at least one of them is 1, we have the second state\n",
    "    return MeasureInteger(LittleEndian(qs)) == 0 ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solutions to the rest of the tasks are included in the [Measurements Workbook, Part 2](./Workbook_Measurements_Part2.ipynb)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}