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)

Adding quantum seems to make many kinds of proof more powerful than they would be otherwise: for example, it’s conjectured that QMA strictly contains MA (where MA = Merlin-Arthur), and that QSZK strictly contains SZK (where SZK = Statistical Zero Knowledge). (Though on the other hand, we now know that QIP=IP=PSPACE, meaning that quantum does not increase the power of poly(n)-round interactive proofs!) On the other hand, quantum is not a panacea whose addition makes a given proof notion “leapfrog” over every other proof notion that could ever be defined: to give one example, no one knows whether QSZK contains classical MA, and they might well be incomparable.

In other words: as far as complexity theory knows or cares, quantumness is basically “just another interesting resource to add to the mix,” similar to nondeterminism, multiple provers, etc. Of course, the fact that the actual physical universe seems to provide quantumness makes that resource extremely special! But then we’re talking physics, not complexity theory.

(Incidentally, I think your comment stopped making sense at “interactive depends on what observables one is allowed to measure.” I don’t know how to define interactive proofs by talking only about “measuring observables,” without making reference to a hypothetical entity that implements a strategy with the goal of maximizing the verifier’s acceptance probability.)