Measurements/Workbook_Measurements_Part2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Measurements Kata Workbook, Part 2\n",
    "\n",
    "The [Measurements Kata Workbook, Part 1](./Workbook_Measurements.ipynb) includes the solutions of the tasks from Part I of the kata. This workbook continues the explanations for the tasks in Part II."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II*. Discriminating Nonorthogonal States"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"task-21\"></a>Task 2.1*. $|0\\rangle$ or $|+\\rangle$?\n",
    "\n",
    "**Input:** A qubit which is guaranteed to be in either the $|0\\rangle$ or the $|+\\rangle$ state.\n",
    "\n",
    "**Output:**  `true` if the qubit was in the $|0\\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.\n",
    "\n",
    "In this task your solution will be called multiple times, with one of the states picked with equal probability every time. You have to get overall accuracy of at least 80%.\n",
    "\n",
    "> This task is an example of quantum hypothesis testing, or state discrimination with minimum error."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Let ${|E_a\\rangle, |E_b\\rangle}$ be a measurement with two outcomes $a$ and $b$, which we identify with the answers, i.e., outcome \"a\" means we answer \"state was $|0\\rangle$\" and outcome \"b\" means we answer \"state was $|+\\rangle$\". Then we define\n",
    "\n",
    "* $P(a|0)$ = probability to observe first outcome given that the state was $|0\\rangle$\n",
    "* $P(b|0)$ = probability to observe second outcome given that the state was $|0\\rangle$\n",
    "* $P(a|+)$ = probability to observe first outcome given that the state was $|+\\rangle$\n",
    "* $P(b|+)$ = probability to observe second outcome given that the state was $|+\\rangle$\n",
    "\n",
    "The task is to maximize the probability to be correct on a single shot experiment, which is the same as to minimize the probability to be wrong on a single shot. \n",
    "\n",
    "Since the task promises uniform prior distribution of the inputs $|0\\rangle$ and $|+\\rangle$, i.e., $P(+) = P(0) = \\frac{1}{2}$, we get the following expression for the probability of giving a correct answer:\n",
    "\n",
    "$$P_{correct} = P(0) P(a|0) + P(+) P(b|+) = \\frac{1}{2} (P(a|0) + P(b|+))$$\n",
    "\n",
    "We can represent our measurement as a von Neumann measurement of the following form:\n",
    "\n",
    "$$|E_a\\rangle = R_y(2\\alpha) \\begin{bmatrix} 1\\\\0\\end{bmatrix} = \\begin{bmatrix}\\cos(\\alpha) \\\\ \\sin(\\alpha)\\end{bmatrix}, |E_b\\rangle = R_y(2\\alpha) \\begin{bmatrix} 0\\\\1\\end{bmatrix} = \\begin{bmatrix}-\\sin(\\alpha) \\\\ \\cos(\\alpha)\\end{bmatrix}$$\n",
    "\n",
    "<img src=\"./img/Task201_Rotation.png\" width=\"70%\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using this representation, we can express our probabilities as follows:\n",
    "\n",
    "$$P(a|0) = |\\langle E_a|0\\rangle|^2 = \\cos^2(\\alpha)$$\n",
    "\n",
    "$$P(b|+) = |\\langle E_b|+\\rangle|^2 = \\frac{1}{2} - \\cos(\\alpha) \\sin(\\alpha)$$\n",
    "\n",
    "$$P_{correct} = \\frac{1}{2} (\\frac{1}{2} + \\cos^2(\\alpha) - \\cos(\\alpha) \\sin(\\alpha))$$\n",
    "\n",
    "Maximizing this for $\\alpha$, we get max $P_{success} = \\frac{1}{2} (1 + \\frac{1}{\\sqrt{2}}) = 0.8535...$, which is attained for $\\alpha = -\\pi/8$.\n",
    "\n",
    "This means that $|E_a\\rangle$ and $|E_b\\rangle$ are the result of rotating $|0\\rangle$ and $|1\\rangle$, respectively, by $-\\pi/8$. If we rotate the whole system by $-\\alpha = \\pi/8$, we will get $|E_a\\rangle=|0\\rangle$ and $|E_b\\rangle=|1\\rangle$, and a measurement in the computational basis will give us the correct result with a probability of 85%.\n",
    "\n",
    "> In Q#, rotating the input state by some angle $\\theta$ can be done by applying $Ry$ gate with angle parameter $2\\theta$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T201_IsQubitZeroOrPlus\n",
    "\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation IsQubitPlusOrZero (q : Qubit) : Bool {\n",
    "    Ry(0.25 * PI(), q);\n",
    "    return M(q) == Zero;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.1 of the Measurements kata.](./Measurements.ipynb#task-21)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"task-22\"></a>Task 2.2**. $|0\\rangle$, $|+\\rangle$ or inconclusive?\n",
    "\n",
    "**Input:** A qubit which is guaranteed to be in either the $|0\\rangle$ or the $|+\\rangle$ state.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "* 0 if the qubit was in the $|0\\rangle$ state, \n",
    "* 1 if it was in the $|+\\rangle$ state,\n",
    "* -1 if you can't decide, i.e., an \"inconclusive\" result. \n",
    "\n",
    "Your solution:\n",
    "\n",
    "* should never give 0 or 1 answer incorrectly (i.e., identify $|0\\rangle$ as 1 or $|+\\rangle$ as 0),\n",
    "* will be called multiple times, with one of the states picked with equal probability every time,\n",
    "* may give an inconclusive (-1) answer in at most 80% of all the cases,\n",
    "* must correctly identify the $|0\\rangle$ state as 0 in at least 10% of all the cases,\n",
    "* must correctly identify the $|1\\rangle$ state as 1 in at least 10% of all the cases.\n",
    "\n",
    "The state of the qubit at the end of the operation does not matter.\n",
    "\n",
    "> This task is an example of unambiguous state discrimination.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "A simple strategy that gives an inconclusive result with probability 0.75 and never errs in case it yields a conclusive result can be obtained from randomizing the choice of measurement basis between the computational basis (std) and the Hadamard basis (had).\n",
    "\n",
    "Notice that when measured in the standard basis, the state $|0\\rangle$ will always lead to the outcome \"0\", and the state $|+\\rangle$ will lead to outcomes \"0\" and \"1\" with probability $\\frac12$ each. This means that if we measure \"1\", we can with certainty conclude that the state was $|+\\rangle$.\n",
    "\n",
    "A similar argument applies to the scenario where we measure in the Hadamard basis, where $|0\\rangle$ can lead to both \"+\" and \"-\" outcomes, and $|+\\rangle$ always leads to \"+\". Then if we measured \"-\", we can with certainty conclude that the state was $|0\\rangle$.\n",
    "\n",
    "This leads to the following scenarios (shown are the conditional probabilities\n",
    "of the resulting answers in each of the above scenarios).\n",
    "\n",
    "\n",
    "   State     | Basis |    P(0)   |    P(1)   |   P(-1)\n",
    "-------------|-------|-----------|-----------|----------\n",
    " $|0\\rangle$ |  std  |     $0$   |     $0$   |    $1$\n",
    " $|+\\rangle$ |  std  |     $0$   | $\\frac12$ | $\\frac12$\n",
    " $|0\\rangle$ |  had  | $\\frac12$ |     $0$   | $\\frac12$\n",
    " $|+\\rangle$ |  had  |     $0$   |     $0$   |    $1$\n",
    "\n",
    "> The easiest way to implement the measurement in the Hadamard basis in Q# is to apply an H gate followed by a regular measurement in computational basis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T202_IsQubitZeroOrPlusSimpleUSD\n",
    "\n",
    "open Microsoft.Quantum.Random;\n",
    "\n",
    "operation IsQubitPlusZeroOrInconclusiveSimpleUSD (q : Qubit) : Int {\n",
    "    let basis = DrawRandomInt(0, 1);\n",
    "\n",
    "    // randomize over std and had measurement bases\n",
    "    if basis == 0 {\n",
    "        // use standard basis\n",
    "        let result = M(q);\n",
    "        // result can be One only if the state was |+⟩; if result is Zero we can't be certain\n",
    "        return result == One ? 1 | -1;\n",
    "    }\n",
    "    else {\n",
    "        // use Hadamard basis\n",
    "        H(q);\n",
    "        let result = M(q);\n",
    "        // result can be One only if the state was |0⟩; if result is Zero we can't be certain\n",
    "        return result == One ? 0 | -1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.2 of the Measurements kata.](./Measurements.ipynb#task-22)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"peres-wooters-game\"></a>Task 2.3**.  Peres/Wooters game\n",
    "\n",
    "**Input:** A qubit which is guaranteed to be in one of the three states:\n",
    "\n",
    "* $|A\\rangle = \\frac{1}{\\sqrt{2}} \\big( |0\\rangle + |1\\rangle \\big)$,\n",
    "* $|B\\rangle = \\frac{1}{\\sqrt{2}} \\big( |0\\rangle + \\omega |1\\rangle \\big)$,\n",
    "* $|C\\rangle = \\frac{1}{\\sqrt{2}} \\big( |0\\rangle + \\omega^2 |1\\rangle \\big)$,\n",
    "\n",
    "Here $\\omega = e^{2i \\pi/ 3}$.\n",
    "\n",
    "**Output:** \n",
    "\n",
    "* 1 or 2 if the qubit was in the $|A\\rangle$ state, \n",
    "* 0 or 2 if the qubit was in the $|B\\rangle$ state, \n",
    "* 0 or 1 if the qubit was in the $|C\\rangle$ state.\n",
    "\n",
    "You are never allowed to give an incorrect answer. Your solution will be called multiple times, with one of the states picked with equal probability every time.\n",
    "\n",
    "The state of the qubit at the end of the operation does not matter. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "> The task is a simple game inspired by a quantum detection problem due to Holevo<sup><a href=\"#peres-wooters-game-ref1\">[1]</a></sup> and Peres/Wootters<sup><a href=\"#peres-wooters-game-ref2\">[2]</a></sup>. In the game, a player A thinks of a number (0,1 or 2) and the opponent, player B, tries to guess any number but the one chosen by player A. \n",
    ">\n",
    "> Classically, if you just made a guess, you'd have to ask two questions to be right $100\\%$ of the time. If instead, player A prepares a qubit with 0, 1, or 2 encoded into three single qubit states that are at an angle of 120 degrees with respect to each other and then hands the state to the opponent, then player B can apply a Positive Operator Valued Measure (POVM) consisting of 3 states that are perpendicular to the states chosen by player A. \n",
    "> It can be shown that this allows B to be right $100\\%$ of the time with only 1 measurement, which is something that is not achievable with a von Neumann measurement on 1 qubit.\n",
    "See also Peres<sup><a href=\"#peres-wooters-game-ref3\">[3, chapter 9.6]</a></sup> for a nice description of the optimal POVM.\n",
    "\n",
    "Next, we address how we can implement the mentioned POVM by way of a von Neumann measurement, and then how to implement said von Neumann measurement in Q\\#. First, we note that the POVM elements are given by the columns of the following matrix: \n",
    " \n",
    "$$M = \\frac{1}{\\sqrt{2}}\\left(\\begin{array}{rrr}\n",
    "1 & 1 & 1 \\\\ \n",
    "1 & \\omega & \\omega^2 \n",
    "\\end{array}\n",
    "\\right)$$\n",
    "\n",
    "where $\\omega = e^{2 \\pi i/3}$ denotes a primitive $3$rd root of unity. Our task will be to implement the rank 1 POVM given by the columns of $M$ via a von Neumann measurement. This can be done by \"embedding\" $M$ into a larger unitary matrix (taking complex conjugates and transposed):\n",
    "\n",
    "$$M' = \\frac{1}{\\sqrt{3}}\\left(\\begin{array}{cccc}\n",
    "1 & -1 & 1 & 0 \\\\ \n",
    "1 & -\\omega^2 & \\omega & 0 \\\\\n",
    "1 & -\\omega & \\omega^2 & 0 \\\\\n",
    "0 & 0 & 0 & -i\\sqrt{3} \n",
    "\\end{array}\n",
    "\\right)$$\n",
    "\n",
    "Notice that applying $M'$ to input states given by column $i$ of $M$ (padded with two zeros to make it a vector of length $4$), where $i=0, 1, 2$ will never return the label $i$ as the corresponding vectors are perpendicular. \n",
    "\n",
    "We are therefore left with the problem of implementing $M'$ as a sequence of elementary quantum gates. Notice that \n",
    "\n",
    "$$M' \\cdot {\\rm diag}(1,-1,1,-1) = M' \\cdot (\\mathbf{1}_2 \\otimes Z) = \n",
    "\\frac{1}{\\sqrt{3}}\\left(\\begin{array}{cccc}\n",
    "1 & 1 & 1 & 0 \\\\ \n",
    "1 & \\omega^2 & \\omega & 0 \\\\\n",
    "1 & \\omega & \\omega^2 & 0 \\\\\n",
    "0 & 0 & 0 & i\\sqrt{3} \n",
    "\\end{array}\n",
    "\\right)$$\n",
    "\n",
    "Using a technique used in the Rader (also sometimes called Rader-Winograd) decomposition of the discrete Fourier transform <sup><a href=\"#peres-wooters-game-ref4\">[4]</a></sup>, which reduces it to a cyclic convolution, we apply a $2\\times 2$ Fourier transform on the indices $i,j=1,2$ of this matrix (i.e. a block matrix which consists of a direct sum of blocks $\\mathbf{1}_1$, $H$, and $\\mathbf{1}_1$ which we abbreviate in short as ${\\rm diag}(1,H,1)$). \n",
    "\n",
    "> To implement this in Q#, we can use the following sequence of gates, applied to a 2-qubit array:\n",
    "> ```\n",
    "CNOT(qs[1], qs[0]);\n",
    "Controlled H([qs[0]], qs[1]);\n",
    "CNOT(qs[1], qs[0]);\n",
    "> ```\n",
    "\n",
    "This yields\n",
    "\n",
    "$${\\rm diag}(1, H, 1) \\cdot M' \\cdot (\\mathbf{1}_2 \\otimes Z) \\cdot {\\rm diag}(1, H, 1) = \n",
    "\\left(\\begin{array}{rrrr}\n",
    "\\frac{1}{\\sqrt3} & \\sqrt{\\frac23} & 0 & 0 \\\\ \n",
    "\\sqrt{\\frac23} & -\\frac{1}{\\sqrt3} & 0 & 0 \\\\\n",
    "0 & 0 & i & 0 \\\\\n",
    "0 & 0 & 0 & i \n",
    "\\end{array}\n",
    "\\right)$$\n",
    "\n",
    "This implies that after multiplication with the diagonal operator $(S^\\dagger \\otimes \\mathbf{1}_2)$, we are left with \n",
    "\n",
    "$${\\rm diag}(1, H, 1) \\cdot M' \\cdot (\\mathbf{1}_2 \\otimes Z) \\cdot {\\rm diag}(1, H, 1)\\cdot (S^\\dagger \\otimes \\mathbf{1}_2) = \n",
    "\\left(\\begin{array}{rrrr}\n",
    "\\frac{1}{\\sqrt3} & \\sqrt{\\frac23} & 0 & 0 \\\\ \n",
    "\\sqrt{\\frac23} & -\\frac{1}{\\sqrt3} & 0 & 0 \\\\\n",
    "0 & 0 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 1 \n",
    "\\end{array}\n",
    "\\right)$$\n",
    "\n",
    "which is a zero-controlled rotation $R$ around the $Y$-axis by an angle given by $\\arccos \\sqrt{\\frac23}$ (plus reordering of rows and columns). \n",
    "\n",
    "> In Q#, we can implement this matrix as the following sequence of gates, applied to a 2-qubit array:\n",
    "> ```\n",
    "CNOT(qs[1], qs[0]);\n",
    "X(qs[0]);\n",
    "let alpha = ArcCos(Sqrt(2.0 / 3.0));\n",
    "(ControlledOnInt(0, Ry))([qs[1]], (-2.0 * alpha, qs[0]));\n",
    "> ```\n",
    "\n",
    "Putting everything together, we can implement the matrix $M'$ by applying the inverses of gates:\n",
    "\n",
    "$$M' = {\\rm diag}(1,H,1) \\cdot R \\cdot (S \\otimes \\mathbf{1}_2) \\cdot {\\rm diag}(1,H,1) \\cdot (\\mathbf{1}_2 \\otimes Z)$$\n",
    "\n",
    "Noting finally, that to apply this sequence of unitaries to a column vector, we have to apply it in reverse when writing it as a program (as actions on vectors are left-associative).\n",
    "\n",
    "<a name=\"peres-wooters-game-ref1\"></a>[1]  A. Holevo.  Information-theoretical aspects of quantum measurement.  Problems of Information Transmission, vol. 9, no. 2,pp. 110–118 (1973)  \n",
    "<a name=\"peres-wooters-game-ref2\"></a>[2]  A. Peres and W. K. Wootters.  Optimal detection of quantum information.  Phys. Rev. Lett., vol. 66, pp. 1119-1122, Mar.1991.  \n",
    "<a name=\"peres-wooters-game-ref3\"></a>[3]  A. Peres.  Quantum Theory:  Concepts and Methods.  Kluwer Academic Publishers, 2002.  \n",
    "<a name=\"peres-wooters-game-ref4\"></a>[4]  C. M. Rader.  Discrete Fourier transforms when the number of data samples is prime.  Proc. IEEE 56, 1107–1108 (1968"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T203_IsQubitNotInABC\n",
    "\n",
    "open Microsoft.Quantum.Math;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation IsQubitNotInABC (q : Qubit) : Int {\n",
    "    use a = Qubit();\n",
    "    // I ⊗ 𝑍\n",
    "    Z(q);\n",
    "\n",
    "    // diag(1, H, 1)\n",
    "    CNOT(a, q);\n",
    "    Controlled H([q], a);\n",
    "    CNOT(a, q);\n",
    "\n",
    "    // S ⊗ I\n",
    "    S(a);\n",
    "\n",
    "    // Ry + row/column reordering\n",
    "    CNOT(a, q);\n",
    "    X(q);\n",
    "    let alpha = ArcCos(Sqrt(2.0 / 3.0));\n",
    "    (ControlledOnInt(0, Ry))([a], (-2.0 * alpha, q));\n",
    "\n",
    "    // diag(1, H, 1)\n",
    "    CNOT(a, q);\n",
    "    Controlled H([q], a);\n",
    "    CNOT(a, q);\n",
    "\n",
    "    // finally, measure in the standard basis\n",
    "    let res0 = MResetZ(a);\n",
    "    let res1 = M(q);\n",
    "\n",
    "    // dispatch on the cases\n",
    "    if (res0 == Zero and res1 == Zero) {\n",
    "        return 0;\n",
    "    }\n",
    "    elif (res0 == One and res1 == Zero) {\n",
    "        return 1;\n",
    "    }\n",
    "    elif (res0 == Zero and res1 == One) {\n",
    "        return 2;\n",
    "    }\n",
    "    else {\n",
    "        // this should never occur\n",
    "        return 3;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.3 of the Measurements kata.](./Measurements.ipynb#peres-wooters-game)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.24"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}