The GHZ Game quantum kata is a series of exercises designed to get you familiar with the GHZ game.
In it three players (Alice, Bob and Charlie) try to win the following game:
Each of them is given a bit (r, s and t respectively), and they have to return new bits (a, b and c respectively) so that r ∨ s ∨ t = a ⊕ b ⊕ c. The input bits will have zero or two bits set to true and three or one bits set to false. The trick is, the players can not communicate during the game.
∨ is the standard bitwise OR operator.
⊕ is the exclusive or, or XOR operator, so (P ⊕ Q) is true if exactly one of P and Q is true.
You can read more about the GHZ game in the lecture notes by John Watrous.
Another description can be found in the lecture notes by Michael Walter.
Each task is wrapped in one operation preceded by the description of the task.
Your goal is to fill in the blank (marked with the // ...
comments)
with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).
Inputs:
Alice, Bob and Charlie's input bits (r, s and t), stored as an array of length 3,
Alice, Bob and Charlie's output bits (a, b and c), stored as an array of length 3.
The input bits will have zero or two bits set to true.
Output: True if Alice, Bob and Charlie won the GHZ game, that is, if r ∨ s ∨ t = a ⊕ b ⊕ c, and false otherwise.
%kata T11_WinCondition
function WinCondition (rst : Bool[], abc : Bool[]) : Bool {
// ...
fail "Task 1.1 not implemented yet";
}
Can't come up with a solution? See the explained solution in the GHZ Game Workbook.
Input: The input bit for one of the players (r, s or t).
Output: A random bit that this player will output (a, b or c).
If all players use this strategy, they will win about 50% of the time.
%kata T12_RandomClassical
operation RandomClassicalStrategy (input : Bool) : Bool {
// ...
fail "Task 1.2 not implemented yet";
}
Can't come up with a solution? See the explained solution in the GHZ Game Workbook.
Input: The input bit for one of the players (r, s or t).
Output: A bit that this player will output (a, b or c) to maximize their chance of winning.
All players will use the same strategy. The best classical strategy should win about 75% of the time.
%kata T13_BestClassical
operation BestClassicalStrategy (input : Bool) : Bool {
// ...
fail "Task 1.3 not implemented yet";
}
Can't come up with a solution? See the explained solution in the GHZ Game Workbook.
Inputs:
An operation which implements a classical strategy (i.e., takes an input bit and produces an output bit),
An array of 3 input bits that should be passed to the players.
Output: An array of 3 bits that will be produced if each player uses this strategy.
%kata T14_PlayClassicalGHZ
operation PlayClassicalGHZ (strategy : (Bool => Bool), inputs : Bool[]) : Bool[] {
// ...
fail "Task 1.4 not implemented yet";
}
Can't come up with a solution? See the explained solution in the GHZ Game Workbook.
In the quantum version of the game, the players still can not communicate during the game, but they are allowed to share qubits from an entangled triple before the start of the game.
Input: An array of three qubits in the $|000\rangle$ state.
Goal: Create the entangled state $|\Phi\rangle = \frac{1}{2} \big(|000\rangle - |011\rangle - |101\rangle - |110\rangle \big)$ on these qubits.
%kata T21_CreateEntangledTriple
operation CreateEntangledTriple (qs : Qubit[]) : Unit {
// ...
fail "Task 2.1 not implemented yet";
}
Can't come up with a solution? See the explained solution in the GHZ Game Workbook.
Inputs:
The input bit for one of the players (r, s or t),
That player's qubit of the entangled triple shared between the players.
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.
The state of the qubit after the operation does not matter.
%kata T22_QuantumStrategy
operation QuantumStrategy (input : Bool, qubit : Qubit) : Bool {
// ...
fail "Task 2.2 not implemented yet";
}
Can't come up with a solution? See the explained solution in the GHZ Game Workbook.
Input: Operations that return Alice, Bob and Charlie's output bits (a, b and c) based on their quantum strategies and given their respective qubits from the entangled triple. The players have already been told what their starting bits (r, s and t) are.
Goal: Return an array of players' output bits (a, b and c).
%kata T23_PlayQuantumGHZ
operation PlayQuantumGHZ (strategies : (Qubit => Bool)[]) : Bool[] {
// ...
fail "Task 2.3 not implemented yet";
}
Can't come up with a solution? See the explained solution in the GHZ Game Workbook.