A very impressive proof of a long-standing open problem.

It is a review of mainly specific topic. I tried to cite only valuable papers, which are not mistakble. Those, presented ideas only and not confirmed by serious arguments are omitted.

I only just discovered this paper while working on some research. I think the results it presents are immensely profound, particularly from a foundational standpoint, but also from a practical standpoint. Pretty impressive stuff, in my opinion.

QUOTE: "From the point of view of entropic dynamics the problem is not to explain the arrow of time, but rather to explain the reversibility of the laws of physics."

Much better than that barely intelligible Categories paper a few days ago!

So how does this work then? Is the information carried by entanglement between the two (individually) zero-capacity channels?

They missed a key point since they never discussed the operator-based uncertainty relations (i.e. the ones Schrödinger derived) which are a purely classical statement about the behavior of operators. It would seem to have relevance for what they are attempting to do.

I love papers like this.

A delightfully simple observation that shakes quantum Shannon theory to its foundations! Great paper.

I have now updated my paper. It now contains an explanation of this object of a conditional probability with respect to a sigma algebra, which Nelson introduced here.

I made a similar explanation as is given by Faris in

"Probability in quantum mechanics," appendix to David Wick, The Infamous Boundary: Seven Decades of Controversy in Quantum Physics , Birkhauser, Boston, 1995.


It is somewhat simple, since it uses coin tossing experiments to define the notations. Maybe such things can be understood by mathematicians, too....

If someone thinks that this is not rigorous enough, or even have some suggestions to write it in a better way, I would be too pleased.

But thank you for your comments quantumcurious.

Dear Quantumcourious, thank you for your corrections of P(X_t \in A')=P(Y_t\in A')

But to your point:

But the set {\cup \omega: \omega \in \bar \mathcal F} would be just be \Omega, again strange.

It would be \Omega. In fact, trivial!
But exactly this is ment in section 2. Why do you not allow me to make trivial examples? Is there anything against trivial statements?

And well, in fact: A \cap \bar \mathcal F = A is ment in the introduction. This is trivial too. In fact.

The third sigma algebra F_x is introduced later in section 4. Then, it is certainly not trivial anymore.But since we deal only with rather trivial probability spaces, where the possible events are only {up} and {down}, I do not think of anything which would prevent equations 33 and 34 to be correct or made the statements at the end of section 4 impossible.

Unfortunately, I have, at my hands, only the references cited by Nelson. His most rigorous threatmenton this is a conference paper cited in my article:

Field theory and the future of stochastic mechanics, pp. 438–469 in Stochastic Processes
in Classical and Quantum Systems (Proceedings, Ascona, Switzerland, 1985), ed. by S.
Albeverio, G. Casati, and D. Merlini, Lecture Notes in Physics 262, Springer-Verlag, Berlin,
1986. [See correction in 45.]



and the contribution of Faris cited in the paper. You might read them yourself. Unfortunately, they are somewhat "short" and do not explain things in full, since they were intended for professional mathematicians.


If you contact me per e-mail, I can send you copies. I would be glad to get more rigour in my paper.


The proof, where you seem to make your arguments against it (the proof in section 4), is from W. Faris in an Appendix of a book. Faris was a student of Nelson and is now Professor at Arizona.
http://math.arizona.edu/~faris/publications.html

"Probability in quantum mechanics," appendix to David Wick, The Infamous Boundary: Seven Decades of Controversy in Quantum Physics , Birkhauser, Boston, 1995.

You can see his proof partly at google books:
http://books.google.de/books?id=FxypunelyRwC&dq=d+wick+infamous+boundary&pg=PP1&ots=AfXTACaBfH&sig=m4OQjZCOLMMuXFmIPBskB8oY2w8&hl=de&sa=X&oi=book_result&resnum=1&ct=result#PPA216,M1

(unfortunately, the page, where the conditional probability with respect to a sigma algebra is defined, cannot be seen through google books. But Faris refers to Nelsons proof and it seems to be the same definition which Nelson had in mind,

I can see no error in both works.

You are probably a mathematician. I'm only a physicist. Of course, I have heard the usual lectures in stochastic processes, but well, If you would help me to get more riguour in this, I would appreciate it.


By the way, thank you for your comments

It seems that this preprint has now been replaced twice since the first version (the July 27th one seems to have disappeared off the arXiv). However, the issues I raised before are still there and, moreover, now a "correction" has been made to a perfectly correct statement in the original turning it to something incorrect in the later versions. It reinforces my suspicion that the author may not have a good understanding of measure-theoretic probability.

I don't see why it would be hard to see while P(A \cap B) makes perfect sense since A and B are both subsets of \Omega and elements of \bar \mathcal{F}, P(A \cap \bar\mathcal{F}) (which can be found in Section 2 of the paper) cannot be treated in the same way. How do you define the intersection of a set with a sigma algebra?? Perhaps A \cap \bar \mathcal F = A? But this is a trivial definition and useless.

In the same vein, P(A) makes perfect sense for any A in \bar \mathcal{F}, but how would you define P(\bar \mathcal F) (as written in Section 2)??
It seems to me that the author is suggesting that this is defined as P({\cup \omega: \omega \in \bar \mathcal F}} but the set {\cup \omega: \omega \in \bar \mathcal F} would be just be \Omega, again strange.

Appeals to authority and a book does not make things right. Although the notation P(A|\bar \mathcal F) is used in Nelson's paper, I hardly think the definition he has in mind is the same as the definition invented in this paper by the author. Also, I can't comment on the Amazon.de book as I don't have access to it. But, if it is true what the author claims, then there must be something more to it than what the author thinks.

For any A \in \bar \mathcal{F}, I would expect P(A|\bar \mathcal{G}), where \bar \mathcal{G} is a sub-sigma algebra of \bar \mathcal{F} to be defined to be something like:

P(A|\bar \mathcal{G})=E(1_A |\bar \mathcal G) P-almost surely,

where 1_A is the indicator function of A and E[\cdot |\bar \mathcal F] is the conditional expectation onto \bar \mathcal F, along with a regularity condition:

For almost every \omega \in \Omega, P(\cdot|\omega) defines a probability measure on \bar \mathcal F,

assuming that such a regular conditional probability exists (not always the case, but do in most cases of practical interest).

Also, the statement "That is for any event A' ∈ \bar \mathcal F' we have: P {X_t ∈ A'} = P {Y_t ∈ A'}" which is correct to begin with in the original version has now been replaced with the incorrect statement "That is for any event A ∈ \Omega we have: P {X_t ∈ A } = P {Y_t ∈ A}" in the later versions.

If the basic definitions are not consistent, what expectation can the reader have that the rest of the paper isn't just gobbledygook? I don't know, although the math may be shaky the resulting physics may still be consistent. Perhaps someone else who can persevere through the whole paper may comment on that aspect...

I have now updated the paper. Now it should be clear what mathematicians think when they write a conditional probability with respect to a sigma algebra.

In fact, this is common notation in lectures about stochastic processes and any mathematician should understand it. I must say, that this is not my own notation, but the one of the well respected probabilist Edward Nelson from Princeton!

Well, I now have looked again in some standard Textbooks of probability theory. For example:
http://www.amazon.de/Wahrscheinlichkeitstheorie-Gruyter-Lehrb%C3%BCcher-Heinz-Bauer/dp/3110172364

He uses at pp. 365 and at 367 a similar notation. Here, a random variable X = P(A|forall W \in \bar\mathcal{F}) with a sigma algebra \bar\mathcal{F} is defined in exactly the same way.

It seems not, that I must learn more about probability theory. But the commenter above....

Well, As the author of the paper above:

I just used the notation of Edward Nelson http://www.math.princeton.edu/~nelson/ himself from his paper in: http://www3.interscience.wiley.com/journal/119493682/abstract?CRETRY=1&SRETRY=0

Also, I sent Edward Nelson my paper. He wrote, that it would be "quite interesting".

Of course, one can write the above definitions with more rigour. This is no problem. For example, you can write, that, what Nelson defines as X = P(A|\bar\mathcal{F})

defines really with all events W in \bar\mathcal{F}

X = P(A|forall W \in \bar\mathcal{F})

clearly, in Nelson's notation X means this.

But of course this would not change the physical content. It would only make all formulas more lengthy.

You might ask Prof Nelson himself, why he thought this notation would be usefull.

This paper looks to be a very interesting read from the abstract, unfortunately this turns out not to be the case as one begins to go through it. The problem is that although the author states (p.2): "Since Nelson’s analysis of Bell’s theorem might have been overlooked by physicists because of its use of advanced probability theory, the article begins with a review of the necessary mathematical background", the first few pages suggests that the author himself may not have an adequate grasp of "advanced probability theory" (or, rather, measure-theoretic probability theory). This can be quite off-putting to scientists who do have a solid background in measure-theoretic probability theory and may prevent them from taking this paper seriously.

Some samples of conceptual misunderstandings in this paper are as follows:
- P.3, section 2: The author claims that X = P(A|\bar\mathcal{F}) is a random variable, but how exactly is this random variable defined? The discussion that follows this definition seems to suggest that the author is defining P(A | \bar\mathcal{F}) = P(A \cap \bar \mathcal{F})/P(\bar \mathcal(F)), but this hardly makes sense since \bar\mathcal{F} is a sigma-algebra while probabilities are assigned to elements of \bar\mathcal{F} (which are all subsets of \Omega), not to the sigma algebra \bar\mathcal{F} itself. Thus the term P(A|\bar\mathcal{F}) and the statement P(\bar\mathcal{F}) = 1 would all just be nonsense the way it is defined here.
- P.3, section 2: The author states "... if A \in G and P(A \cap G| \bar \mathcal{F}) = 0 for events A \notin G". How can A be in or not in G?? A is a subset of \Omega and so is G (since A and G are both elements of the sigma algebra \bar \mathcal{F}). G contains elements of \Omega, not subsets of \Omega such as A.
- P.3, section 2: The author states that (X_t)_{t \in I} \in \bar \mathcal{F}', but the stochastic process (X_t) does not take on values in the sigma algebra \mathcal{F}', but on the underlying sample space \Omega'.
- P.7, section 4: In line with first dashed point above, equations (32)-(34) make no sense.

Throughout the parts of the paper I read I get the impression the author is confusing events (elements of a sigma algebra) and random variables. I stopped reading after page 7 as I at that point I had already developed a deep distrust of the paper.

This paper has been revised since the abstract appeared on SciRate. Version 2 has the amended title, "The Computational Status of Physics: A Computable Formulation of Quantum Theory", and the paper now contains several pages of additional contextual material; the introductory section has also been substantially rewritten.

Version 2 of the paper:
* explains more clearly why you'd want to reformulate quantum mechanics as a formally computational theory in the first place;
* illustrates how the reformulation is related to (but different from) work in Digital Physics;
* reviews several (known) examples of idealised physical systems that are arguably hypercomputational. Perhaps surprisingly, these include a couple of examples from Newtonian physics, as well as quantum and relativistic exemplars;
* ends with some open questions, one of which suggests that the paper's reformulation may well provide an automatic and natural link between quantum theory and gravity.

I'm not entirely sure that's true (that positive-P is necessarily excluded), though I'd have to ask Rob to be sure. I was under the impression he was explicitly talking about P- and Q-functions, but I could be wrong.

This states "It follows that a nonnegative quasiprobability representation of quantum theory is also impossible." -- presumably explicitly positive quasiprobability distributions like the positive-P are excluded from this statement somehow. Can anyone clarify?

Wonder how this compares cost-wise with traditional photon detectors/counters. I'm presently in the market for cheap ones.

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).