CHSHGame/Workbook_CHSHGame.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CHSH Game 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 [CHSH Game kata](./CHSHGame.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."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Classical CHSH\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. Win Condition\n",
    "**Input:** \n",
    "\n",
    "  1. Alice and Bob's starting bits (X and Y),\n",
    "\n",
    "  2. Alice and Bob's output bits (A and B).\n",
    "\n",
    "**Output:** \n",
    "True if Alice and Bob won the CHSH game, that is, if X ∧ Y = A ⊕ B, and false otherwise."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "There are four input pairs (X, Y) possible, (0,0), (0,1), (1,0), and (1,1), each with 25% probability.\n",
    "In order to win, Alice and Bob have to output different bits if the input is (1,1), and same bits otherwise.\n",
    "\n",
    "To check whether the win condition holds, you need to compute $x \\wedge y$ and $a \\oplus b$ and to compare these values: if they are equal, Alice and Bob won. [`Microsoft.Quantum.Logical`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.logical) library offers you logical functions `And` and `Xor` which you can use for this computation. Alternatively, you can compute these values using built-in operators: $x \\wedge y$ as `x and y` and $a \\oplus b$ as `a != b`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_WinCondition \n",
    "\n",
    "open Microsoft.Quantum.Logical;\n",
    "\n",
    "function WinCondition (x : Bool, y : Bool, a : Bool, b : Bool) : Bool {\n",
    "    let p = And(x, y);\n",
    "    let u = Xor(a, b);\n",
    "    return (p == u);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.1 of the CHSH Game kata.](./CHSHGame.ipynb#Task-1.1.-Win-Condition)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Alice and Bob's classical strategy\n",
    "\n",
    "In this task you have to implement two functions, one for Alice's classical strategy and one for Bob's.\n",
    "Note that they are covered by one test, so you have to implement both to pass the test. Once you implement one of the strategies, execute its cell - it will fail with the error message indicating that the other strategy is not implemented yet. Once you implement the second strategy, execute its cell to get the test result.\n",
    "\n",
    "**Input:** Alice's OR Bob's starting bit (X or Y, respectively).\n",
    "\n",
    "**Output:** The bit that Alice OR Bob should output (A or B, respectively) to maximize their chance of winning."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "If Alice and Bob always return TRUE, they will have a 75% win rate,\n",
    "since TRUE ⊕ TRUE = FALSE, and the AND operation on their input bits will be false with 75% probability.\n",
    "\n",
    "Alternatively, Alice and Bob could agree to always return FALSE to achieve the same 75% win probability.\n",
    "A classical strategy cannot achieve a higher success probability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "raises-exception"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T12_ClassicalStrategy \n",
    "\n",
    "operation AliceClassical (x : Bool) : Bool {\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_ClassicalStrategy \n",
    "\n",
    "operation BobClassical (y : Bool) : Bool {\n",
    "    // Alternatively, Alice and Bob could agree to always return FALSE to achieve the same 75% win chances.\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.2 of the CHSH Game kata.](./CHSHGame.ipynb#Task-1.2.-Alice-and-Bob's-classical-strategy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Quantum CHSH\n",
    "\n",
    "In the quantum version of the game, the players still can not\n",
    "communicate during the game, but they are allowed to share \n",
    "qubits from a Bell pair before the start of the game.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. Entangled pair\n",
    "\n",
    "**Input:** An array of two qubits in the $|00\\rangle$ state.\n",
    "\n",
    "**Goal:** Create a Bell state $|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big( |00\\rangle + |11\\rangle \\big)$ on these qubits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "You can find a detailed explanation of the solution to this task in the [Superposition kata workbook](../Superposition/Workbook_Superposition.ipynb#bell-state)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_CreateEntangledPair \n",
    "\n",
    "operation CreateEntangledPair (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    // This performs a Hadamard transform on the first qubit\n",
    "    // which produces the intermediate state (|00> + |10>) / sqrt(2).\n",
    "    \n",
    "    CX(qs[0], qs[1]);\n",
    "    // CX (Controlled X, Controlled NOT, CNOT) operates on two qubits, putting the second qubit through a NOT gate\n",
    "    // if and only if the first qubit is '1'.\n",
    "    \n",
    "    // The 4x4 operator matrix for CX is:\n",
    "    // [1  0  0  0]\n",
    "    // [0  1  0  0]\n",
    "    // [0  0  0  1]\n",
    "    // [0  0  1  0]\n",
    "    \n",
    "    // The original state |00> corresponds to the two-qubit amplitude vector [1, 0, 0, 0].\n",
    "    \n",
    "    // The state after the Hadamard transform is given by the column vector [1/sqrt(2), 0, 1/sqrt(2), 0].\n",
    "    \n",
    "    // The CX operator changes this vector to [1/sqrt(2), 0, 0, 1/sqrt(2)], which is the desired Bell state.\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.1 of the CHSH Game kata.](./CHSHGame.ipynb#Task-2.1.-Entangled-pair)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Alice's quantum strategy\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. Alice's starting bit (X),\n",
    "\n",
    "  2. Alice's half of Bell pair she shares with Bob.\n",
    "\n",
    "**Goal:** Measure Alice's qubit in the Z basis if her bit is 0 (false), or the X basis if her bit is 1 (true), and return the result.\n",
    "The state of the qubit after the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "In Q#, you can perform measurements in a specific basis using either the \n",
    "[Measure operation](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.measure) \n",
    "or convenient shorthands for measure-and-reset-to-$|0\\rangle$ sequence of operations \n",
    "[MResetZ](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.measurement.mresetz) and \n",
    "[MResetX](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.measurement.mresetx).\n",
    "\n",
    "(See the [discussion](#discussion) below for details on why Alice should follow this strategy.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_AliceQuantum \n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation AliceQuantum (bit : Bool, qubit : Qubit) : Bool {\n",
    "    if bit {\n",
    "        let q = MResetX(qubit);\n",
    "        return (q == One);\n",
    "    }\n",
    "    else {\n",
    "        let q = MResetZ(qubit);\n",
    "        return (q == One);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.2 of the CHSH Game kata.](./CHSHGame.ipynb#Task-2.2.-Alice's-quantum-strategy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. Rotate Bob's qubit\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. The direction to rotate: true for clockwise, false for counterclockwise,\n",
    "\n",
    "  2. Bob's qubit.\n",
    "\n",
    "**Goal:** Rotate the qubit $\\frac{\\pi}{8}$ radians around the Y axis in the given direction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "In Q#, you can perform rotations around a specific axis using one of the rotation gates. \n",
    "In our case the axis is Y, and the corresponding rotation gate is [Ry](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry).\n",
    "\n",
    "Note that in the $R_y(\\theta)$ matrix entries, the trigonometric functions are actually performed on $\\frac{\\theta}{2}$, so the angle input into the function has to be doubled.\n",
    "\n",
    "(See the [discussion](#discussion) below for details on why Bob should rotate the qubit.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_RotateBobQubit \n",
    "\n",
    "open Microsoft.Quantum.Math;\n",
    "\n",
    "operation RotateBobQubit (clockwise : Bool, qubit : Qubit) : Unit {\n",
    "    mutable dir = PI() / 8.0;\n",
    "    if clockwise {\n",
    "        set dir = dir * -1.0;\n",
    "    }\n",
    "    Ry(2.0 * dir, qubit);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.3 of the CHSH Game kata.](./CHSHGame.ipynb#Task-2.3.-Rotate-Bob's-qubit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.4. Bob's quantum strategy\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. Bob's starting bit (Y),\n",
    "\n",
    "  2. Bob's half of Bell pair he shares with Alice.\n",
    "\n",
    "**Goal:** Measure Bob's qubit in the $\\frac{\\pi}{8}$ basis if his bit is 0 (false), or the $-\\frac{\\pi}{8}$ basis if his bit is 1 (true), and return the result.\n",
    "The state of the qubit after the operation does not matter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Measuring a qubit in the $\\theta$ basis is the same as rotating the qubit by $\\theta$, clockwise, and then making a standard measurement in the Z basis.\n",
    "\n",
    "To implement the described transformation in Q#, we need to rotate the qubit by $\\frac{\\pi}{8}$ clockwise if `bit = false` or counterclockwise if `bit = true` and then perform a measurement. \n",
    "We can do the rotation using the previous task (note the negation of the boolean parameter we need to do).\n",
    "\n",
    "(See the [discussion](#discussion) below for details on why Bob should follow this strategy.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_BobQuantum \n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation BobQuantum (bit : Bool, qubit : Qubit) : Bool {\n",
    "    RotateBobQubit(not bit, qubit);\n",
    "    return M(qubit) == One;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.4 of the CHSH Game kata.](./CHSHGame.ipynb#Task-2.4.-Bob's-quantum-strategy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.5. Play the CHSH game using the quantum strategy\n",
    "\n",
    "**Input:**\n",
    "Operations that return Alice and Bob's output bits (A and B) based on their quantum\n",
    "strategies and given their respective qubits from the Bell pair.\n",
    "Alice and Bob have already been told what their starting bits X and Y are.\n",
    "\n",
    "**Goal:** Return Alice and Bob's output bits (A, B).\n",
    "Note that this task uses strategies `AliceQuantum` and `BobQuantum`, which you've implemented in tasks 2.2 and 2.4, respectively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Putting together the building blocks we've implemented into a strategy is very simple:\n",
    "\n",
    "1. Allocate two qubits and prepare a Bell state on them (using `CreateEntangledPair` from task 2.1).\n",
    "2. Send one of the qubits to Alice and another to Bob (this step is \"virtual\", not directly reflected in Q# code, other than making sure that Alice and Bob each act on their qubit only).\n",
    "3. Have Alice and Bob perform their measurements on their respective qubits using `askAlice` and `askBob` operations.\n",
    "4. Return their measurement results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T25_PlayQuantumCHSH \n",
    "\n",
    "operation PlayQuantumCHSH (askAlice : (Qubit => Bool), askBob : (Qubit => Bool)): (Bool, Bool) {\n",
    "    use bell = Qubit[2];\n",
    "    CreateEntangledPair(bell);\n",
    "\n",
    "    let A = askAlice(bell[0]);\n",
    "    let B = askBob(bell[1]);\n",
    "\n",
    "    return (A, B);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.5 of the CHSH Game kata.](./CHSHGame.ipynb#Task-2.5.-Play-the-CHSH-game-using-the-quantum-strategy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a name=\"discussion\"></a>Discussion: probability of victory for quantum strategy\n",
    "\n",
    "The above quantum strategy adopted by Alice and Bob offers a win rate of $\\frac{2 + \\sqrt{2}}{4}$, or about 85.36%. Let's see why this is the case.\n",
    "\n",
    "First, consider the outcome if Alice and Bob simply measure their qubits in the Z basis without manipulating them at all.  Because of the entanglement inherent to the Bell state they hold, their measurements will always agree (i.e., both true or both false).  \n",
    "This will suffice for victory in the three scenarios (0,0), (0,1) and (1,0) and fail for (1,1), so their win probability is 75%, the same as that for the straightforward classical strategies of invariably returning both true or both false.\n",
    "\n",
    "Now let's analyze the optimal quantum strategy.\n",
    "\n",
    "> As a reminder, probability \"wavefunction\" for a two-qubit state is given by the following length-4 vector of amplitudes:\n",
    "> \n",
    "> $$\n",
    "\\begin{bmatrix}\n",
    "\\psi_{00}\\\\\n",
    "\\psi_{01}\\\\\n",
    "\\psi_{10}\\\\\n",
    "\\psi_{11}\n",
    "\\end{bmatrix}\n",
    "$$\n",
    ">\n",
    "> $|\\psi_{ij}|^2$ gives the probability of observing the corresponding basis state $|ij\\rangle$ upon measuring the qubit pair.\n",
    "\n",
    "The initial state $|00\\rangle$ has $\\psi_{00} = 1$ and $\\psi_{01} = \\psi_{10} = \\psi_{11} = 0$.  \n",
    "The Bell state we prepare as the first step of the game has an amplitude vector as follows (we'll use decimal approximations for matrix elements):\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "1/\\sqrt{2}\\\\\n",
    "0\\\\\n",
    "0\\\\\n",
    "1/\\sqrt{2}\n",
    "\\end{bmatrix} = \n",
    "\\begin{bmatrix}\n",
    "0.7071\\\\\n",
    "0\\\\\n",
    "0\\\\\n",
    "0.7071\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Let's analyze the probabilities of outcomes in case of different bits received by players.\n",
    "\n",
    "#### Case 1: Alice holds bit 0\n",
    "\n",
    "In this case Alice simply measures in the Z basis as above.  \n",
    "\n",
    "* When Bob's bit is 0, he rotates his qubit clockwise by $\\pi/8$, which corresponds to the operator\n",
    "\n",
    "  $$\n",
    "\\begin{bmatrix}\n",
    "0.9239 & 0.3827 & 0 & 0\\\\\n",
    "-0.3827 & 0.9239 & 0 & 0\\\\\n",
    "0 & 0 & 0.9239 & 0.3827\\\\\n",
    "0 & 0 & -0.3827 & 0.9239\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "  This performs the $R_y$ rotation by $\\pi/8$ radians clockwise on Bob's qubit while leaving Alice's qubit unchanged.\n",
    "\n",
    "* If Bob's bit were 1, he would rotate his qubit counterclockwise by $\\pi/8$, applying a very similar operator\n",
    "\n",
    " $$\n",
    "\\begin{bmatrix}\n",
    "0.9239 & -0.3827 & 0 & 0\\\\\n",
    "0.3827 & 0.9239 & 0 & 0\\\\\n",
    "0 & 0 & 0.9239 & -0.3827\\\\\n",
    "0 & 0 & 0.3827 & 0.9239\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Therefore, when Alice has bit 0, the application of the rotation operator to the Bell state gives\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0.6533 \\\\\n",
    "-0.2706 \\\\\n",
    "0.2706 \\\\\n",
    "0.6533 \n",
    "\\end{bmatrix} \\text{ or }\n",
    "\\begin{bmatrix}\n",
    "0.6533\\\\\n",
    "0.2706\\\\\n",
    "-0.2706\\\\\n",
    "0.6533\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "depending on whether Bob holds 0 (left-hand case) or 1 (right-hand case).  \n",
    "\n",
    "The result of AND on their input bits will always be 0; thus they win when their outputs agree.  These two cases correspond to the top and bottom elements of the vectors above, with a combined probability of $(0.6533)^2 + (0.6533)^2 = 0.4268 + 0.4268 = 0.8536$, so they have an 85.36% win chance.\n",
    "\n",
    "#### Case 2: Alice holds bit 1\n",
    "\n",
    "When Alice holds bit 1, she measures in basis X (or, equivalently, Hadamard-transforms her qubit, leaving Bob's be, before making her Z-basis measurement).  This corresponds to applying the operator\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0.7071 & 0 & 0.7071 & 0\\\\\n",
    "0 & 0.7071 & 0 & 0.7071\\\\\n",
    "0.7071 & 0 & -0.7071 & 0\\\\\n",
    "0 & 0.7071 & 0 & -0.7071\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "to the Bell state, resulting in a vector of:\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0.5\\\\\n",
    "0.5\\\\\n",
    "0.5\\\\\n",
    "-0.5\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Now, one of the two rotation operators is applied depending on what bit Bob holds, transforming this vector into:\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0.6533 \\\\\n",
    "0.2706 \\\\\n",
    "0.2706 \\\\\n",
    "-0.6533\n",
    "\\end{bmatrix} \\text{ or }\n",
    "\\begin{bmatrix}\n",
    "0.2706\\\\\n",
    "0.6533\\\\\n",
    "0.6533\\\\\n",
    "-0.2706\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "When Bob holds 0, they still want to return the same parity, which they again do with 85.36% probability (left-hand vector above). \n",
    "But when Bob holds 1, the AND condition is now true and the players want to answer in opposite parity.  This corresponds to the second and third elements of the right-hand vector above. \n",
    "Thanks to the \"magic\" of the combination of the counterclockwise rotation and Hadamard transform, they now do this with probability $(0.6533)^2 + (0.6533)^2 = 0.8536$ and thus 85.36% becomes their win odds once more.\n",
    "\n",
    "#### Side notes\n",
    "\n",
    "* If Bob never rotated his qubit, their entangled state would remain the Bell state if Alice held bit 0 and the state corresponding to $\\frac12 \\big(|00\\rangle + |01\\rangle + |10\\rangle - |11\\rangle\\big)$ if Alice held bit 1.  \n",
    "While she and Bob would have a 100% success probability against Alice's 0 bit, they would have only a 50% chance of success if she held bit 1, and thus their win chance would revert to the 75% of the classical strategy again.\n",
    "\n",
    "* It can be proven that Alice and Bob cannot surpass an overall win probability of 85.36% in the CHSH game.  This entails a higher-level discussion of quantum observable theory, for instance see [Tsirelson's bound](https://en.wikipedia.org/wiki/Tsirelson's_bound)."
   ]
  }
 ],
 "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
}