The Magic Square Game quantum kata is a series of exercises designed to get you familiar with the Mermin-Peres magic square game.
In it two players (Alice and Bob) try to win the game in which they have to fill one row and one column of a 3x3 table with plus and minus signs.
Alice is given an index of a row and has to fill that row so that it has an even number of minus signs. Bob is given an index of a column and has to fill that column so that it has an odd number of minus signs. The sign in the cell that belongs to the intersection of Alice's row and Bob's column has to match in both Alice's and Bob's answers. The trick is, the players can not communicate during the game.
Each task is wrapped in one operation preceded by the description of the task.
Your goal is to fill in the blanks (marked with the // ...
comments)
with some Q# code that solves the task. To verify your answer, run the cell with Ctrl+Enter (⌘+Enter on macOS).
Within each section, tasks are given in approximate order of increasing difficulty; harder ones are marked with asterisks.
In this task you have to implement function for validating Alice's move.
Input:
The signs Alice chose for each cell in her row,
represented as an Int
array of length 3.
Output:
true
if Alice's move is valid (every cell is either +1 or -1 and
the array has an even number of minus signs), and false
otherwise.
%kata T111_ValidAliceMove
function ValidAliceMove (cells : Int[]) : Bool {
// ...
fail "Validating Alice's move in task 1.1.1 not implemented yet";
}
In this task you have to implement function for validating Bob's move.
Input:
The signs Bob chose for each cell in his column,
represented as an Int
array of length 3.
Output:
true
if Bob's move is valid (every cell is either +1 or -1 and
the array has an odd number of minus signs), and false
otherwise.
%kata T112_ValidBobMove
function ValidBobMove (cells : Int[]) : Bool {
// ...
fail "Validating Bob's move in task 1.1.2 not implemented yet";
}
Inputs:
The row and column indices Alice and Bob were assigned. Each index will be between 0 and 2, inclusive.
Alice and Bob's moves, represented as Int
arrays of length 3.
Output:
true
if Alice and Bob won the game (that is, if both their moves are valid and
they chose the same sign in the cell on the intersection of Alice's row and Bob's column),
and false
otherwise.
%kata T12_WinCondition
function WinCondition (rowIndex : Int, columnIndex : Int, row : Int[], column : Int[]) : Bool {
// ...
}
In this task you have to implement two functions, one for Alice's classical strategy and one for Bob's. 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.
The classical strategy should win about 89% of the time.
Input: The index of Alice's row.
Output:
The signs Alice should place in her row (as an Int
array of length 3).
+1 indicates plus sign, -1 - minus sign.
%kata T13_ClassicalStrategy
function AliceClassical (rowIndex : Int) : Int[] {
// ...
fail "Alice's strategy in task 1.3 not implemented yet";
}
Input: The index of Bob's column.
Output:
The signs Bob should place in his column (as an Int
array of length 3).
+1 indicates plus sign, -1 - minus sign.
%kata T13_ClassicalStrategy
function BobClassical (columnIndex : Int) : Int[] {
// ...
fail "Bob's strategy in task 1.3 not implemented yet";
}
In the quantum version of the game, the players still can not communicate during the game, but they are allowed to share qubits from two entangled pairs before the start of the game.
Input: An array of 4 qubits in the $|0000\rangle$ state.
Goal:
Create the entangled state $|\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)$, where $|\psi\rangle_0$ and $|\psi\rangle_1$ are Alice's qubits and $|\psi\rangle_2$ and $|\psi\rangle_3$ are Bob's qubits.
%kata T21_CreateEntangledState
operation CreateEntangledState (qs : Qubit[]) : Unit {
// ...
}
Input: A row and column indices corresponding to a cell in a magic square.
Output:
A tuple that represents the given cell of a magic square.
The first element of the tuple is an Int
denoting the sign of the observable (+1 for plus, -1 for minus),
the second - an array of 2 observables of type Pauli
.
The square should satisfy the following properties:
Note that different sources that describe Mermin-Peres game give different magic squares. We recommend you to pick one source and follow it throughout the rest of the tasks in this kata.
%kata T22_GetMagicObservables
function GetMagicObservables (rowIndex : Int, columnIndex : Int) : (Int, Pauli[]) {
// ...
}
Inputs:
A tuple representing an observable in a cell of a magic square, in the same format as in task 2.2.
An array of 2 qubits.
Goal: Apply the observable described by this tuple to the given array of qubits.
For example, if the given tuple is (-1, [PauliX, PauliY])
, you have to
apply X to the first qubit, Y to the second qubit, and a global phase of -1 to the two-qubit state.
%kata T23_ApplyMagicObservables
operation ApplyMagicObservables (observable : (Int, Pauli[]), qs : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Inputs:
A tuple representing an observable in a cell of a magic square, in the same format as in task 2.2.
A 2-qubit register to measure the observable on.
The register is guaranteed to be in one of the eigenstates of the observable.
Output: The result of measuring the observable on the given register: Zero if eigenvalue +1 has been measured, One if eigenvalue -1 has been measured.
The state of the qubits at the end of the operation does not matter.
Measure
operation to perform a joint measurement.
%kata T24_MeasureObservables
operation MeasureObservable (observable : (Int, Pauli[]), target : Qubit[]) : Result {
// ...
}
Inputs:
An operator which acts on 2 qubits, has eigenvalues +1 and -1 and has a controlled variant.
A 2-qubit register to measure the operator on.
The register is guaranteed to be in one of the eigenstates of the operator.
Output: The result of measuring the operator on the given register: Zero if eigenvalue +1 has been measured, One if eigenvalue -1 has been measured.
The state of the qubits at the end of the operation does not matter.
%kata T25_MeasureOperator
operation MeasureOperator (op : (Qubit[] => Unit is Ctl), target : Qubit[]) : Result {
// ...
}
In this task you have to implement two functions, one for Alice's quantum strategy and one for Bob's. 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.
The best quantum strategy can win every time.
Inputs:
The index of Alice's row.
Alice's share of the entangled qubits, stored as an array of length 2.
Output:
The signs Alice should place in her row (as an Int
array of length 3).
+1 indicates plus sign, -1 - minus sign.
GetMagicObservables
from task 2.2.
MeasureObservable
from task 2.4, or ApplyMagicObservables
and MeasureOperator
from tasks 2.3 and 2.5.
%kata T26_QuantumStrategy
operation AliceQuantum (rowIndex : Int, qs : Qubit[]) : Int[] {
// ...
fail "Alice's strategy in task 2.6 not implemented yet";
}
Inputs:
The index of Bob's column.
Bob's share of the entangled qubits, stored as an array of length 2.
Output:
The signs Bob should place in his column (as an Int
array of length 3).
+1 indicates plus sign, -1 - minus sign.
%kata T26_QuantumStrategy
operation BobQuantum (columnIndex : Int, qs : Qubit[]) : Int[] {
// ...
fail "Bob's strategy in task 2.6 not implemented yet";
}
Inputs:
Operations that return Alice and Bob's moves based on their quantum strategies and given their respective qubits from the entangled state. Alice and Bob have already been told their row and column indices.
Goal: Return Alice and Bob's moves.
Note that this task uses strategies AliceQuantum
and BobQuantum
which you've implemented in task 2.6.
%kata T27_PlayQuantumMagicSquare
operation PlayQuantumMagicSquare (askAlice : (Qubit[] => Int[]), askBob : (Qubit[] => Int[])) : (Int[], Int[]) {
// ...
}
Goal: Use your classical and quantum magic square strategies from tasks 1.3 and 2.6 to verify their probabilities of winning. Can you make the classical strategy lose?
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
).
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.
PlayQuantumMagicSquare
from task 2.7.
WinCondition
function from task 1.2 to check that Alice and Bob won the game.
operation Run_MagicSquareGame () : Unit {
// ...
}
%simulate Run_MagicSquareGame