This paper defines and characterizes a new form of quantum multi-prover interactive proof system. The authors consider a quantum verifier who can interact with multiple unentangled quantum provers. The twist is that the provers are allowed to exchange unlimited amounts of classical communication. Even so, the authors show that such a proof system can still recognize languages in NEXP. This is a wonderful result: the model is novel, the outcome is surprising, and there are some nice ideas used to devise the protocol.

The result probably also has implications for quantum information processing. There are a number of situations where one would like to find the optimal protocol for some task using LOCC (local operations with classical communication), e.g., LOCC state discrimination, entanglement distillation. The sentiment in the community is that these problems are difficult, and the result in this paper is a first indication as to why. I'm not aware of earlier work about the classical complexity of finding an optimal LOCC protocol.

The main idea is start with classical 2-prover proof system for NEXP and to modify it so that the verifier asks the questions from the classical proof system in superposition with fake questions, the answers of which he doesn't actually care about. To gain classical information about what the questions are, a prover would have to decohere the superposition, and the verifer can detect this.

This paper is worth reading just to see the bound Eq. (2) on the number of solutions to the quantum marginal problem. The calculation is just a few lines and very clean.

I need to read this more fully, but if this is correct it might be very useful in understanding the quantum-classical boundary.

concave lens + surface corrugations = convex lens

As far as I can tell, the authors make an assumption that the channel acts as a beamsplitter. In particular, the transmission probability of an n-photon pulse is given by $\eta_n = 1 - (1-\eta)^n$, where $\eta$ is the transmission probability of a single photon.

The whole point of decoy states is to be able to counter attacks such as photon-number-splitting, where an adversary may block single photon pulses and split off a photon from multi-photon pulses, which are let through otherwise undisturbed, in order to gain partial or full information on the sifted bits. If we assume that an eavesdropper has no such control over the quantum channel, then certainly decoy states are no longer needed to achieve security, but this is neither a good assumption against a sophisticated adversary nor is the analysis in such a case new.

interesting ... but where's the mathematical analysis?

a valiant attempt... but let down by an odd def of the Lorentz transform (see eq. (2.3,2.4)) and various other mistakes
(e.g eq. (3.7,3.8) isn't a rotation)

Might prove useful for studying mixed quantum states in gravitational fields.

Is this the first actual simulation of Rob's model (or generalized version of said model) or has someone put his model to the test before?

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.

An important step in fully understanding entropy & the second law in relation to quantum theory. The paper could stand to be cleaned up a bit, though.

Is this guy really proposing that nucleons are not made up of quarks??

Oh no! Another paper propagating the silly idea that you can measure entanglement by assuming you create two identical pure states. Do people realize that the assumption of pure states is rather large? For instance, any pure state (except those in a set of measure zero) is entangled.

Also, one motivation for the measurement, that witnesses do not give a quantitative estimate of entanglement is incorrect, as several papers have shown.

Not as nuts as its title suggests. Really a historical/philosophical review paper.

Um, what exactly does it mean to be "outside spacetime?" And what's the difference between immaterial and material free will, for that matter?

A nice result. But let me hypothesize that you could recast the problem and find you still only match the Carnot limit -- because N correlated 2 level atoms acts like fewer than N such; e.g. starting with a naive calculation of number of degrees of freedom (i.e. N) artificially reduces the Carnot efficiency as compared to a calculation using the "true" number (M

More of a review article, but very interesting nonetheless in light of recent work on entanglement in gravitational fields by Preskill, Fuentes-Schuller, Adesso, Alsing, etc., etc.

An instant classic

An instant classic

Hahaha! OK, good point on the "recommend" function. As for citing things non-QI related, I do, but I can't speak for everyone. Personally, I'm more of a foundations sort of guy so my tastes run in that direction (hence, I am frequently the only one who cites some of the more 'bizarre' papers).

Voting for your own paper is sensible -- after all, how else is the "recommend" function supposed to match you up with your core interests?

... and while we're off topic -- can all you QI enthusiasts occasionally look at/ scite some papers not in your own specific field? Surely your interests are not that narrow?

OK, so how gauche is it to vote for your own paper?

I was just wondering what had become of the Afshar experiment and here I see it is alive and well in modified form...

I suspect the reason this works is that a number of seemingly disparate problems including these and a few others (see my recent paper quant-ph/0801.0403, for instance) are really just manifestations of a generalized probability theory. I actually suspect much of this will prove useful to artifical intelligence at some point.

But squeezing generation requires power, and there may other (simpler) ways of using that power: see e.g. quant-ph/0110118

Two papers on the same day with the same title? This and 0802.4248.

I liked the power law distributions from fragmentation/coalescence processes; not so sure about the ant/human stuff though.

This simplifies and strengthens the state-randomization result of quant-ph/0307104 (and quant-ph/0307100).

The original idea is that if you act on any pure state with a bunch of random unitaries you get a state where all its eigenvalues are within epsilon/d of 1/d. This is proved by taking an epsilon-net over all pure states and showing with the union bound that w.h.p. this holds for all states in the epsilon net.

The original paper actually took an epsilon/d net, figuring that when you move out of the net by delta, the largest eigenvalue could increase by as much as delta. The new paper shows than an epsilon-net is sufficient. This is done with a sort of bootstrapping argument. It's simple mathematically, but hard to concisely explain in words. If I were to try, I'd say that if the map is known to be weakly randomizing everywhere, then moving out of the net by delta won't hurt you by as much as delta. This in turn improves our estimates of how well the map randomizes, and we can iterate this to get a much better bound.

DMRG and other MPS methods work very well in practice to find ground states of 1d problems, but in some practical cases can get stuck in false minima. This is a separate question from the question of whether the desired ground state does indeed have a matrix product state representation. The question is whether one can find the MPS. Recently Eisert presented evidence that the problem of finding the best MPS can be NP-hard. Eisert varied over certain matrices while leaving other matrices fixed and showed that this problem was NP-hard. Thus, Eisert's result left open the question of whether finding the ground states of 1d Hamiltonians with MPS ground states of polynomial bond dimension really is a hard problem or not. The present paper answers this question.

Now *this* looks cool. As a teacher, I would still want students to know how to do this kind of thing by hand, but for quick results when doing research or just thinking about things, this looks very useful (though, admittedly, I have not tried any of them yet).

An example of a quantum proof of a classical computer science problem which, at least if you know quantum computing, is much simpler. (Of course your mileage will vary according to your comfort with quantum computation.)

Cool use of Linear Trajectories. Easy to read as well.

I finally got a chance to read this paper which has been sitting on my desk since it was published. This is a very cute result about Kitaev's toric code (and a host of related models.) Basically the authors show how the ground state of Kitaev's toric code can be thought of as a MERA state. What this means in practice is that they show a series of unitary transformations followed by a discarding of qubits such that the toric code stabilizer on a lattice is mapped to a toric code stabilizer on a lattice with double the lattice constant. I'm still trying to wrap my head around uses for this, but I'm sure there are some out there.

Inching closer to an understanding just what it means for a quantum object to be "distinguishable" from another - one of the great unsolved foundational problems... :)

Not sure what I make of this. I studied this problem in depth from a historical standpoint while working on my PhD and I'm not sure he correctly characterizes the relation of exclusion to the Dirac sea.

Amendment: He actually makes two distinct claims and one hinges on what one considers a true derivation (i.e. in the logic chain, where do the foundational axioms need to be). In any case, I still say that his claim to be the first to do this is incorrect. On the other hand, it is possible he has found an alternate "derivation." [See pp. 236-280 in Max Jammer's Conceptual Development of Quantum Mechanics (1966).]

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.

This paper points out difficulties with the Ohmic spin-boson model in the case of pure dephasing. This is an important result, especially given the popularity and widespread of this model.

This is pretty neat. It's curious to see what differences there are between software for quantum and classical computers. I'm sure there have been plenty of papers on this topic. I just don't happen to be that familiar with that area of study.

This a message I've sent to the ArXiv moderator about this paper:

Dear arXiv-moderation,

This concerns the authorship of http://arxiv.org/abs/0712.3934 , "A critical analysis of the GP-B mission. I: on the impossibility of a reliable measurement of the gravitomagnetic precession of the GP-B gyroscopes." This paper may represent an anonymous attack.

The author's name is given as "Gerhard Forst," with the email address g.forst@yahoo.com . He has no prior ArXiv papers, and seems to have no peer-reviewed publications. His affiliation and address are given as:

G. Forst
FGP
Behrenstr. 1
10117 Berlin

Whatever FGP stands for, there is no mention on the web of such an organization at the given address. Was this paper endorsed? If so, can the endorser show "Gerhard Forst" is the author's real name?

There is an interesting similarity to papers by another author, who has a history of tit-for-tat disputes on ArXiv:

"On the impossibility of measuring a galvano-gravitomagnetic effect with current carrying semiconductors in a space-based experiment," http://arxiv.org/abs/gr-qc/0308053

"On the impossibility of using the longitude of the ascending node of GP-B for measuring the Lense-Thirring effect," http://arxiv.org/abs/gr-qc/0404107

"On the impossibility of using certain existing spacecraft for the measurement of the Lense-Thirring effect in the terrestrial gravitational field," http://arxiv.org/abs/gr-qc/0508012

"On the impossibility of measuring the general relativistic part of the terrestrial acceleration of gravity with superconducting gravimeters, http://arxiv.org/abs/gr-qc/0602005

"On some critical issues of the LAGEOS/LAGEOS II Lense-Thirring experiment," http://arxiv.org/abs/0710.1022

In addition to the titles, there are many other similarities. Comparing the most recent of these to the paper in question, there are these sequences:

"...no other tests performed by independent teams, without connections with Ciufolini and coworkers...have been so far reported in literature."

"...no independent team, without connections with the GP-B team, will be able to repeat the GP-B data analysis..."

In the former there are 4 sentences beginning with the word "Indeed." Such a sentence is also found in the latter. I could list further examples.

That author has himself claimed increasingly accurate measurements of the Lense-Thirring effect, which I've discussed here:

http://arxiv.org/abs/astro-ph/0701653

Both those claimed measurements and his reputation would be seriously threatened by a contrary result from Gravity Probe B. I hope the reasons are clear from my paper.

Best regards,

Kris Krogh

The original GHZ paper. It's interesting that the abstract says "deterministic" local model. I would say that Bell's theorem rules out all probabilistic or stochastic local models.

Not sure why, but SciRate truncated his last name. It's Omnès.

I think this is going to be my winter break reading material. It is an interesting idea but I'm curious about the exact details.

Can anyone comment on this paper?!

Looks interesting, though the sense in which he uses the word emergence might need to be studied a tad.

I'd compare/ contrast it to arXiv:0711.2315, if I had the time.

Fig.2: The evolution of nose size as a function of time.

The following Work is very spectacular !!!

I am particularly excited about this new proposed architecture for quantum simulations, because it could be well-suited for cluster state quantum computing and may offer gate fidelities better than 99%, where fault tolerance can be achieved.