Summary:
The authors describe a scheme where Alice can make quantum queries to a database Bob. If Bob tries to cheat to learn what Alice queried, then she catches him with constant probability.

Let D_j be the jth entry in the database. Fix entry 0 of the database to be D_0 = 0. To query j > 0, Alice sends |j> and |0>+|j> in random order to Bob. She waits for Bob's response before she sends the second one. Bob is supposed to respond respectively with |j, D_j> or |0,0> + |j,D_j>. Alice can clearly get D_j. Intuitively, Bob can't learn j because he doesn't know whether he is seeing |j> or |0>+|j>. If he measures the latter, then he will collapse the superposition, which Alice can detect.

They don't actually give a security proof in any detail, but say that a full proof will be forthcoming.

Summary:
They start by describing the concept of coherent state exchange. State exchange means m parties converting |psi> to |phi> using only local operations without communication. (Note that the ability to create |psi> and |phi> each from |0^m> implies the ability to go between |psi> and |phi>.) Coherent state exchange means that the conversion can be done coherently, i.e., as
 (alpha |0^m> + beta |1^m>)|0^m> -> alpha |0^m>|0^m> + beta |1^m>|psi> .
First they give a catalytic way of doing this approximately using assisted entanglement. Assume that <psi|phi> = 0. Then start with
 |E_N> \propto sum_{k=0}^{N-1} |phi>^k |psi>^{N-k}
Then a cyclic shift transforms |phi>|E_N> to |psi>|E_N'> with <E_N'|E_N> = 1-1/N. (This is trivial to check, since we may take phi=0 and psi=1 so |E_N> = 1/{sqrt N} sum_{k=0}^{N-1}|0^k>|1^{N-k}> and |E_N'> = 1/{sqrt N} sum_{k=1}^N |0^k>|1^{N-k}>.) The case of <psi|phi> != 0 can be dealt with by going to a third state that is orthogonal to them both (or see the appendix). A "universal embezzling state" can be built out of epsilon-nets to cover everything closely. This is rather hugely inefficient compared to the bipartite construction of van Dam and Hayden, and a good question is if it can be improved.

Next they give an example of a two-party game for which no finite amount of shared entanglement allows achieving the optimal strategy. The referee R hands the two provers P,Q pieces of the state
 |0>R |00>PQ + |1>R (|11>+|22>)PQ .
The provers initially share entanglement, and their goal is to return the state
 |0>R |00>PQ + |1>R |11>PQ .
(This is coherent state exchange between |11> and |11>+|22>.) The provers can succeed with probability arbitrarily close to 1 by using better and better embezzlers. However, there is a simple proof that they can't win with certainty with any finite-dimensional shared state. (The key claim is that if ||A||<=1, then A can be written as a convex combination of unitaries, which is immediate from the singular-value decomposition of A. Then they rewrite the acceptance probability in terms of operators with norms <=1. Convexity bounds the success probability by what we have with unitaries. But unitaries can't give equality since there are different amounts of entanglement on the two sides.) They also use some arguments similar to [DH03] to upper-bound the winning probability as a function of the dimension d of the shared state; I haven't read this, but the answer is
 <=1-1/log^2(d) .

Finally, they talk about QMIP a bit more. They say that Kempe, Kobayashi, Matsumoto & Vidick's procedure for transforming a QMIP protocol to have completeness exactly one is complicated (it transforms an m-turn protocol into a 3*(m+2) turn protocol, two turns to make completeness exactly 1/2, then a factor of 3 for Watrous rewinding) and that there is a simpler procedure that allows getting the completeness arbitrarily close to one similarly to the two-party transformation of Kitaev and Watrous (m+2 turns). The idea is very intuitive.
- Assume that the completeness parameter is exactly achieved for every x and that it is known to the verifier.
- At the end of the interaction, write the total state as
 sqrt{1-p} |0> |psi_0> + sqrt{p} |1> |psi_1> ,
where the first qubit is the verifier's acceptance bit, and then there is everything else. We may assume <psi_0|psi_1> = 0 (e.g., the verifier can duplicate his acceptance bit). Now add one more round to the protocol. The verifier sends his workspace to the provers in some arbitrary way and they use some more entanglement to embezzle |psi_1> to |psi_0> arbitrarily well. Therefore, the verifier is left with
 (sqrt{1-p} |0> + sqrt{p} |1>) tensor |psi_0>
The verifier then just checks that p=c (by measuring with respect to sqrt{1-c} |0> + sqrt{c} |1>. It is easy to see that soundness is maintained because then there is a gap from p to c.

This paper gives protocol transformations for the class QMIP of quantum multi-prover interactive proofs. Ultimately, it shows that QMIP(k prover, m round, 1/poly completeness-soundness gap) lies in QMIP(poly provers, 1 round, completeness 1, soundness 2^{-poly}).

QMIP is the quantum generalization of MIP, which equals NEXP and PCP(poly, poly). QMIP allows for quantum messages and provers that share an unlimited amount of entanglement. (Note that some papers call this class QMIP*.) It is known that MIP = QMIP(with unentangled provers), and also that QMIP(with provers sharing poly entanglement only) lies in MIP [Kobayashi, Matsumoto, cs.CC/0102013]. However, the power of QMIP, in which provers are allowed to share an arbitrary prior entangled state, is not known. In fact, relatively little is known about QMIP. For example, unlike in the classical case, it is not known whether using more than two provers is advantageous or not---classically not, MIP(poly players, poly rounds) = MIP(2 players, 1 round) = NEXP. A major motivation for studying QMIP is to develop some quantum version of the classically important PCP theorem, but this has not yet come to pass (although see [Raz, quant-ph/0504075]).

Allowing the provers to share entanglement lets them cheat in protocols designed for unentangled provers, as in the well-known CHSH game. By reducing the protocol soundness, this would seem to reduce the power of the proof system. There have been several papers on putting limits on how much the provers can cheat, and on redesigning protocols to "immunize" them against shared entanglement. For example, the authors of this paper and Toner have shown that NEXP lies in MIP*(c=1,s=1-2^{-poly})(3 prover,1 round) [quant-ph/0704.2903], which has also been shown by Ito, Kobayashi, Preda, Sun & Yao [quant-ph/0712.2163]. (MIP* means a classical protocol in which the provers can share unlimited entanglement.)

Instead of trying to protect against entanglement, this paper takes a different tack, and tries to design protocols that take advantage of the honest provers' shared entanglement. It shows that any QMIP protocol can be
1. Made perfectly complete (using the Watrous rewinding reflection trick).
2. Parallelized to three turns, with soundness error 1-1/poly (by Marriott/Watrous forward/backward trick repeatedly).
3. Made public coin, with the verifier sending the same bit to all provers (using the same M/W trick).
4. Converted to just two turns by adding a prover, again with soundness error 1-1/poly.
Note that the first two transformations can be made classically as well. However, the public coin transformation cannot be made classically, since then one might as well have only a single prover (i.e., MIP(public coin) = IP). That it works quantumly comes from the monogamy of entanglement.

The proofs are short and clear. For making the protocol perfectly complete, the verifier first essentially flips a weighted coin in order to make the completeness exactly 1/2. Then the Watrous reflection trick applies to ensure that the completeness is 1. To show soundness, the difficulty is that the dishonest provers may not rewind as they are supposed to. To catch this kind of cheating, the verifier flips a coin to decide whether he tests for acceptance or tests that the provers have inverted their first action.

To parallelize the protocol to three turns, the authors apply the Marriott/Watrous forward/backward trick that was used to show QMAM = QIP [cs.CC/0506068]. (See [Kobayashi, quant-ph/0705.1129] for another application of this trick.) Recall the Kitaev/Watrous trick originally used to show QIP = QIP(three rounds) [STOC 2000]: roughly, the prover sends the snapshot states for all messages of the original protocol and the verifier challenges him to show consistency between a random adjacent pair, using a swap test. This trick does not work with multiple provers because the transformation between the prover workspaces of the snapshots may have to be coordinated across several parties. In the M/W trick, on the other hand, the provers instead send a snapshot for the protocol halfway through, and the verifier flips a coin to decide whether to go forward or backward. If forward, then the verifier will check for acceptance, and if backward, then he will check that the final state is properly initialized to zeros. This transformation reduces the number of rounds by half, and can be applied repeatedly. Soundness follows intuitively because if the provers can convince the verifier both forward and backward in the transformed protocol, then they could have gone all the way forward in the original protocol; the proof uses the "triangle inequality" for fidelities. Note that this transformed protocol requires entanglement, because the snapshot state is entangled across all the provers. (Note too that the snapshot state depends on the input x, so an exponential amount of entanglement may be required, a different state for each possible input.)
The proof of the public coin transformation is almost the same, and is very close to the M/W proof that QMAM = QIP.

Finally, the authors transform the k-prover, three-turn protocol to just two turns (i.e., one round) by adding a (k+1)st prover. The new prover sends the verifier the first messages of the k provers in the original protocol. The verifier sends his coin flip only to the first k provers, who should respond with their second messages in the original protocol. Completeness and soundness of the transformed protocol are both immediate. Again, this transformed protocol generically requires entanglement between the honest provers.
In particular, applying this transformation with k=1 implies that QIP lies in QMIP(2 prover, 2 turn, completeness 1, soundness 2^{-poly}), by [Marriott/Watrous 05].

Putting the results together, the authors have shown QMIP(k prover, m turn, 1/poly completeness/soundness gap) lies in QMIP(poly provers, 2 turn, completeness 1, soundness 2^{-poly}), by using multiple provers for parallelization amplification.

Although most of the tricks used in the protocol transformations are not novel, their application to studying QMIP is. Also, the proofs are extremely simple.