tutorials/MultiQubitSystemMeasurements/Workbook_MultiQubitSystemMeasurements.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multi-Qubit System Measurements Tutorial 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 [Multi-Qubit System Measurements tutorial](./MultiQubitSystemMeasurements.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 Single-Qubit System Measurements tutorial (and this workbook):\n",
    "1. Basic linear algebra\n",
    "2. Single and multi-qubit systems\n",
    "3. Single and multi-qubit gates\n",
    "$\\newcommand{\\ket}[1]{\\left|#1\\right>}$\n",
    "$\\newcommand{\\bra}[1]{\\left<#1\\right|}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 1</span>: Multi-qubit measurement outcome probabilities I \n",
    "Suppose that a two-qubit system is known to be in the following state:\n",
    "$$\\ket \\psi =  \\frac{1}{3}\\ket {00} + \\frac{2}{3} \\ket {01} + \\frac{2}{3}\\ket {11}$$\n",
    "\n",
    "If all the qubits are measured simultaneously in the computational basis, what are the outcome probabilities?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "The wave function $|\\psi\\rangle$ is normalized, since $\\left(\\frac{1}{3}\\right)^2 + \\left(\\frac{2}{3}\\right)^2 + \\left(\\frac{2}{3}\\right)^2 = 1$. Hence, the probabilities of measuring each of the computational basis states is simply the square of the absolute value of the corresponding coefficients. That is, the probabilities of measuring $00$, $01$ and $11$ are $\\frac{1}{9}$, $\\frac{4}{9}$ and $\\frac{4}{9}$, respectively, and the probability of measuring the basis state $10$ that is not part of the superposition is $0$:\n",
    "\n",
    "<table style=\"border:1px solid\">\n",
    "    <col width=150>\n",
    "    <col width=150>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Measurement outcome</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Probability of outcome</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$00$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\left( \\frac{1}{3}\\right)^2 = \\frac{1}{9}$</td>\n",
    "    </tr> \n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$01$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\left( \\frac{2}{3}\\right)^2 = \\frac{4}{9}$</td>\n",
    "    </tr> \n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$10$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\left( 0\\right)^2 = 0$</td>\n",
    "    </tr>     \n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$11$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\left( \\frac{2}{3}\\right)^2 = \\frac{4}{9}$</td>\n",
    "    </tr> \n",
    "</table>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 1 of the Multi-Qubit System Measurements tutorial.](./MultiQubitSystemMeasurements.ipynb#Exercise-1:-Multi-qubit-measurement-outcome-probabilities-I)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 2</span>: Multi-qubit measurement outcome probabilities II \n",
    "Suppose that a two-qubit system is known to be in the following state:\n",
    "$$\\ket \\psi =  \\frac{2}{3}\\ket {00} + \\frac{1}{3} \\ket {01} + \\frac{2}{3}\\ket {11}$$.\n",
    "\n",
    "If all the qubits are measured simultaneously in the Pauli X basis, i.e., in the $\\{ \\ket{++}, \\ket{+-}, \\ket{-+}, \\ket{--}\\}$ basis, what are the outcome probabilities?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "Using the expressions $|0\\rangle = \\frac{1}{\\sqrt{2}} \\big( |+\\rangle + |-\\rangle \\big)$ and $|1\\rangle = \\frac{1}{\\sqrt{2}} \\big( |+\\rangle - |-\\rangle \\big)$, we first express $|\\psi\\rangle$ in the Pauli X basis. This gives us\n",
    "$$\n",
    "|\\psi \\rangle =  \n",
    "\\frac{2}{3} \\cdot \\frac{1}{\\sqrt{2}} \\big( |+\\rangle + |-\\rangle \\big) \\otimes \\frac{1}{\\sqrt{2}}\\big( |+\\rangle + |-\\rangle \\big) + \n",
    "\\frac{1}{3} \\cdot \\frac{1}{\\sqrt{2}} \\big( |+\\rangle + |-\\rangle \\big) \\otimes \\frac{1}{\\sqrt{2}} \\big( |+\\rangle - |-\\rangle \\big) + \n",
    "\\frac{2}{3} \\cdot \\frac{1}{\\sqrt{2}} \\big( |+\\rangle - |-\\rangle \\big) \\otimes \\frac{1}{\\sqrt{2}} \\big( |+\\rangle - |-\\rangle \\big) =\n",
    "\\\\ = \\frac{5}{6} |++\\rangle - \\frac{1}{6} |+-\\rangle + \\frac{1}{2} |-+\\rangle + \\frac{1}{6} |--\\rangle\n",
    "$$\n",
    "After this, the probabilities of measuring each of the four basis vectors is given by the square of the absolute value of its amplitude in the superposition:\n",
    "<table style=\"border:1px solid\">\n",
    "    <col width=150>\n",
    "    <col width=150>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Measurement outcome</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Probability of outcome</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$++$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\left( \\frac{5}{6}\\right)^2 = \\frac{25}{36}$</td>\n",
    "    </tr> \n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$+-$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\left( -\\frac{1}{6}\\right)^2 = \\frac{1}{36}$</td>\n",
    "    </tr> \n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$-+$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\left( \\frac{1}{2}\\right)^2 = \\frac{1}{4}$</td>\n",
    "    </tr>     \n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$++$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\left( \\frac{1}{6}\\right)^2 = \\frac{1}{36}$</td>\n",
    "    </tr> \n",
    "</table>\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 2 of the Multi-Qubit System Measurements tutorial.](./MultiQubitSystemMeasurements.ipynb#Exercise-2:-Multi-qubit-measurement-outcome-probabilities-II)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 3</span>: 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",
    "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](../MultiQubitSystems/MultiQubitSystems.ipynb#Endianness)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T1_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": [
    "We can generalize this code to read out an integer in big endian notation from a qubit array of arbitrary length using several library operations and functions:\n",
    "\n",
    "* `MultiM` measures each of the qubits in the array in the computational basis and returns an array of `Result` data type.\n",
    "* `Reversed` reverses the given array.\n",
    "* `ResultArrayAsInt` converts an array of bits given as `Result` to an integer, assuming little-endian notation (that's why we have to reverse the array before converting it)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T1_BasisStateMeasurement\n",
    "\n",
    "open Microsoft.Quantum.Arrays;\n",
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation BasisStateMeasurement (qs : Qubit[]) : Int {\n",
    "    return ResultArrayAsInt(Reversed(MultiM(qs)));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 3 of the Multi-Qubit System Measurements tutorial.](./MultiQubitSystemMeasurements.ipynb##Exercise-3:-Distinguish-four-basis-states)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 4</span>: Partial measurement probabilities for the Hardy state\n",
    "\n",
    "Consider a 2-qubit system in the state $\\ket \\psi = \\frac{1}{\\sqrt{12}} \\big(3|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle\\big)$.\n",
    "\n",
    "If only the first qubit is measured in the computational basis, what are the probabilities of the outcomes, and the post-measurement states of the system?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "A measurement outcome of $0$ on the first qubit corresponds to the projection operator $P_0|0\\rangle\\langle 0| \\otimes \\mathbb{1}$. Applying it to the state $\\ket \\psi$ gives us \n",
    "$$\\big|P_0 \\ket{\\psi}\\big|^2 = \\big|\\frac{1}{\\sqrt{10}} \\left(3\\ket {00} + \\ket{01}\\right) \\big|^2 = \\frac{5}{6}$$\n",
    "and \n",
    "$$\\frac{P_0 \\ket{\\psi}}{\\big|P_0 \\ket{\\psi}\\big|} = \\frac{1}{\\sqrt{10}} \\left( 3\\ket{00} + \\ket{01}\\right)$$\n",
    "\n",
    "Similarly, $P_1 = |1\\rangle \\langle 1 | \\otimes \\mathbb{1}$ is the projector corresponding to a measurement outcome of $1$ on the first qubit. Applying $P_1$ on $\\ket{\\psi}$ gives us $\\big|P_1 \\ket{\\psi}\\big|^2 = \\frac{1}{6}$ and \n",
    "\n",
    "$$\\frac{P_1 \\ket{\\psi}}{\\big|P_1 \\ket{\\psi}\\big|} = \\frac{1}{\\sqrt{2}} \\left(\\ket{10} + \\ket{11}\\right)$$\n",
    "\n",
    "<table style=\"border:1px solid\">\n",
    "    <col width=150>\n",
    "    <col width=150>\n",
    "    <col width=150>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Measurement outcome</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Probability of outcome</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Post-measurement state</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$0$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\frac{5}{6}$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\frac{1}{\\sqrt{10}} \\left( 3\\ket{00} + \\ket{01}\\right)$</td>\n",
    "    </tr> \n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$1$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\frac{1}{6}$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\frac{1}{\\sqrt{2}} \\left(\\ket{10} + \\ket{11}\\right)$</td>\n",
    "    </tr> \n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 4 of the Multi-Qubit System Measurements tutorial.](./MultiQubitSystemMeasurements.ipynb#Exercise-4:-Partial-measurement-probabilities-for-the-Hardy-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 5</span>: Distinguish orthogonal states using partial measurements\n",
    "\n",
    "\n",
    "**Input**: A 3-qubit system which is guaranteed to be in either the $\\ket{++-}$ state, or the $\\ket{---}$ state.\n",
    "\n",
    "**Output**: \n",
    "- 0 if the qubit is in the $\\ket{++-}$ state,\n",
    "- 1 if the qubit is in the $\\ket{---}$ state.\n",
    "\n",
    "The state of the qubits at the end of the operation should be the same as the initial state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "Since the state of the first qubit is different in these states ($\\ket +$ and $\\ket -$, respectively), it is sufficient to measure only the first qubit in the Pauli X basis in order to distinguish the two states. Furthermore, this measurement will not change the state of the system, since the post-projection state is identical to the original state regardless of the input state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T2_IsPlusPlusMinus\n",
    "\n",
    "operation IsPlusPlusMinus (qs : Qubit[]) : Int {\n",
    "    return Measure([PauliX], [qs[0]]) == Zero ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 5 of the Multi-Qubit System Measurements tutorial.](./MultiQubitSystemMeasurements.ipynb#Exercise-5:-Distinguish-orthogonal-states-using-partial-measurements)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 6</span>: Sequential measurements on an entangled state and a separable state\n",
    "Consider two two-qubit states:\n",
    "- The Bell state $|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|00\\rangle + |11\\rangle\\big)$.\n",
    "- A state $\\ket \\Theta = \\frac{1}{2} \\big( \\ket{00} + \\ket{01} + \\ket{10} + \\ket{11} \\big)$.\n",
    "\n",
    "For both states, consider a measurement on the first qubit, followed by a measurement on the second qubit, both done in the computational basis. For which state can we expect the measurement outcomes to be correlated? Verify by calculating the sequential measurement probabilities explicitly for both states. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "- *The Bell state*: If the measurement outcome on the first qubit is $0$, a subsequent measurement on the second qubit *always* results in an outcome of $0$, with probability $1$. Similarly, if the measurement outcome on the first qubit is $1$, then the second qubit measurement always results in $1$. Thus, sequential measurements are perfectly *correlated*.\n",
    "- *Separable state* $\\ket \\Theta$: Irrespective of whether the first qubit measurement outcome is $0$ of $1$ (each of which occurs with a probability of $0.5$), a subsequent measurement on the second qubit results in an outcome of $0$ or $1$ (both with a probability of $0.5$). Thus, sequential measurements are perfectly *uncorrelated*.  \n",
    "\n",
    "This aligns with the fact that the Bell state is entangled, while the $\\ket{\\Theta}$ is separable and can be expressed as $\\ket \\Theta = \\ket + \\otimes \\ket +$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 6 of the Multi-Qubit System Measurements tutorial.](./MultiQubitSystemMeasurements.ipynb#Exercise-6:-Sequential-measurements-on-an-entangled-state-and-a-separable-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 7</span>: State selection using partial measurements \n",
    "\n",
    "**Input**: \n",
    "1. A 2-qubit system in the state\n",
    "$$\n",
    "|\\psi\\rangle = \\frac{1}{\\sqrt{2}} |0\\rangle \\otimes ( a |0\\rangle + b|1\\rangle) + \\frac{1}{\\sqrt{2}} |1\\rangle \\otimes (b|0\\rangle + a |1\\rangle),\n",
    "$$\n",
    "where the constants $a$ and $b$ satisfying $|a|^2 + |b|^2 = 1$ are unknown.\n",
    "2. An integer $ind$ which is either $0$ or $1$.\n",
    "\n",
    "**Goal**: \n",
    "- If $ind$ equals 0, the state of the state of the second qubit should be $a|0\\rangle + b|1\\rangle$\n",
    "- If $ind$ equals 1, the state of the second qubit should be $b|0\\rangle + a |1\\rangle$. \n",
    "\n",
    "The state of the first qubit at the end does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "We note that if we measure the first qubit in the computational basis, then an outcome of $0$ collapses the second qubit to the state $a\\ket 0 + b \\ket 1$, while an outcome of $1$ collapses the second qubit to the state $b\\ket 0 + a \\ket 1$.\n",
    "\n",
    "Thus, if $ind=0$ and we measure $0$ or if $ind=1$ and we measure $1$, then after the measurement the second qubit will be in the desired state. On the other hand, if $ind=1$ and we measure $0$, or if $ind=0$ and we measure $1$, then the state of the second qubit after the measurement is not what we're looking for, but we can adjust it using the Pauli X gate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T3_StateSelction\n",
    "\n",
    "operation StateSelction(qs : Qubit[], ind : Int) : Unit {\n",
    "    // It is convenient to convert measurement outcome to an integer\n",
    "    let outcome = M(qs[0]) == Zero ? 0 | 1;\n",
    "    if outcome != ind {\n",
    "        X(qs[1]);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 7 of the Multi-Qubit System Measurements tutorial.](./MultiQubitSystemMeasurements.ipynb#Exercise-7:-State-selection-using-partial-measurements)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 8</span>: State preparation using partial measurements\n",
    "\n",
    "**Input:** Two qubits (in an array) which are in the state $\\ket{00}$.\n",
    "\n",
    "**Goal:**  Modify the qubits to the state $\\frac{1}{\\sqrt{3}} \\big(|00\\rangle + |01\\rangle + |10\\rangle\\big)$ using post-selection."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "While it is possible to prepare the state $\\ket \\psi$ directly using unitary rotations, it is simpler to use post-selection for preparing it. Here, we describe the procedure in more detail below.\n",
    "\n",
    "Initially we will prepare an equal superposition of all basis states corresponding to the first two qubits by applying the **H** gate to each of them: \n",
    "$$\\frac{1}{2} \\big(|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle\\big) \\otimes \\ket 0$$\n",
    "\n",
    "This state is a superposition of the state we want to prepare, and the $|11\\rangle$ state that we would like to discard.\n",
    "\n",
    "Now, we want to separate the first three basis states from the last one and to store this separation in the extra qubit. \n",
    "For example, we can keep the state of the extra qubit $|0\\rangle$ for the basis states that we want to keep, and switch it to $|1\\rangle$ for the basis states that we would like to discard. \n",
    "A **CCNOT** gate can be used to accomplish this, with the first two qubits used as control qubits and the extra qubit as target. \n",
    "When the gate is applied, the state of the extra qubit will only change to $|1\\rangle$ if both control qubits are in the $|11\\rangle$ state, which marks exactly the state that we want to discard:\n",
    "\n",
    "$$\\text{CCNOT}\\frac{1}{2} \\big(|00\\textbf{0}\\rangle + |01\\textbf{0}\\rangle + |10\\textbf{0}\\rangle + |11\\textbf{0}\\rangle\\big) = \n",
    "\\frac{1}{2}\\big(|00\\rangle + |01\\rangle + |10\\rangle \\big) \\otimes |\\textbf{0}\\rangle + \\frac{1}{2}|11\\rangle \\otimes |\\textbf{1}\\rangle $$\n",
    "\n",
    "Finally we measure just the extra qubit; this causes a partial collapse of the system to the state defined by the measurement result:\n",
    "* If the result is $|0\\rangle$, the system collapses to a state that is a linear combination of basis states which had the extra qubit in state $|0\\rangle$, i.e., the two qubits end up in the target state $\\frac{1}{\\sqrt3}\\big(|00\\rangle + |01\\rangle + |10\\rangle\\big)$. \n",
    "* If the result is $|1\\rangle$, the system collapses to a state $|11\\rangle$, so our goal is not achieved. The good thing is, this only happens in 25% of the cases, and we can just reset our qubits to the $|00\\rangle$ state and try again.\n",
    "\n",
    "\n",
    "> Q# has a built-in [repeat-until-success (RUS) loop](https://docs.microsoft.com/en-us/quantum/user-guide/using-qsharp/control-flow#repeat-until-success-loop), which comes in handy in this case. \n",
    "> * We will describe the main operations (applying **H** and **CCNOT** gates and the measurement) in the `repeat` part of the loop, which specifies its body.  \n",
    "> * `until` section specifies the condition which will break the loop. In this case the result of the measurement needs to be `Zero` to indicate our success.  \n",
    "> * Finally, the `fixup` section allows us to clean up the results of the loop body execution before trying again if the success criteria is not met. In this case we reset the first two qubits back to the $|00\\rangle$ state.\n",
    "\n",
    "This technique is sometimes called post-selection."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T4_PostSelection\n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation PostSelection (qs : Qubit[]) : Unit {\n",
    "    // Initialize the extra qubit\n",
    "    use anc = Qubit();\n",
    "    // Using the repeat-until-success pattern to prepare the right state\n",
    "    repeat {\n",
    "        ApplyToEach(H, qs);\n",
    "        Controlled X(qs, anc);\n",
    "        let res = MResetZ(anc);\n",
    "    } \n",
    "    until (res == Zero)\n",
    "    fixup {\n",
    "        ResetAll(qs);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 8 of the Multi-Qubit System Measurements tutorial.](./MultiQubitSystemMeasurements.ipynb#Exercise-8:-State-preparation-using-partial-measurements)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 9</span>: Two qubit parity measurement\n",
    "\n",
    "**Inputs**: Two qubits stored in an array which are guaranteed to be either in a superposition of the states $|00\\rangle$ and $|11\\rangle$ or in a superposition of states $|01\\rangle$ and $|10\\rangle$.\n",
    "\n",
    "**Output**: 0 if qubits were in the first superposition, 1 if they were in the second superposition.  \n",
    "*The state of the qubits at the end of the operation should be the same as the starting state.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "If we were not asked to maintain the state of the qubits, one approach would be to measure both the qubits separately in the computational basis, and check if the result is the same for both the measurements. If the measurement results are equal, the input state must have been a superposition of $\\ket{00}$ and $\\ket{11}$, while different measurement outcomes will imply that the input state must have been a superposition of $\\ket{01}$ and $\\ket{10}$. However, in these measurements we will lose the information about the original superposition states: a state $\\alpha |00\\rangle + \\beta |11\\rangle$ will collapse to either $|00\\rangle$ or $|11\\rangle$, and we won't be able to recover the information about the coefficients $\\alpha$ and $\\beta$.\n",
    "\n",
    "We need to measure the *parity* of the state without collapsing it all the way to the basis states. [Pauli measurements](https://docs.microsoft.com/en-us/quantum/concepts/pauli-measurements) can be used for joint measurements involving multiple qubits. For this task we apply the $Z \\otimes Z$ measurement on both qubits.\n",
    "\n",
    "A joint measurement using $Z \\otimes Z$ operator can be thought as projecting the measured state to one of the two eigenspaces of $Z \\otimes Z$ with $+1$ and $-1$ as the corresponding eigenvalues. The measurement returns `Zero` if the measured state is projected to the space with an eigenvalue of $+1$, and a result of `One` if projected to the space with an eigenvalue of $-1$.\n",
    "\n",
    "As we've seen in the tutorial, the state $\\alpha |00\\rangle + \\beta |11\\rangle$ is an eigenstate of the $Z \\otimes Z$ operator with the eigenvalue $+1$, and the state $\\alpha |01\\rangle + \\beta |10\\rangle$ is an eigenstate with the eigenvalue $-1$.\n",
    "Hence, we can use this joint measurement to recognize which of the superposition states we were given while preserving the initial superposition state.\n",
    "\n",
    "In Q#, the operation [`Measure`](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.measure) can be used to measure multiple qubits using an array of [Pauli](https://docs.microsoft.com/en-us/quantum/user-guide/language/types?#primitive-types) constants that define the basis for measurement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T5_ParityMeasurement\n",
    "\n",
    "operation ParityMeasurement (qs : Qubit[]) : Int {\n",
    "    return Measure([PauliZ, PauliZ], qs) == Zero ? 0 | 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 9 of the Multi-Qubit System Measurements tutorial.](./MultiQubitSystemMeasurements.ipynb#Exercise-9:-Two-qubit-parity-Measurement)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span style=\"color:blue\">Exercise 10</span>: Parity measurement in different basis\n",
    "\n",
    "Consider a system which is in a state $\\alpha |00\\rangle + \\beta |01\\rangle + \\beta |10\\rangle + \\alpha |11\\rangle$.\n",
    "\n",
    "What are the possible outcomes and their associated probabilities, if a measurement in an $XX$ Pauli measurement is done?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "The first step towards identifying the outcomes and their probabilities for joint measurements is to identify the eigenvectors corresponding to eigenvalues $\\pm1$ of the Pauli operator. We note that since $X\\ket{\\pm}= \\pm\\ket{\\pm}$, we have \n",
    "\\begin{align}\n",
    "XX \\ket{++} &= \\ket{++}, &XX \\ket{--} &= \\ket{--};\\\\\n",
    "XX \\ket{+-} &= -\\ket{+-}, &XX \\ket{-+} &= -\\ket{-+}.\n",
    "\\end{align}\n",
    "Thus, the $XX$ operator measures the parity in the Hadamard, or the $\\ket{\\pm}$ basis. That is, it distinguishes basis states with an even number of $+$'s from basis states which have an odd number of $+$'s.\n",
    "\n",
    "The projector corresponding to a result of `Zero` is given by $P_{+1} = \\ket{++}\\bra{++} + \\ket{--}\\bra{--}$, while the projector corresponding to a result of `One` is given by $P_{-1} = \\ket{+-}\\bra{+-} + \\ket{-+}\\bra{-+}$. Then, we note that $P_{+1}$ annihilates states with odd parity, while leaving states with even parity unaffected. That is, for any values of the constants \n",
    "\\begin{align}\n",
    "P_{+1} ( \\gamma \\ket{++} + \\delta \\ket{--} ) &= ( \\gamma \\ket{++} + \\delta \\ket{--} )\\\\\n",
    "P_{+1} ( \\mu \\ket{-+} + \\nu \\ket{+-} ) &= 0.\n",
    "\\end{align}\n",
    "Similarly, $P_{-1}$ annihilates states with even parity, while leaving states with odd parity unaffected.\n",
    "\n",
    "\n",
    "Now we express the given state in the Hadamard basis. We note that it is possible to go from the computational basis to the Hadamard basis using the following relations\n",
    "$$\n",
    "\\ket{0} = \\frac{1}{\\sqrt{2}} \\left( \\ket{+} + \\ket{-} \\right)\\\\\n",
    "\\ket{1} = \\frac{1}{\\sqrt{2}} \\left( \\ket{+} - \\ket{-} \\right).\n",
    "$$\n",
    "Using these, we obtain\n",
    "$$ \\alpha |00\\rangle + \\beta |01\\rangle + \\beta |10\\rangle + \\alpha |11\\rangle = (\\alpha + \\beta) |++\\rangle + (\\alpha - \\beta) |--\\rangle.$$\n",
    "Thus, this state has an even parity in the Hadamard basis. It follows that an $XX$ Pauli measurement will result in the outcome `Zero` with probability 1, leaving the state unchanged after the measurement.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to exercise 10 of the Multi-Qubit System Measurements tutorial.](./MultiQubitSystemMeasurements.ipynb#Exercise-10:-Parity-measurement-in-different-basis)"
   ]
  }
 ],
 "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": 5
}