CHSHGame/CHSHGame.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CHSH Game\n",
    "\n",
    "The **CHSH Game** quantum kata is a series of exercises designed\n",
    "to get you familiar with the CHSH game.\n",
    "\n",
    "In it, two players (Alice and Bob) try to win the following game:\n",
    "\n",
    "Each of them is given a bit (Alice gets X and Bob gets Y), and\n",
    "they have to return new bits (Alice returns A and Bob returns B)\n",
    "so that X ∧ Y = A ⊕ B. The trick is, they can not communicate during the game.\n",
    "\n",
    "> * ∧ is the standard bitwise AND operator.\n",
    "> * ⊕ is the exclusive or, or XOR operator, so (P ⊕ Q) is true if exactly one of P and Q is true.\n",
    "\n",
    "* You can read more about CHSH game in the [lecture notes](https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.20.pdf) by\n",
    "  John Watrous. \n",
    "* Q# Samples repository has [an implementation of the CHSH\n",
    "  game](https://github.com/microsoft/Quantum/tree/main/samples/algorithms/chsh-game)\n",
    "  that includes an explanation of the history and theory behind the game.\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "Your goal is to fill in the blank (marked with the `// ...` comments)\n",
    "with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).\n"
   ]
  },
  {
   "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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_WinCondition \n",
    "\n",
    "function WinCondition (x : Bool, y : Bool, a : Bool, b : Bool) : Bool {\n",
    "    // ...\n",
    "    fail \"Task 1.1 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [CHSH Game Workbook](./Workbook_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 starting bit (X).\n",
    "\n",
    "**Output:** The bit that Alice should output (A) to maximize their chance of winning."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T12_ClassicalStrategy \n",
    "\n",
    "operation AliceClassical (x : Bool) : Bool {\n",
    "    // ...\n",
    "    fail \"Alice's strategy in task 1.2 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Input:** Bob's starting bit (Y).\n",
    "\n",
    "**Output:** The bit that Bob should output (B) to maximize their chance of winning."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T12_ClassicalStrategy \n",
    "\n",
    "operation BobClassical (y : Bool) : Bool {\n",
    "    // ...\n",
    "    fail \"Bob's strategy in task 1.2 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [CHSH Game Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_CreateEntangledPair \n",
    "\n",
    "operation CreateEntangledPair (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "    fail \"Task 2.1 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [CHSH Game Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_AliceQuantum \n",
    "\n",
    "operation AliceQuantum (bit : Bool, qubit : Qubit) : Bool {\n",
    "    // ...\n",
    "    fail \"Task 2.2 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [CHSH Game Workbook](./Workbook_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.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary><b>Need a hint? Click here</b></summary>\n",
    "  <a href=\"https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry\">Ry gate</a> applies a rotation by a given angle in counterclockwise direction.\n",
    "</details>"
   ]
  },
  {
   "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",
    "    // ...\n",
    "    fail \"Task 2.3 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [CHSH Game Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_BobQuantum \n",
    "\n",
    "operation BobQuantum (bit : Bool, qubit : Qubit) : Bool {\n",
    "    // ...\n",
    "    fail \"Task 2.4 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [CHSH Game Workbook](./Workbook_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": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T25_PlayQuantumCHSH \n",
    "\n",
    "operation PlayQuantumCHSH (askAlice : (Qubit => Bool), askBob : (Qubit => Bool)): (Bool, Bool) {\n",
    "    // ...\n",
    "    fail \"Task 2.5 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [CHSH Game Workbook](./Workbook_CHSHGame.ipynb#Task-2.5.-Play-the-CHSH-game-using-the-quantum-strategy).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*See the detailed discussion of the quantum strategy in the [CHSH Game Workbook](./Workbook_CHSHGame.ipynb#discussion).*"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}