Migrate Nonlocal Games katas to quantum.microsoft.com

[tcNickolas]

Current CHSH game, GHZ game, and Mermin-Peres magic square game katas cannot be used with the modern QDK. It would be nice to have them available as part of the new katas experience.

I think each of them is too small to warrant a separate kata in the new experience, so it would make sense to merge them together into one kata called "Nonlocal Games: CHSH, GHZ, and Mermin-Peres".

We'll probably want to explain each quantum strategy ahead of the exercises that implement it, same as we did in QEC Shor kata, since it's tricky to come up with independently (especially for the magic square!)

• [x] CHSH game: Keep task 1.1, merge two cells in task 1.2 in one task by defining an operation that returns a tuple of two operations, one for Alice and one for Bob, drop 2.1 and 2.3, keep 2.2 and 2.4-2.5 (possibly make 2.5 a demo), keep the discussion of quantum strategy and its win probability.
• [ ] GHZ game: Keep task 1.1, merge 1.2 and 1.3 in a more open-ended task that evaluates success probability of a classical strategy, keep 1.4 and 2.1-2.3 (possibly make 2.3 a demo), keep the discussion of quantum strategy and its win probability.
• [ ] Mermin-Peres: Merge 1.1.1 and 1.1.2 into one task with Boolean flag isAlice, keep 1.2 and 1.3 (merge two cells in 1.3 in one task returning a tuple), keep 2.1, drop 2.2 (it will be verified in 2.3 automatically), keep 2.3-2.7.

[ggridin]

I'd like to work on these issues

Here are a few clarifying questions: What do you think is a good section structure for nonlocal games? Should I move quantum demos and discussions to separate sections?

Suggestion for sections (total 10, maybe 13):

1. Overview (to be written? This section will contain the idea of nonlocal games + the topic summary + prerequisite knowledge)
2. CHSH game (overview moved from CHSH overview
3. Classical CHSH (Tasks 1.1, 1.2 The content is from the above link, readme, and workbook)
4. Quantum CHSH (Tasks 2.2, 2.4, 2.5(demo and Discussion: probability of victory for quantum strategy ) )
5. GHZ game (overview moved from GHZ overview )
6. Classical GHZ (Tasks 1.1, 1.2/3, 1.4)
7. Quantum GHZ (Tasks 2.1, 2.2, 2.3 + discussion + demo)
8. Magic Square Game (overview moved from Magic Square overview)
9. Classical Magic Square Game (Tasks 1.1, 1.2, 1.3)
10. Quantum Magic Square Game (Tasks 2.1, 2.3, 2.4, 2.5, 2.6, 2.7 + demo + experiments)

[tcNickolas]

This breakdown sounds about right, yes. The limitation we have for the infrastructure is that each exercise is its own section, and after an exercise you must have a new section immediately, you can't have any follow-up text. So whenever you have exercises and then a demo/discussion, you'll need to create a section to hold these, titled something like "Quantum CHSH End to End". You can have a discussion immediately after a demo without a new section, though, since demos don't define their own sections

You'll probably want to start with adding just the first game to the kata in one PR, and then send two more PRs with the other games. This way the scope of each review would be smaller and I'll be able to do it faster :-)

[ggridin]

@tcNickolas Maria - thank you for information. Question for CHSH game, Task 1.2: Does it make sense "...one task by defining an operation that returns a tuple" ? Alice and Bob must not communicate during the game, but single operation that return a tuple allows a "peeking". Two separate functions, like below, support isolation:

namespace Kata { function AliceClassical (x : Bool) : Bool { // Implement your solution here... return false; } function BobClassical (y : Bool) : Bool { // Implement your solution here... return true; } }

I think, it make sense to merge 2 cells into 1 exercise but ask student to implement both of functions.

[tcNickolas]

If the operation returns a tuple of functions, how would you implement peeking from one of them into the other? They still cannot share a state, since Q# doesn't have global variables, and sharing some function code wouldn't help.

My idea is to still have two separate functions for Alice and Bob, yes, but use the wrapper that returns both these functions, similar to task Entanglement Swapping in Teleportation kata. The learner then implements both functions indeed, but they live in one exercise.

[ggridin]

@tcNickolas - thank you for clarification. I confused 2 values tuple with 2 functions tuple. Where do you think, the good place for nonlocal games in katas list? I consider to put them between marking oracles and deutsch algorithms.

[tcNickolas]

I'd put it either after Superdense Coding and before Oracles or after all the oracular algorithms before QEC. Oracles and oracular algorithms are one unit logically, so I wouldn't break them up. These games don't rely on the concept of an oracle, so they can go before, together with the "simple algorithms". On the other hand, they're an optional topic (I don't cover them in my course, for example) so they can be closer to the end.

[ggridin]

@tcNickolas I am ready to submit PR for quantum CHSH but it depends on https://github.com/microsoft/qsharp/pull/1710 (particularly: nonlocal_games/index.md) Could you review?

[tcNickolas]

I reviewed now! Thank you for your patience, I needed to wrap up some urgent work on other katas, and the heat this week was not helpful. Heads up, I'll be traveling throughout next week, so will get back to reviews on July 22nd.

[ggridin]

@tcNickolas As far as understand, historically, GHZ game kata is based on Michael Walter and John Watrous lectures. As entangled triple, they are using $\frac{1}{2} \big(|000\rangle - |011\rangle - |101\rangle - |110\rangle \big)$ rather than commonly used $\frac{1}{\sqrt{2}} \big(|000\rangle + |111\rangle \big)$. As mentioned in external lectures, these states are identical up to local unitary operations.

However, the difference might cause learners confusion. I think there are 2 ways to resolve the problem:

1. Keep the current approach
   • add notes and the proof (because we are removing external links...) that entangled triples are identical.
   • as optional task, ask students to implement GHZ game using $\frac{1}{\sqrt{2}} \big(|000\rangle + |111\rangle \big)$ entangled state.
2. Move to traditional GHZ state implementation. Here are 2 ways to proceed:
   • Implement approach 1 and create enhancement issue to use commonly used GHZ state
   • Switch to new implementation right now. Quantum code implementation is quite easy. Section "Discussion" will need a rework.

What do you think?

[tcNickolas]

Good question!!

I like that in this variant of the game the measurements are done in Z and X bases, since they are quite commonly used in other katas, unlike the measurement in Y basis that Wikipedia suggests for the game with GHZ state. I also like that the solution for this variant is already written up :-) I would lean towards the first option you suggested, keep the current approach and add a note that this game is equivalent to the game with GHZ state itself, and mention the strategy for that state, but we probably don't need to write up the proof of these two games being equivalent, just mention that if the learner is curious they can do it as an exercise.