So, that last paper ballooned way out of control. There was just so much information, and it was explained in a way that even I could understand it! Thank goodness for good paper writers :) But for this post, let’s try to tackle a short (and in my opinion hilarious) paper.
So, let’s start with the title. Quantum strategies. Alright, you got my attention – what kind of strategies can you have with quantum mechanics exactly? I swear, if this is just another quantum communication trick disguised in a game show again…
The introduction is intriguing enough – Meyer briefly goes over the history of quantum information, with discussion of quantum algorithms, QKD, and other entanglement-based communications. He then launches into a comparison between quantum algorithms and game trees found in game theory. Already, I’m getting a bit suspicious – how exactly is this game played?
Thankfully, Meyer fully explains the specific strategy that he is considering, by going to none else but Captain Picard on the Spaceship Enterprise. The premise is that there are two actors in a game to begin with, Picard (P) and Q. A single fair coin is placed heads-up within a box, and if the coin is heads-up by the end of the game, Q wins. There are three turns, where at each turn, the actor can decide to either flip or not flip the coin, without knowing the previous state of the coin. The turns will begin with Q, then P, then Q.
A simple examination of the game seems to show that this is a zero-sum game with no pure equilibrium strategy for P. The only Nash equilibrium strategy is a random chance, 50/50 mixed strategy for Picard. In my mind’s eye, I can picture Picard first flipping a coin to decide if he should flip the real coin! And of course, for Q, the Nash Equilibrium strategy is to choose each of the four options (NN, NF, FN, FF) with 25% probability. However, the expected value for each of the actors should be 0, so for a large number of games, the end result of the coin should be heads or tails with 50% probability.
And that’s when things start to go off the rails. In a series of 10 games, Q wins every single one of them. How? By implementing a *quantum strategy* for the coin. Meyer begins explaining the game in terms of quantum transformations, where a flip (F) is equivalent to a NOT gate, while a no flip (N) is equivalent to an identity game. Furthermore, a classical mixed strategy is represented by a matrix as well, where the diagonals are identical. From here, Meyer extrapolates to being able to apply any series of quantum gates on the poor coin!
What is then explained is essentially a way to cheat the system. Q first prepares the qubit in a Bell state, and then acts the Bell state again after P’s turn. At this point, I smack my head. Of course, Meyer is just treating Picard as an Oracle, and implementing a quantum algorithm onto the state of the qubit! There isn’t any “strategy” happening here – it’s simply using Simon’s algorithm to deduce and reverse Picard’s actions. At least Meyer is a good storyteller…
There are so many objections I have. For one, how could you do this in practice, ever? A coin is not a quantum object – what kind of special hands do you need to have to flip it so that your coin ends up in a Bell state? And afterwards, how is Picard acting on the object without disturbing it? Yes, I understand that if both of them were doing the same experiment on a qubit, say an NMR spin, then it would be feasible. But that’s an entirely different situation than what game theory deals with! You aren’t analyzing situations that can come up in decision making, you’re literally analyzing a quantum game and trying to solve it using quantum algorithms and transformations.
But Meyer does continue in the paper. He states three theorems, and they are as follows:
All quantum algorithms do as well as mixed Nash equilibriums. The proof of this seems obvious – as a quantum gate can always be written in matrix form as a classical probability matrix, you can always use a quantum algorithm to do at least the same thing as a mixed equilibrium.
There does not always exist a pure quantum Nash equilibrium. Meyer shows this in a very similar way to Nash’s original problem. He uses the unitary nature of each of the quantum transforms to show that there exists no single strategy that cannot be improved by switching strategies. I’m actually not sure what he means here by pure quantum strategy – does that mean that he implemented a pure strategy using quantum gates? What’s the difference between that and a regular pure strategy?
There always exists a mixed quantum Nash equlibrium. For this, Meyer doesn’t even show a proof – he just asserts that it is the same as Neumann’s and Nash’s result on classical mixed strategies, on the basis of the Hilbert space that quantum transformations exist in.
All in all, Meyer is a wonderful writer who can really tell a strategy using Picard. Surely not so many people would fall for his thinly veiled Simon’s algorithm, right? Oh, 628 citations you say? Wow.