GHZGame/Workbook_GHZGame.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GHZ 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 [GHZ Game kata](./GHZGame.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 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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "There are four inputs possible, (0,0,0), (0,1,1), (1,0,1), and (1,1,0), each with 25% probability.\n",
    "Therefore, in order to win, the sum of the output bits has to be even if the input is (0,0,0) and odd otherwise.\n",
    "\n",
    "To check whether the win condition holds, you need to compute the expressions $r \\vee s \\vee t$ and $a \\oplus b \\oplus c$ and to compare them: if they are equal, the game is won. To compute the expressions, you can use either logical functions `Or` and `Xor` from the [`Microsoft.Quantum.Logical`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.logical) library."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T11_WinCondition \n",
    "\n",
    "open Microsoft.Quantum.Logical;\n",
    "\n",
    "function WinCondition (rst : Bool[], abc : Bool[]) : Bool {\n",
    "    let p = Or(rst[0], Or(rst[1], rst[2])); \n",
    "    let u = Xor(abc[0], Xor(abc[1], abc[2]));\n",
    "    return (p == u);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.1 of the GHZ Game kata.](./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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Q# namespace [Microsoft.Quantum.Random](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.random) offers a variety of operations implementing random number generation. [DrawRandomBool](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.random.drawrandombool) is particularly convenient for this task."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_RandomClassical \n",
    "\n",
    "open Microsoft.Quantum.Random;\n",
    "\n",
    "operation RandomClassicalStrategy (input : Bool) : Bool {\n",
    "    return DrawRandomBool(0.5);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.2 of the GHZ Game kata.](./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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "If all three players return TRUE, then a ⊕ b ⊕ c = TRUE by necessity (since the sum of their bits is odd).\n",
    "This will win against inputs 011, 101, and 110 and lose against 000.\n",
    "Since the four above inputs have equal probability and represent all possible inputs,\n",
    "this strategy wins with 75% probability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T13_BestClassical \n",
    "\n",
    "operation BestClassicalStrategy (input : Bool) : Bool {\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.3 of the GHZ Game kata.](./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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "You are given both the input bits and the strategy each of the players are using, so you have simply to convert them to the output bits and return those."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_PlayClassicalGHZ \n",
    "\n",
    "operation PlayClassicalGHZ (strategy : (Bool => Bool), inputs : Bool[]) : Bool[] {\n",
    "    let r = inputs[0];\n",
    "    let s = inputs[1];\n",
    "    let t = inputs[2];\n",
    "    let a = strategy(r);\n",
    "    let b = strategy(s);\n",
    "    let c = strategy(t);\n",
    "    return [a, b, c];\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can make the code a lot more concise using library operation [ForEach](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.arrays.foreach) that applies an operation to each element of an array and returns an array of results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T14_PlayClassicalGHZ \n",
    "\n",
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation PlayClassicalGHZ (strategy : (Bool => Bool), inputs : Bool[]) : Bool[] {\n",
    "    return ForEach(strategy, inputs);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1.4 of the GHZ Game kata.](./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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "1. Apply an X gate to the first and the second qubits to get the $|110\\rangle$ state.\n",
    "2. Appy an H gate to the first and the second qubits to get the following state:\n",
    "$$\\frac12 \\big( |000\\rangle - |010\\rangle - |100\\rangle + |110\\rangle \\big)$$\n",
    "3. Flip the sign of the last term using a controlled Z gate with the first qubit as control and the second qubit as target (or vice versa):\n",
    "$$\\frac12 \\big( |000\\rangle - |010\\rangle - |100\\rangle \\color{blue}- |110\\rangle \\big)$$\n",
    "4. Now we have the right signs for each term, and the first and the last terms match those of the state we're preparing, so we just need to adjust the two middle terms. \n",
    "To do this, we can use [ControlledOnBitString](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring) operation to flip the state of the last qubit if the first two qubits are in $|01\\rangle$ or in $|10\\rangle$ states, which gives us:\n",
    "$$\\frac{1}{2} \\big(|000\\rangle - |01\\color{blue}1\\rangle - |10\\color{blue}1\\rangle - |110\\rangle \\big)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_CreateEntangledTriple \n",
    "\n",
    "operation CreateEntangledTriple (qs : Qubit[]) : Unit {\n",
    "    X(qs[0]);\n",
    "    X(qs[1]);\n",
    "\n",
    "    H(qs[0]);\n",
    "    H(qs[1]);\n",
    "\n",
    "    CZ(qs[0], qs[1]);\n",
    "\n",
    "    (ControlledOnBitString([false, true], X))([qs[0], qs[1]], qs[2]);\n",
    "    (ControlledOnBitString([true, false], X))([qs[0], qs[1]], qs[2]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.1 of the GHZ Game kata.](./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": "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)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_QuantumStrategy \n",
    "\n",
    "open Microsoft.Quantum.Measurement;\n",
    "\n",
    "operation QuantumStrategy (input : Bool, qubit : Qubit) : Bool {\n",
    "    if (input) {\n",
    "        let res = MResetX(qubit);\n",
    "        return res == One;\n",
    "    }\n",
    "    else {\n",
    "        let res = MResetZ(qubit);\n",
    "        return res == One;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively, you can recall that measuring the qubit in the X basis is equivalent to applying an H gate to it and measuring it in the Z basis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_QuantumStrategy \n",
    "\n",
    "operation QuantumStrategy (input : Bool, qubit : Qubit) : Bool {\n",
    "    if (input) {\n",
    "        H(qubit);\n",
    "    }\n",
    "    return M(qubit) == One;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.2 of the GHZ Game kata.](./GHZGame.ipynb#Task-2.2.-Quantum-strategy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Discussion: Why the above strategy has a 100% win rate\n",
    "\n",
    "Recall the formula for the win condition:\n",
    "* The sum of the answer bits must be even if the question bits are (0,0,0)\n",
    "* The sum of the answer bits must be odd if the question bits are (1,1,0), (1,0,1) or (0,1,1).\n",
    "\n",
    "> As a reminder, the probability \"wavefunction\" for three qubits is given by the following vector of length 8:\n",
    ">\n",
    "> $$\n",
    "\\begin{bmatrix}\n",
    "\\psi_{000}\\\\\n",
    "\\psi_{001}\\\\\n",
    "\\psi_{010}\\\\\n",
    "\\psi_{011}\\\\\n",
    "\\psi_{100}\\\\\n",
    "\\psi_{101}\\\\\n",
    "\\psi_{110}\\\\\n",
    "\\psi_{111}\n",
    "\\end{bmatrix}\n",
    "$$\n",
    ">\n",
    "> $|\\psi_{ijk}|^2$ gives the probability of observing the corresponding basis state $|ijk\\rangle$ upon measuring the qubit trio.\n",
    "\n",
    "Now, the entangled state $|\\Phi\\rangle$ that Alice, Bob and Charlie have agreed to use is represented as\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "+1/2\\\\\n",
    " 0\\\\\n",
    " 0\\\\\n",
    "-1/2\\\\\n",
    " 0\\\\\n",
    "-1/2\\\\\n",
    "-1/2\\\\\n",
    " 0\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Let's first consider the case in which **all three players got the 0 bit**.\n",
    "\n",
    "When the players make their measurements, they will collectively get one of the basis states of the original state - 000, 011, 101 or 110. This measn they'll report back zero \"1\" bits between them (with 25% probability) or two \"1\" bits between them (with 75% probability), either way satisfying the win condition for the team.\n",
    "\n",
    "Now, suppose **Alice gets a 0 bit and the others get 1**.\n",
    "\n",
    "Alice, looking at the 0, takes a Z basis measurement as before, while Bob and Charlie each take X basis measurements. \n",
    "(An X basis measurement is also equivalent to performing a Hadamard transform followed by a standard Z basis measurement, as the X basis is the $| + \\rangle$ / $| - \\rangle$, and a Hadamard transform rotates the $| 0 \\rangle$ / $| 1 \\rangle$ basis to $| + \\rangle$ / $| - \\rangle$.) \n",
    "So Bob and Charlie apply a Hadamard transform to their qubits, which corresponds to the following transformation applied to the whole system state:\n",
    "\n",
    "$$\n",
    "I \\otimes H \\otimes H = \\begin{bmatrix}\n",
    "1/2 & 1/2 & 1/2 & 1/2 & 0 & 0 & 0 & 0\\\\\n",
    "1/2 & -1/2 & 1/2 & -1/2 & 0 & 0 & 0 & 0\\\\\n",
    "1/2 & 1/2 & -1/2 & -1/2 & 0 & 0 & 0 & 0\\\\\n",
    "1/2 & -1/2 & -1/2 & 1/2 & 0 & 0 & 0 & 0\\\\\n",
    "0 & 0 & 0 & 0 & 1/2 & 1/2 & 1/2 & 1/2\\\\\n",
    "0 & 0 & 0 & 0 & 1/2 & -1/2 & 1/2 & -1/2\\\\\n",
    "0 & 0 & 0 & 0 & 1/2 & 1/2 & -1/2 & -1/2\\\\\n",
    "0 & 0 & 0 & 0 & 1/2 & -1/2 & -1/2 & 1/2\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "When applied to the original entangled state, all the amplitude shifts to the states corresponding to $|001\\rangle$, $|010\\rangle$, $|100\\rangle$, and $|111\\rangle$.  The precise configuration of the new entangled state is\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    " 0\\\\\n",
    " 1/2\\\\\n",
    " 1/2\\\\\n",
    " 0\\\\\n",
    "-1/2\\\\\n",
    " 0\\\\\n",
    " 0\\\\\n",
    " 1/2\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Now the players perform their measurements, and an odd number of them will see \"1\" (thanks to the new entangled state), again satisfying the win condition.  \n",
    "\n",
    "Similarly, if **Alice and Charlie get \"1\" bits and Bob a \"0\"**, Alice and Charlie will apply Hadamard transforms to their qubits to give the tensor product\n",
    "\n",
    "$$\n",
    "H \\otimes I \\otimes H = \\begin{bmatrix}\n",
    "1/2 & 1/2  & 0   & 0    & 1/2  & 1/2  & 0    & 0\\\\\n",
    "1/2 & -1/2 & 0   & 0    & 1/2  & -1/2 & 0    & 0\\\\\n",
    "0   & 0    & 1/2 & 1/2  & 0    & 0    & 1/2  & 1/2\\\\\n",
    "0   & 0    & 1/2 & -1/2 & 0    & 0    & 1/2  & -1/2\\\\\n",
    "1/2 & 1/2  & 0   & 0    & -1/2 & -1/2 & 0    & 0\\\\\n",
    "1/2 & -1/2 & 0   & 0    & -1/2 & 1/2  & 0    & 0\\\\\n",
    "0   & 0    & 1/2 & 1/2  & 0    & 0    & -1/2 & -1/2\\\\\n",
    "0   & 0    & 1/2 & -1/2 & 0    & 0    & -1/2 & 1/2\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "The resulting state vector before the measurement will be the same as in the previous case, except that the $|010\\rangle$ state ends up with the negative amplitude instead of $|100\\rangle$.  Again the players report back an odd number of true bits between them and the team wins.\n",
    "\n",
    "Finally if Charlie got the \"0\" bit and Alice and Bob both got \"1\", the latter two will apply Hadamard transform for the tensor product\n",
    "\n",
    "$$\n",
    "H \\otimes H \\otimes I = \\begin{bmatrix}\n",
    "1/2 & 0 & 1/2 & 0 & 1/2 & 0 & 1/2 & 0\\\\\n",
    "0 & 1/2 & 0 & 1/2 & 0 & 1/2 & 0 & 1/2\\\\\n",
    "1/2 & 0 & -1/2 & 0 & 1/2 & 0 & -1/2 & 0\\\\\n",
    "0 & 1/2 & 0 & -1/2 & 0 & 1/2 & 0 & -1/2\\\\\n",
    "1/2 & 0 & 1/2 & 0 & -1/2 & 0 & -1/2 & 0\\\\\n",
    "0 & 1/2 & 0 & 1/2 & 0 & -1/2 & 0 & -1/2\\\\\n",
    "1/2 & 0 & -1/2 & 0 & -1/2 & 0 & 1/2 & 0\\\\\n",
    "0 & 1/2 & 0 & -1/2 & 0 & -1/2 & 0 & 1/2\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Operating with this on the original entangled state yields $(|100\\rangle + |010\\rangle - |001\\rangle + |111\\rangle)/2$ and once more the team will report back an odd number of true bits between them and win."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.2 of the GHZ Game kata.](./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": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Putting together the building blocks we've implemented into a strategy is very simple:\n",
    "\n",
    "1. Allocate three qubits and prepare our entangled state on them (using `CreateEntangledTriple` from task 2.1).\n",
    "2. Send one of the qubits to each of the players (this step is \"virtual\", not directly reflected in Q# code, other than making sure that the strategies each act on their qubit only).\n",
    "3. Have the players perform their measurements on their respective qubits using corresponding elements of the `strategies` array.\n",
    "4. Return their measurement results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_PlayQuantumGHZ \n",
    "\n",
    "operation PlayQuantumGHZ (strategies : (Qubit => Bool)[]) : Bool[] {\n",
    "    using (ghz = Qubit[3]) {\n",
    "        CreateEntangledTriple(ghz);\n",
    "\n",
    "        let a = strategies[0](ghz[0]);\n",
    "        let b = strategies[1](ghz[1]);\n",
    "        let c = strategies[2](ghz[2]);\n",
    "\n",
    "        return [a, b, c];\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2.3 of the GHZ Game kata.](./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
}