GHZGame/GHZGame.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GHZ Game\n",
    "\n",
    "The **GHZ Game** quantum kata is a series of exercises designed\n",
    "to get you familiar with the GHZ game.\n",
    "\n",
    "In it three players (Alice, Bob and Charlie) try to win the following game:\n",
    "\n",
    "Each of them is given a bit (r, s and t respectively), and\n",
    "they have to return new bits (a, b and c respectively) so\n",
    "that  r ∨ s ∨ t = a ⊕ b ⊕ c. The input bits will have\n",
    "zero or two bits set to true and three or one bits set to false.\n",
    "The trick is, the players can not communicate during the game.\n",
    "\n",
    "* ∨ is the standard bitwise OR 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",
    "\n",
    "* You can read more about the GHZ game in the [lecture notes](https://cs.uwaterloo.ca/~watrous/CPSC519/LectureNotes/20.pdf) by John Watrous. \n",
    "* Another description can be found in the [lecture notes](https://staff.fnwi.uva.nl/m.walter/physics491/lecture1.pdf) by Michael Walter.\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 GHZ\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1. Win Condition\n",
    "**Inputs:** \n",
    "\n",
    "  1. Alice, Bob and Charlie's input bits (r, s and t), stored as an array of length 3,\n",
    "\n",
    "  2. Alice, Bob and Charlie's output bits (a, b and c), stored as an array of length 3.\n",
    "\n",
    "The input bits will have zero or two bits set to true.\n",
    "\n",
    "**Output:** \n",
    "True if Alice, Bob and Charlie won the GHZ game, that is, if r ∨ s ∨ t = a ⊕ b ⊕ c, and false otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_WinCondition \n",
    "\n",
    "function WinCondition (rst : Bool[], abc : 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 [GHZ Game Workbook](./Workbook_GHZGame.ipynb#Task-1.1.-Win-Condition).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Random classical strategy\n",
    "\n",
    "**Input:** The input bit for one of the players (r, s or t).\n",
    "\n",
    "**Output:** A random bit that this player will output (a, b or c).\n",
    "\n",
    "If all players use this strategy, they will win about 50% of the time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_RandomClassical \n",
    "\n",
    "operation RandomClassicalStrategy (input : Bool) : Bool {\n",
    "    // ...\n",
    "    fail \"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 [GHZ Game Workbook](./Workbook_GHZGame.ipynb#Task-1.2.-Random-classical-strategy).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.3. Best classical strategy\n",
    "\n",
    "**Input:** The input bit for one of the players (r, s or t).\n",
    "\n",
    "**Output:** A bit that this player will output (a, b or c) to maximize their chance of winning.\n",
    "\n",
    "All players will use the same strategy.\n",
    "The best classical strategy should win about 75% of the time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_BestClassical \n",
    "\n",
    "operation BestClassicalStrategy (input : Bool) : Bool {\n",
    "    // ...\n",
    "    fail \"Task 1.3 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [GHZ Game Workbook](./Workbook_GHZGame.ipynb#Task-1.3.-Best-classical-strategy).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.4. Referee classical GHZ game\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "  1. An operation which implements a classical strategy (i.e., takes an input bit and produces an output bit),\n",
    "\n",
    "  2. An array of 3 input bits that should be passed to the players.\n",
    "\n",
    "**Output:** \n",
    "An array of 3 bits that will be produced if each player uses this strategy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_PlayClassicalGHZ \n",
    "\n",
    "operation PlayClassicalGHZ (strategy : (Bool => Bool), inputs : Bool[]) : Bool[] {\n",
    "    // ...\n",
    "    fail \"Task 1.4 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Can't come up with a solution? See the explained solution in the [GHZ Game Workbook](./Workbook_GHZGame.ipynb#Task-1.4.-Referee-classical-GHZ-game).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Quantum GHZ\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 an entangled triple before the start of the game.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. Entangled triple\n",
    "\n",
    "**Input:** An array of three qubits in the $|000\\rangle$ state.\n",
    "\n",
    "**Goal:** Create the entangled state $|\\Phi\\rangle = \\frac{1}{2} \\big(|000\\rangle - |011\\rangle - |101\\rangle - |110\\rangle \\big)$ on these qubits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_CreateEntangledTriple \n",
    "\n",
    "operation CreateEntangledTriple (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 [GHZ Game Workbook](./Workbook_GHZGame.ipynb#Task-2.1.-Entangled-triple).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Quantum strategy\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. The input bit for one of the players (r, s or t),\n",
    "\n",
    "  2. That player's qubit of the entangled triple shared between the players.\n",
    "\n",
    "**Goal:** Measure the qubit in the Z basis if the bit is 0 (false), or the X basis if the bit is 1 (true), and return the result.\n",
    "\n",
    "The state of the qubit after the operation does not matter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_QuantumStrategy \n",
    "\n",
    "operation QuantumStrategy (input : 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 [GHZ Game Workbook](./Workbook_GHZGame.ipynb#Task-2.2.-Quantum-strategy).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. Play the GHZ game using the quantum strategy\n",
    "\n",
    "**Input:** Operations that return Alice, Bob and Charlie's output bits (a, b and c) based on\n",
    "their quantum strategies and given their respective qubits from the entangled triple.\n",
    "The players have already been told what their starting bits (r, s and t) are.\n",
    "\n",
    "**Goal:** Return an array of players' output bits (a, b and c)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_PlayQuantumGHZ \n",
    "\n",
    "operation PlayQuantumGHZ (strategies : (Qubit => Bool)[]) : Bool[] {\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 [GHZ Game Workbook](./Workbook_GHZGame.ipynb#Task-2.3.-Play-the-GHZ-game-using-the-quantum-strategy).*"
   ]
  }
 ],
 "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
}