challenge-2021.04-apr/challenge-2021.04-apr.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 06: The Mermin-Peres Magic Square\n",
    "\n",
    "For the 6th QOSF challenge, you will be playing a game. Well, not really. Alice and Bob will be playing a game and your job is to come up with classical _and_ quantum strategies to help them win as often as possible.\n",
    "\n",
    "What make this game interesting is that, as you will learn, there is no classical strategy that guarantees Alice and Bob can always win the game. The best possible rate of success using a classical approach is 88.89% (i.e., they can win only 8 out of every 9 games they play). However, by the use of a quantum strategy that uses entanglement as a resource, the game can be won every... single... time (100% success rate).\n",
    "\n",
    "### Description of the Game\n",
    "\n",
    "The game we'll be playing is a variant of the [Magic Square](https://en.wikipedia.org/wiki/Magic_square) puzzle, known as the [Mermin-Peres Magic Square](https://en.wikipedia.org/wiki/Quantum_pseudo-telepathy#The_Mermin%E2%80%93Peres_magic_square_game). Here are the rules of the game:\n",
    "\n",
    "**1.** We start with an empty 3 x 3 board. The cells in the board can be populated with either a one or a zero.\n",
    "\n",
    "\n",
    "**2.** Alice and Bob sit in separate rooms and are not allowed to use any classical means of communication to conspire.\n",
    "\n",
    "\n",
    "**3.** A referee, Richard, assigns a row to Alice and a column to Bob at random, which they have to populate.\n",
    "\n",
    "\n",
    "**4.** To win the game, Alice and Bob must meet the following requirements:\n",
    "\n",
    "       a. Alice should populate her row so that the binary sum (addition mod2) of her numbers is 0.  \n",
    "       b. Bob should populate his column so that the binary sum of his numbers is 1.  \n",
    "       c. Alice and Bob must place the same number in the cell where her row and his column intersect.  \n",
    "       \n",
    "**5.** Alice and Bob _are_ allowed to discuss and come up with a strategy _before_ the game starts.\n",
    "\n",
    "If you want more details regarding this specific formulation of the Mermin-Peres Magic Square, make sure to listen to the podcast episode provided in reference [A] below.\n",
    "\n",
    "### Game Examples\n",
    "\n",
    "Let's go over a few examples to build a better understanding.\n",
    "\n",
    "**Example 1: A losing example**\n",
    "\n",
    "- Richard randomly assigns row 2 to Alice, and column 3 to Bob\n",
    "- Alice populates her row with values 1, 0, 1.\n",
    "- Bob populates his column with values 1, 1, 0.\n",
    "\n",
    "Here's how the final board will look like:\n",
    "<img src=\"images/ex_01.png\" width = 450/>\n",
    "\n",
    "When checking the three conditions needed to win the game we see that:\n",
    "\n",
    "    a. Alice correctly populated her row because her numbers sum up to 0.  \n",
    "    b. Bob incorrectly populated his column because his numbers did NOT sum up to 1.  \n",
    "    c. Alice and Bob did place the same number in the cell where their row and column intersect: cell (2,3).\n",
    "    \n",
    "So, in this case, Alice and Bob have **lost** this round of the game... Bob should've known better.\n",
    "\n",
    "**Example 2: Another losing example**\n",
    "\n",
    "- Richard randomly assigns row 3 to Alice, and column 3 to Bob\n",
    "- Alice populates her row with values 0, 0, 0.\n",
    "- Bob populates his column with values 0, 0, 1.\n",
    "\n",
    "The final board now looks like this:\n",
    "<img src=\"images/ex_02.png\" width = 450/>\n",
    "\n",
    "Checking again the three conditions:\n",
    "\n",
    "    a. Alice correctly populated her row because her numbers sum up to 0.  \n",
    "    b. Bob correctly populated her row because her numbers sum up to 0 (good job Bob!).  \n",
    "    c. Alice and Bob did NOT place the same number in the cell where their row and column intersect: cell (3,3).\n",
    "    \n",
    "In this second example, Alice and Bob **lost** again because they picked different numbers for the cell where their row and column intersect.\n",
    "\n",
    "**Example 3: A winning example**\n",
    "\n",
    "- Richard randomly assigns row 1 to Alice, and column 2 to Bob\n",
    "- Alice populates her row with values 0, 1, 1.\n",
    "- Bob populates his column with values 1, 0, 0.\n",
    "\n",
    "Final board:\n",
    "<img src=\"images/ex_03.png\" width = 450/>\n",
    "\n",
    "Checking the conditions:\n",
    "\n",
    "    a. Alice correctly populated her row because her numbers sum up to 0.  \n",
    "    b. Bob correctly populated her row because her numbers sum up to 0 (good job Bob!).  \n",
    "    c. Alice and Bob did place the same number in the cell where their row and column intersect: cell (1,2).\n",
    "    \n",
    "At last, Alice and Bob have met all conditions and **won** a game.\n",
    "\n",
    "### The Challenge\n",
    "\n",
    "**Task 1**\n",
    "Write a program to emulate the game described above following these rules:\n",
    "\n",
    "- The rows and column that Richard assigns to Alice and Bob are always selected at random with equal probability.  \n",
    "- Alice and Bob select the numbers to populate their respective row and column at random with equal probability. \n",
    "\n",
    "Run the game several times and extract the probability of winning under each of these conditions.\n",
    "\n",
    "(Optional): Calculate the probability of winning under the given conditions to verify the results from your program.\n",
    "\n",
    "**Task 2**  \n",
    "Repeat task 1, but now:\n",
    "- Alice still picks her numbers to populate her row at random, but she improves her strategy by making sure she only selects numbers that will add up to 0.  \n",
    "- Bob still picks the numbers to populate his column at random, but he improves his strategy by making sure he only selects numbers that will add up to 1.  \n",
    "\n",
    "**Task 3**  \n",
    "Repeat task 1, but now you utilize a classical strategy to make sure that Alice and Bob very deliberately select how to populate their assigned row and column to maximize their chances of winning the game. Remember, Alice and Bob are not allowed to communicate after their row/column has been assigned.\n",
    "\n",
    "Hint: As mentioned in the challenge description, the best possible classical strategy can only guarantee that Alice and Bob win only 8 out of 9 games they play.\n",
    "\n",
    "**Task 4**  \n",
    "Now, to the quantum realm. Alice and Bob understand that one of the rules of the game is that they cannot communicate in any way once the game has started. However, they realize that if they can generate two pairs of entangled qubits, they can build shared correlations that will allow them to win the game every single time (see reference [B] and section 5 of reference [C] for examples of how this can be done). In this task, write a program that emulates the process of generating the two entangled pairs Alice and Bob share, and perform the right unitary operations in each of their qubits (depending on the row/column they are assigned) so that when they perform a measurement, they can generate the right string of ones and zeros to fill out their row/column to win each game.\n",
    "\n",
    "If you need more details on how multi-qubit and Pauli measurement operations work, make sure to check resource [D]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### References\n",
    "\n",
    "[A] [The origin of the Mermin-Peres magic square](https://nonlocal.libsyn.com/001-the-origin-of-the-mermin-peres-magic-square) (podcast)\n",
    "\n",
    "[B] [A Pseudo-Telepathy Game](http://electron6.phys.utk.edu/phys250/modules/module%203/a_pseudotelepathy_game.htm)\n",
    "\n",
    "[C] [Quantum Pseudo-Telepathy](https://arxiv.org/pdf/quant-ph/0407221.pdf)\n",
    "\n",
    "[D] [Single- and multi-qubit Pauli measurement operations](https://docs.microsoft.com/en-us/azure/quantum/concepts-pauli-measurements)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}