Well, my grades are all turned in, and so I’ve pretty much officially finished teaching my first class. On the final, I had an extra credit problem which was basically the GHZ problem. It was very interesting to see the different ways in which the students would come up with a contradiction for the impossibility of winning the GHZ game. My favorite was the student who wrote a spreadsheet for every single possible strategy and showed that none of those would win. This is such a computer science way to solve the problem: I love it! The students all did remarkably well on the final and I was very happy with their final scores (they may be more or less happy.) One of the students didn’t miss a point the entire term!
This week I’m preparing my lectures for a summer school in Italy. Again it will be a course for graduate students in computer science. Pretty soon Dirac notation will be standard in computer science departments 😉 Here is my favorite quote about Dirac notation:
Mathematicians tend to despise Dirac notation, because it can prevent them from making important distinctions, but physicists love it, because they are always forgetting such distinctions exist and the notation liberates them from having to remember.–David Mermin
I made the spreadsheet. Why do math when there are only 2^6 possible strategies?
What’s the GHZ problem ?
GHZ problem:
Three players, Alice, Bob, and Charlie. They are locked away and not allowed to talk to each other. A warden comes around and gives them a slip of paper with either an X or a Y on it. The warden guarantees that either all of the slips are X or two out of three are Y with the last slip X. After the slips are distributed, the players are supposed to shout out either +1 or -1. They can’t hear each other when they do this. The players win if the (1) they were all given X and the product of what they shout is +1 or (2) two of the three were given Y and the product of what they shout is -1.
The GHZ problem is to design a strategy so the players can always win (i.e. assume they know they are going to play this game so they can chat, exchange random bitstrings, etc, before they are locked away and not allowed to communicate.
Classically it is impossible for them to always win this game. But if the parties share a three party entangled state, the so-called GHZ state, then they can make measurements on this state such that they win this game. The measurements don’t allow them to communicate, but are correlated in a strange way such that they can beat this game (this is known as pseudo-telepathy.)
You can see the problem I gave them here:
http://www.cs.washington.edu/education/courses/csep590/05su/final.pdf
I should have given you guys the four party GHZ problem with one bit of communication. But I’m afraid I then would have had huge reams of paper with tables on them 😉
BTW, I once got fed up with a problem in the General Relativity class I was taking. So I printed out all 256 components of the Riemman tensor.
and that helped how?
The Riemman tensor? It didn’t help (unlike jeffdav who got the problem correct) but it was kind of funny seeing as how, you know there are only 20 independent components. I’m sure the TA for the class didn’t find it ammusing.
Thanks. That’s an interesting problem. I have to argue with the characterization of brute force solutions as a “CS solution” :), but I won’t argue very hard 🙂
Suresh: well I would call it a “CS solution” but not a “CS theory solution” 😉 Maybe I should have called it a programmers solution?
on behalf of the legions of offended CS theory folks everywhere, I accept your correction 😉
sheesh. I am getting ornery in my old age…