MagicSquareGame/MagicSquareGame.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Magic Square Game\n",
    "\n",
    "The **Magic Square Game** quantum kata is a series of exercises designed\n",
    "to get you familiar with the Mermin-Peres magic square game.\n",
    "\n",
    "In it two players (Alice and Bob) try to win the game in which they\n",
    "have to fill one row and one column of a 3x3 table with plus and minus signs.\n",
    "\n",
    "Alice is given an index of a _row_ and has to fill that row\n",
    "so that it has an _even_ number of minus signs.\n",
    "Bob is given an index of a _column_ and has to fill that column\n",
    "so that it has an _odd_ number of minus signs.\n",
    "The sign in the cell that belongs to the intersection of Alice's row and Bob's column\n",
    "has to match in both Alice's and Bob's answers.\n",
    "The trick is, the players can not communicate during the game.\n",
    "\n",
    "* You can read more about Mermin-Peres magic square game [on Wikipedia](https://en.wikipedia.org/wiki/Quantum_pseudo-telepathy#The_Mermin-Peres_magic_square_game).\n",
    "* It is also described in Exercise 4 from the [assignment](http://edu.itp.phys.ethz.ch/fs13/atqit/sol01.pdf) from Advanced Topics in Quantum Information Theory course by Christandl and Renner.\n",
    "* And in a [blog post](http://twistedoakstudios.com/blog/Post6536_implementing-quantum-pseudo-telepathy) by Craig Gidney.\n",
    "\n",
    "Each task is wrapped in one operation preceded by the description of the task.\n",
    "Your goal is to fill in the blanks (marked with the `// ...` comments)\n",
    "with some Q# code that solves the task.  To verify your answer, run the cell with Ctrl+Enter (⌘+Enter on macOS).\n",
    "\n",
    "Within each section, tasks are given in approximate order of increasing difficulty;\n",
    "harder ones are marked with asterisks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part I. Classical Magic Square Game\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1.1. Validate Alice's  move\n",
    "\n",
    "In this task you have to implement function for validating Alice's move.\n",
    "\n",
    "**Input:** \n",
    "  The signs Alice chose for each cell in her row,\n",
    "  represented as an `Int` array of length 3.\n",
    "\n",
    "**Output:**\n",
    "  `true` if Alice's move is valid (every cell is either +1 or -1 and\n",
    "  the array has an even number of minus signs), and `false` otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T111_ValidAliceMove \n",
    "\n",
    "function ValidAliceMove (cells : Int[]) : Bool {\n",
    "    // ...\n",
    "    fail \"Validating Alice's move in task 1.1.1 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.1.2. Validate Bob's move\n",
    "\n",
    "In this task you have to implement function for validating Bob's move.\n",
    "\n",
    "**Input:** \n",
    "  The signs Bob chose for each cell in his column,\n",
    "  represented as an `Int` array of length 3.\n",
    "\n",
    "**Output:**\n",
    "  `true` if Bob's move is valid (every cell is either +1 or -1 and\n",
    "  the array has an odd number of minus signs), and `false` otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T112_ValidBobMove \n",
    "\n",
    "function ValidBobMove (cells : Int[]) : Bool {\n",
    "    // ...\n",
    "    fail \"Validating Bob's move in task 1.1.2 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.2. Win condition\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. The row and column indices Alice and Bob were assigned. Each index will be between 0 and 2, inclusive.\n",
    "\n",
    "  2. Alice and Bob's moves, represented as `Int` arrays of length 3.\n",
    "\n",
    "**Output:**\n",
    "  `true` if Alice and Bob won the game (that is, if both their moves are valid and\n",
    "  they chose the same sign in the cell on the intersection of Alice's row and Bob's column),\n",
    "  and `false` otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T12_WinCondition \n",
    "\n",
    "function WinCondition (rowIndex : Int, columnIndex : Int, row : Int[], column : Int[]) : Bool {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 1.3. 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 before attempting 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",
    "The classical strategy should win about 89% of the time.\n",
    "\n",
    "**Input:**\n",
    "  The index of Alice's row.\n",
    "\n",
    "**Output:**\n",
    "  The signs Alice should place in her row (as an `Int` array of length 3).\n",
    "  +1 indicates plus sign, -1 - minus sign."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T13_ClassicalStrategy \n",
    "\n",
    "function AliceClassical (rowIndex : Int) : Int[] {\n",
    "    // ...\n",
    "    fail \"Alice's strategy in task 1.3 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Input:**\n",
    "  The index of Bob's column.\n",
    "\n",
    "**Output:**\n",
    "  The signs Bob should place in his column (as an `Int` array of length 3).\n",
    "  +1 indicates plus sign, -1 - minus sign."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T13_ClassicalStrategy \n",
    "\n",
    "function BobClassical (columnIndex : Int) : Int[] {\n",
    "    // ...\n",
    "    fail \"Bob's strategy in task 1.3 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part II. Quantum Magic Square Game\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 two entangled pairs before the start of the game.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.1. Entangled state\n",
    "\n",
    "**Input:**\n",
    "  An array of 4 qubits in the $|0000\\rangle$ state.\n",
    "\n",
    "**Goal:**\n",
    "\n",
    "  Create the entangled state\n",
    "$|\\psi\\rangle = \\frac{1}{\\sqrt{2}} \\big( |+\\rangle_0 \\otimes |+\\rangle_2 + |-\\rangle_0 \\otimes |-\\rangle_2 \\big) \\otimes \\frac{1}{\\sqrt{2}} \\big( |+\\rangle_1 \\otimes |+\\rangle_3 + |-\\rangle_1 \\otimes |-\\rangle_3 \\big)$,\n",
    "where $|\\psi\\rangle_0$ and $|\\psi\\rangle_1$ are Alice's qubits and $|\\psi\\rangle_2$ and $|\\psi\\rangle_3$ are Bob's qubits.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Can you represent this state as a combination of Bell pairs?\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T21_CreateEntangledState \n",
    "\n",
    "operation CreateEntangledState (qs : Qubit[]) : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.2. Magic square observables\n",
    "\n",
    "**Input:**\n",
    "  A row and column indices corresponding to a cell in a magic square.\n",
    "\n",
    "**Output:**\n",
    "A tuple that represents the given cell of a magic square.\n",
    "The first element of the tuple is an `Int` denoting the sign of the observable (+1 for plus, -1 for minus),\n",
    "the second - an array of 2 observables of type `Pauli`.\n",
    "\n",
    "The square should satisfy the following properties:\n",
    "\n",
    "  1. The observables in each row and column mutually commute,\n",
    "  2. The product of observables in each row is $i$,\n",
    "  3. The product of observables in each column is $-i$.\n",
    "\n",
    "Note that different sources that describe Mermin-Peres game give different magic squares.\n",
    "We recommend you to pick one source and follow it throughout the rest of the tasks in this kata."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T22_GetMagicObservables \n",
    "\n",
    "function GetMagicObservables (rowIndex : Int, columnIndex : Int) : (Int, Pauli[]) {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.3. Apply magic square observables\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. A tuple representing an observable in a cell of a magic square, in the same format as in task 2.2.\n",
    "\n",
    "  2. An array of 2 qubits.\n",
    "\n",
    "**Goal:** \n",
    "  Apply the observable described by this tuple to the given array of qubits.\n",
    "\n",
    "For example, if the given tuple is `(-1, [PauliX, PauliY])`, you have to \n",
    "apply X to the first qubit, Y to the second qubit, and a global phase of -1 to the two-qubit state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T23_ApplyMagicObservables \n",
    "\n",
    "operation ApplyMagicObservables (observable : (Int, Pauli[]), qs : Qubit[]) : Unit is Adj+Ctl {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.4. Measure observables using joint measurement\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. A tuple representing an observable in a cell of a magic square, in the same format as in task 2.2.\n",
    "\n",
    "  2. A 2-qubit register to measure the observable on.\n",
    "\n",
    "The register is guaranteed to be in one of the eigenstates of the observable.\n",
    "\n",
    "**Output:** \n",
    "  The result of measuring the observable on the given register:\n",
    "Zero if eigenvalue +1 has been measured, One if eigenvalue -1 has been measured.\n",
    "\n",
    "The state of the qubits at the end of the operation does not matter.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Use <code>Measure</code> operation to perform a joint measurement.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T24_MeasureObservables \n",
    "\n",
    "operation MeasureObservable (observable : (Int, Pauli[]), target : Qubit[]) : Result {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.5. Measure an operator\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. An operator which acts on 2 qubits, has eigenvalues +1 and -1 and has a controlled variant.\n",
    "\n",
    "  2. A 2-qubit register to measure the operator on.\n",
    "\n",
    "The register is guaranteed to be in one of the eigenstates of the operator.\n",
    "\n",
    "**Output:** \n",
    "  The result of measuring the operator on the given register: \n",
    "  Zero if eigenvalue +1 has been measured, One if eigenvalue -1 has been measured.\n",
    "\n",
    "The state of the qubits at the end of the operation does not matter.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Applying the operator to an eigenstate will introduce a global phase equal to the eigenvalue. Is there a way to convert this global phase into a relative phase?\n",
    "</details>\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary>Need another hint? Click here</summary>\n",
    "  Remember that you can allocate extra qubits.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T25_MeasureOperator \n",
    "\n",
    "operation MeasureOperator (op : (Qubit[] => Unit is Ctl), target : Qubit[]) : Result {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.6. Alice and Bob's quantum strategy\n",
    "\n",
    "In this task you have to implement two functions, one for Alice's quantum strategy and one for Bob's.\n",
    "Note that they are covered by one test, so you have to implement both before attempting 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",
    "The best quantum strategy can win every time.\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  1. The index of Alice's row.\n",
    "\n",
    "  2. Alice's share of the entangled qubits, stored as an array of length 2.\n",
    "\n",
    "**Output:**\n",
    "\n",
    "  The signs Alice should place in her row (as an `Int` array of length 3).\n",
    "  +1 indicates plus sign, -1 - minus sign.\n",
    "  \n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "  Use <code>GetMagicObservables</code> from task 2.2.\n",
    "</details>\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary>Need another hint? Click here</summary>\n",
    "  You can use either <code>MeasureObservable</code> from task 2.4, or <code>ApplyMagicObservables</code> and <code>MeasureOperator</code> from tasks 2.3 and 2.5.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T26_QuantumStrategy \n",
    "\n",
    "operation AliceQuantum (rowIndex : Int, qs : Qubit[]) : Int[] {\n",
    "    // ...\n",
    "    fail \"Alice's strategy in task 2.6 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Inputs:**\n",
    "\n",
    "  1. The index of Bob's column.\n",
    "\n",
    "  2. Bob's share of the entangled qubits, stored as an array of length 2.\n",
    "\n",
    "**Output:**\n",
    "\n",
    "  The signs Bob should place in his column (as an `Int` array of length 3).\n",
    "  +1 indicates plus sign, -1 - minus sign."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T26_QuantumStrategy \n",
    "\n",
    "operation BobQuantum (columnIndex : Int, qs : Qubit[]) : Int[] {\n",
    "    // ...\n",
    "    fail \"Bob's strategy in task 2.6 not implemented yet\";\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 2.7. Play the magic square game using the quantum strategy\n",
    "\n",
    "**Inputs:**\n",
    "\n",
    "  Operations that return Alice and Bob's moves based on their quantum\n",
    "strategies and given their respective qubits from the entangled state.\n",
    "Alice and Bob have already been told their row and column indices.\n",
    "\n",
    "**Goal:** \n",
    "  Return Alice and Bob's moves.\n",
    "\n",
    "Note that this task uses strategies `AliceQuantum` and `BobQuantum`\n",
    "which you've implemented in task 2.6."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "multicell_solution"
    ]
   },
   "outputs": [],
   "source": [
    "%kata T27_PlayQuantumMagicSquare \n",
    "\n",
    "operation PlayQuantumMagicSquare (askAlice : (Qubit[] => Int[]), askBob : (Qubit[] => Int[])) : (Int[], Int[]) {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part III. Experimenting with the Magic Square"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task 3.1. Testing magic square strategies\n",
    "\n",
    "**Goal:**\n",
    "  Use your classical and quantum magic square strategies from tasks 1.3 and 2.6 to\n",
    "verify their probabilities of winning. Can you make the classical strategy lose?\n",
    "\n",
    "> This is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the `Run_MagicSquareGame` operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (`%simulate Run_MagicSquareGame`).\n",
    "\n",
    "> Note that this task relies on your implementations of the previous tasks. If you are getting the \"No variable with that name exists.\" error, you might have to execute previous code cells before retrying this task.\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need a hint? Click here</b></summary>\n",
    "    You will need to use partial application to use your quantum strategies from task\n",
    "2.6 with <code>PlayQuantumMagicSquare</code> from task 2.7.\n",
    "</details>\n",
    "<br/>\n",
    "<details>\n",
    "  <summary><b>Need another hint? Click here</b></summary>\n",
    "    Use <code>WinCondition</code> function from task 1.2 to check that Alice and Bob won the game.\n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "operation Run_MagicSquareGame () : Unit {\n",
    "    // ...\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%simulate Run_MagicSquareGame"
   ]
  }
 ],
 "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
}