Unfortunately, the paper “Quantum Coloring Games via Symmetric SAT Games” by Imai, Le Gall, Fukawa that I refer to above, can only be found in the conference proceedings of AQIS 11.

]]>(The AI underlying the blog moderation appears to be running on an Atari 2600 these days)

If we’re to believe that the refs in http://arxiv.org/abs/1212.1724 (Graph Homomorphisms for Quantum Players) are up to date (it just appeared today), then (a) the object in question is called the quantum chromatic number of a graph (the minimum c such that there exists a perfect quantum strategy, i.e., winning every time despite the lack of a classical c-coloring), and (b) currently there are no known graphs with c=3.

If this interpretation is correct, this small part of the talk may need to be modified next time around.

]]>Yes, the Magic Square and Pentagram games are described in Mermin’s ’93 article http://link.aps.org/doi/10.1103/RevModPhys.65.803 , but the 3-color case still requires more thought. It is conceivable that Arkhipov the author of http://arxiv.org/abs/1209.3819 would already know the answer (though the problem is slightly different from his generalization of Mermin-Peres).

]]>For other similar examples, see the Mermin Magic Square Game and Pentagram Game.

]]>In other words, how does Arthur know that the boxes can only be decrypted one way and Merlin isn’t just picking a decryption key based on Arthur’s question? Do you need some kind of signature scheme to keep Merlin honest (in addition to encryption)? Or does your encryption scheme make it hard to fake the true contents of a message?

[I don't think the question changes much if Merlin is only allowed to send back one key for all |V| Hamiltonian edge boxes. Maybe that just means he needs each box to have 2^|V| hidden compartments, rather than 2].

]]>OK I have looked. In 3.2 they discuss convincing a ref that an odd cycle of length n is 2-colorable, using a single Bell pair. The optimal strategy is correct with probability cos^2(pi/4n): better than the classical 1-1/2n, but not a perfect quantum strategy. (So now it’s not clear if your two Merlin’s were just beating the classical odds, or always successful.)

In 4.1, they discuss the graph coloring proof system, with k colors, where there is a perfect quantum strategy for a class of graphs G_n, but the smallest number of colors for which one of these is uncolorable (and hence would require the quantum strategy) is k=n=16, so inapplicable to the k=3 case.

So still slightly unclear as to whether there’s a perfect quantum strategy for two Merlins purporting to 3-color, or just one that beats the classical odds (i.e., does better than 1-1/(V+E) ), and in either case how may qubits are used.

(Sorry if this takes your talk too literally)

]]>I even suspect this can be done with 2logN qubits, such that each vertex is associated to applying a specific binary pattern of Hadamards before measurement, again such that same and neighboring patterns measure same and different.

But do you happen to know the minimum number of qubits necessary for this case of cheating, specifically whether constant or how it scales with N? ]]>