So Loïck wants me (Fred Grosshans) to live-blog this morning session. Any mistake are therefore mine and not his ! This morning is mainly about trying to get beyond quantum mechanics and/or understanding why quantum mechanics is the way it is. In other words, why is so difficult to get PR-boxes.

Information causality

Marcin Pawłowski arXiv:0905.2292

Marcin speaks about those people that are so angry not to get a PR-box. I think you can count me among them ! To understand why the world makes us so unhappy, he introduce a new principle (information causality), which has been a “small step for mankind, but a big step for his PhD thesis”. He has a good explanation what principles should be, in decreasing order of importance :

As far as I understood, information causality is a quantitative statement saying there is no more information in a message than the sender initially put into it. It is now well known that prefect PR-boxes (with CHSH=4) make any distributed computation task trivial. in other words, with a single bit of classical communication and shared nonlocal randomness (from perfect PR-boxes), Alice and Bob could compute any distributed function f(x,y), where x and y are bit-strings. A single bit could get information from many bits. Information causality, if it is true, prevents this by saying that m bits can only carry m bits of information.

Information causality is true in every theory allowing to introduce a reasonable mutual information, i.e. one which obeys the following axioms:

Furthermore, it allows them to recover Tsirelson/Cirel’son/Цирельсон ’s bound (CHSH≤2√2) with only information theoretic axioms and no (direct) reference to quantum mechanics!




Local quantum measurement and relativity imply quantum correlations



Salman Beigi, Sergio Boixo, Matthew Elliot, and Stephanie Wehner
arXiv:0910.3952




Here, the question is whether a theory can be locally quantum and violate the Tsirelson bound. After some math involving POVM, the naswer is no. In other words, if you manage to violate the Tsirelson's inequality in a Bell-like set-up, you have also proven that quantum mechanics is wrong locally.




According to Antonio Acín in rump session, this result do not extend to 3-party.




All reversible dynamics in maximally non-local theories are trivial



David Gross, Markus Mueller, Roger Colbeck, and Oscar Dahlsten
arXiv:0910.1840 , accepted yesterday in PRL.




This talk brings us to (N,M,K)-boxworld. In Boxworld, states are described by nonlocal hidden variables, where N parties can choose between M measurement devices which give K outcomes. Standard PR-boxes exist in (2,2,2)-boxworld. The question is basically what kind of reversible computing is possible in boxworld. The symmetry of boxworld, where the equivalent of Bloch's sphere are pointy polytopes strongly reduce the number of possible reversible transformations to basically trivial transformations.




In particular, you cannot reversibly create PR-box from product states, even if the theory allows for their existence.






Measurements incompatible in quantum theory cannot be measured jointly  in any other no-signaling theory



Michael M. Wolf, David Perez-Garcia, and Carlos Fernandez




The title says everything I was able to catch from Michael's talk. Except that some dual semi-definite programs where involved during the proof.




Laying the quantum and classical embedding problems



Toby Cubitt, Jens Eisert, and Michael Wolf




The problem here is basically finding a master equation compatible with a CP-map description of a channel. The classical version of this problem (finding a Markov equation explaning a stochastic transformation) is as old as the Hindenburg disaster (1937) and had not been solved.




Using Linblad generators, matrix logarithms, 1-in-3SAT problem, integer semi-definite programming, Toby shows that the quantum and the classical problems are NP-hard. Solving the problem is equivalent to solving P=NP. But there is a (known) algorithm which is efficient for fixed dimension.




It somehow means that physics extraction from experimental data is NP-complete !




Quantum interactive proofs with short messages



Salman Beigi, Peter W. Shor, and John Watrous




Since QIP=IP=PSPACE, quantum proofs seem to bring no advantages over classical proofs and QIP = QIP(3). This talk is about the power of QIP(1) = QMA,  QIP(2), QIP[log,poly]…




Theorem: QIP[log,poly] = QMA.

Theorem: QIP_log = BQP

Theorem: QAM[poly,log] = BQP




Open problem: what is the power of QIP[poly,log]