Quantum correlations and generalized probabilistic theories:
an introduction

MVSpec (Advanced Lecture on Special Topics, 4 Credit Points).
Every Wednesday (Mittwoch), 14.15 - 15.45, Philosophenweg 12, kleiner Hörsaal.

To get the credit points, you have to solve a little research / literature search question. The list of questions is at the bottom of this page, and will grow from lecture to lecture. As a group of two people, you pick one of the questions (those that are already assigned have names next to it). Until the end of the semester, you should answer the question clearly and in some detail (this may involve reading scientific papers from the field, and coming to my office with questions), and write the answer up as a LaTeX PDF document (something between 5 and 12 pages). The document should be written such that it can be read and understood by everybody who visited the course. It will be uploaded to the course homepage.

Contact: Markus Müller

As shown theoretically by John Bell, and confirmed in numerous experiments, quantum theory admits correlations that are impossible classically, in the sense that they violate a Bell inequality. Much later, Tsirelson as well as Popescu and Rohrlich demonstrated a fact which seems surprising at first sight: there are conceivable correlations - now called "PR-boxes" -- which violate Bell inequalities even stronger than any quantum state, while still respecting the "no-signalling principle" necessary to comply with relativity. This has initiated a research program, aiming at bounding the set of quantum correlations in terms of simple physical principles.

From a more general perspective, quantum information theory has demonstrated that quantum theory is only a special case of a large class of "generalized probabilistic theories" (GPTs), with different physical predictions such as superstrong nonlocality or higher-order interference. This is comparable to the earlier insight that Lorentz transformations are just a special case of a large class of "theories of geometry". This lecture gives an introduction to GPTs and some classical results from the last few years by the quantum information community. Possible applications range from device-independent cryptography to the design of experimental tests of quantum theory, approaches to quantum gravity, and simple operational explanations for "why" we have the strange formalism of quantum mechanics with its complex numbers, operators, and Hilbert spaces.

This is a great overview article on the general research direction: S. Popescu, Nonlocality beyond quantum mechanics, Nature Physics 10, 264-270 (2014).

Furthermore, Asher Peres has written a great book (Quantum Theory: Concepts and Methods, Kluwer 2002) covering many of the topics of this lecture (and actually much more interesting stuff). Google for it!

More good books - have a look:
* K. Kraus, States, Effects, and Operations, Lecture Notes in Physics, Springer Verlag, 1983.
* A. S. Holevo, Probabilistic and Statistical Aspects of Quantum Theory, North-Holland, 1982.

Finally, Rob Spekkens is regularly giving a great course on quantum foundations at Perimeter Institute. You can watch the videos online! Some of the lectures cover some material in much more depth than I can do here - see, for example, Lecture 8, which contains a great presentation that PR-box correlations cannot be simulated classically (in contrast to "Bertlmann's socks"-type correlations). Rob's lectures have a more philosophical flavor, and also much more conceptual clarity than what I can offer in my lecture (I'm instead putting more emphasis on recent mathematical results in this field).


List of lectures, and additional links

1. Overview and perspective on the course; the CHSH Bell inequality. (16.04.2014, download PDF)
What is research on "quantum foundations" all about? Bell scenarios; classical, quantum, and non-signalling behaviors.

Here are some papers for further reading. Boris Tsirelson was the first to consider general behaviors; for example
* L. A. Khalfin, B. S. Tsirelson, Quantum and quasi-classical analogs of Bell inequalities, Symposium on the Foundations of Modern Physics (ed. Lahti et al.; World Sci. Publ.), 441-460 (1985).
* B. Tsirelson, Quantum Bell-type inequalities, Hadronic Journal Supplement 8, 329-345 (1993).

Oh, and this is Bertlmann (sorry for the wrong spelling in the lecture notes): :-)
Wikipedia: Reinhold Bertlmann

2. No-signalling, PR-boxes, convex geometry, Bell's Theorem. (23.04.2014, download PDF)
The "Popescu-Rohrlich box" correlations appear already in Tsirelson's work, but were rediscovered in this paper
* S. Popescu and D. Rohrlich, Quantum Nonlocality as an Axiom, Found. Phys. 24(3), 379-385 (1993)
which opened up a whole new field of research.

Here is a standard references (book) on convex geometry:
* R. Webster, Convexity, Oxford University Press (1994).
We will need convex geometry again later on, when we talk about generalized probabilistic theories.

Here is another paper where the no-signalling conditions appear; it will become important later:
* J. Barrett, Information processing in generalized probabilistic theories, Phys. Rev. A 75, 032304 (2007).

An application of no-signalling (and the general ideas and framework) is device-independent cryptography. I will probably not have enough time in the lecture to discuss this, but here is a reference for everybody who's interested:
* J. Barrett, L. Hardy, and A. Kent, No Signalling and Quantum Key Distribution, Phys. Rev. Lett. 95, 010503 (2005).


3. Implausible consequences of superstrong nonlocality: collapse of communication complexity. (7.5.2014, download PDF)
The result is from this paper (which appeared on the arxiv in 2005, but was published only 8 years later):
* W. van Dam, Implausible consequences of superstrong nonlocality, Natural Computing 12(1), 9-12 (2013).
Brassard and coauthors have generalized this to the case where the PR-boxes are not perfect, and the Bell-CHSH violation is not 4, but 3.3 (still larger than the quantum bound of 2.82):
* G. Brassard, H. Buhrman, N. Linden, A. A. Méthot, A. Tapp, and F. Unger, Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial, Phys. Rev. Lett. 96, 250401 (2006).

"The" standard book on communication complexity is this one:
* E. Kushilevitz and N. Nisan, Communication Complexity, Cambridge University Press (2008).
See also this little document:
* E. Kushilevitz, Communication Complexity.

The claimed bound on the quantum communication complexity of the inner-product function is in the following paper:
* R. Cleve, W. van Dam, M. Nielsen, and A. Tapp, Quantum Entanglement and the Communication Complexity of the Inner Product Function, Lect. Notes Comput. Sci. 1509, 61-74 (1998).


4. No-signalling and nonlocality imply irreducible randomness in physics. (14.5.2014, download PDF)
The main idea is old, and specific formulations of it have come up many times in many different forms. The short introduction is inspired by this talk by Toni Acín:
* A. Acin, Randomness and quantum non-locality (talk at QCRYPT 2012, Singapore).

A very strong recent result, saying that random predictions of quantum theory cannot be improved (under assumptions similar to those mentioned in the lecture) is this one:
* R. Colbeck and R. Renner, No extension of quantum theory can have improved predictive power, Nature Communications 2, 411 (2011).
There is lots of material on device-independent cryptography; see for example the paper above by Barrett, Hardy and Kent. The specific result proven in the lecture (that there cannot be hidden non-signalling states improving the predictions of measurements on a maximally entangled state) is a special case of the result in this paper:
* S. Pironio, Randomness vs. non-locality in a no-signalling world, Journal of Physics: Conference Series 67, 012017 (2007).


5. Principles bounding the set of quantum correlations. Example: macroscopic locality. (21.5.2014, download PDF)
Here is the paper introducing macroscopic locality:
* M. Navascues and H. Wunderlich, A glance beyond the quantum model, Proc. R. Soc. A 466 (2010).

The definition of the set of "almost quantum correlations" (which agrees with Q^(1+AB) for correlations on two parties only) is here. It's not too difficult, have a look (this paper is only 2 months old!):
* M. Navascués, Y. Guryanova, M. J. Hoban, and A. Acín, Almost quantum correlations, arXiv:1403.4621.

The relation to quantum gravity (in more detail, for "histories" approaches and its decoherence functionals) is shown here:
* F. Dowker, J. Henson, and P. Wallden, A histories perspective on characterising quantum non-locality, arXiv:1311.6287.


6. Further example of possible beyond-quantum physics: higher-order interference. (28.5.2014, download PDF)
Sorkin's measure-theoretic definition can be found in this paper:
* R. D. Sorkin, Quantum mechanics as quantum measure theory, Mod. Phys. Lett. A 9, 3119-3128 (1994).
An experimental test of absence of higher-order interference is described in the following publication. It's not that difficult; check it out!
* U. Sinha, C. Couteau, T. Jennewein, R. Laflamme, and G. Weihs, Ruling Out Multi-Order Interference in Quantum Mechanics, Science 329, 418 (2010).
See also this popular-scientific article. As you can see, absence of third-order interference is usually sold as "correctness of the Born rule"; but, as we will see, this is not strictly correct. As soon as we describe states of physical systems by density matrices, with the usual interpretation of convex combinations as probabilistic mixtures, the Born rule follows trivially and cannot be wrong. Rather, these experiments test deviations from the state space of quantum theory.
Higher-order interference can be formulated in the framework of generalized probabilistic theories as described in the following paper:
* C. Ududec, H. Barnum, and J. Emerson, Three Slit Experiments and the Structure of Quantum Theory, Found. Phys. 41, 396-405 (2011),
and it can be used as one of four postulates to derive the Hilbert space formalism of quantum theory:
* H. Barnum, M. P. Müller, and C. Ududec, Higher-order interference and single-system postulates characterizing quantum theory, arXiv:1403.4147.

It turns out that absence of third-order interference constrains the possible correlations, and implies the principle of local orthogonality that was briefly mentioned earlier on in the lecture! The following paper gives this result, and also gives some interesting background on the relation to quantum gravity, as well as more mathematical details than the lecture:
* J. Henson, Bounding quantum contextuality with lack of third-order interference, arXiv:1406.3281.


7. Generalized probabilistic theories, part I: motivation and definition of state spaces. (4.6.2014, download PDF)
The introductions to generalized probabilistic theories that I mentioned are here:
* P. Janotta and H. Hinrichsen, Generalized Probabilistic Theories: What determines the structure of quantum theory?, arXiv:1402.6562.
A bit of different and more mathematical style:
* B. Mielnik, Generalized quantum mechanics, Commun. Math. Phys. 37, 221-256 (1974).
A nice introduction, though with a bit of a different notation, is in Jon Barrett's paper:
* J. Barrett, Information processing in generalized probabilistic theories, Phys. Rev. A 75, 032304 (2007).
Also the following master thesis is great. The notation is exactly the same as in my lectures, and there are many pictures and very good explanation:
* C. Pfister, One simple postulate implies that every polytopic state space is classical, Master Thesis, ETH Zurich, arXiv:1203.5622.

To learn more about the (intricate) geometry of the set of quantum states (for 3 and more levels), have a look at the book by Bengtsson and Zyczkowski,
* I. Bengtsson and K. Zyczkowski, Geometry of Quantum States, Cambridge University Pres, 2006,
or at this little paper:
* I. Bengtsson, S. Weis, and K. Zyczkowski, Geometry of the set of mixed quantum states: An apophatic approach, Geometric Methods in Physics, XXX Workshop 2011, Trends on Mathematics, 175-197, Springer, Basel, 2013.


8. Generalized probabilistic theories, part II: transformations. (18.6.2014, download PDF)
One of the best resources for the quantum examples (that is: the Bloch ball; the proof that the (partial) transpose operation maps a maximally entangled state to a non-state) is the following book:
* M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambrige, 2000.
Transformations of a gbit are also discussed by Jon Barrett in his famous paper; however, the notation is a bit different:
* J. Barrett, Information processing in generalized probabilistic theories, Phys. Rev. A 75, 032304 (2007).
A good resource for Wigner's Theorem (quickly explained in this Wikipedia entry), containing a proof, is Bargmann's paper:
* V. Bargmann, Note on Wigner's Theorem on Symmetry Operations, J. Math. Phys. 5(7), 862-868 (1964).


9. Generalized probabilistic theories, part III: measurements. (25.6.2014, download PDF)
For very good explanations and nice pictures of the states and effects of a gbit, see again the paper by Janotta and Hinrichsen mentioned above. More about POVMs (positive operator-valued measures) in the quantum case, and their physical meaning, is explained in the quantum information book by Nielsen and Chuang, also mentioned above.
In the lecture, I mentioned that continuous POVMs on finite-dimensional quantum state spaces can always be understood as continuous classical mixtures of discrete POVMs. This is a result by Chiribella, d'Ariano and Schlingemann - see Exercise 8 below.
In the lecture, I do not talk about post-measurement states, but one can do that (for example, Pfister's Master thesis mentioned above is all about post-measurement states). As it turns out, the first general definition of a "quantum instrument", giving all possibilities what post-measurement states can look like in quantum theory, was defined in full generality for (even infinite-dimensional) generalized probabilistic theories! See the following paper:
* E. B. Davies and J. T. Lewis, An Operational Approach to Quantum Probability, Commun. Math. Phys. 17, 239-260 (1970).
The online PDF contains one part that I had to skip, which is on continuous reversible time evolutions and uncertainty relations. The state spaces considered there are such that the sets of normalized states are the p-norm unit balls. These state spaces have also been considered in the following paper, where it was shown that the maximal CHSH Bell violation (in quantum theory, the Tsirelson bound) can be derived from the shape of that state space only.
* G. ver Steeg and S. Wehner, Relaxed uncertainty relations and information processing, Quantum Information and Computation 9, 0801-0832 (2009).


10. Generalized probabilistic theories, part IV: composite systems. (2.7.2014, download PDF)
The parameters N and K have first been introduced by Wootters and Hardy:
* W. K. Wootters, Quantum mechanics without probability amplitudes, Found. Phys. 16, 391-405 (1986).
* L. Hardy, Quantum Theory From Five Reasonable Axioms, arXiv:quant-ph/0101012.
The paper by Hardy also contains more material on local tomography. To learn more about quaternionic quantum mechanics, see Graydon's Master thesis, linked in Exercise 4 below. There is also the book by Adler,


11. Boxworld, and a general no-cloning theorem. (9.7.2014, download PDF)
More about boxworld can be found in Jonathan Barrett's paper,
* J. Barrett, Information processing in generalized probabilistic theories, Phys. Rev. A 75, 032304 (2007).
The result that reversible transformations in boxworld are trivial is here:
* D. Gross, Markus Müller, R. Colbeck, and O. C. O. Dahlsten, All reversible dynamics in maximally non-local theories are trivial, Phys. Rev. Lett. 104, 080402 (2010).
The generalized no-cloning theorem can be found in the following paper:
* H. Barnum, J. Barrett, M. Leifer, and A. Wilce, Cloning and Broadcasting in Generic Probabilistic Models, arXiv:quant-ph/0611295.
Regarding no-cloning in (the special case of) quantum theory, see the book by Nielsen and Chuang linked above. The original paper is
* W. K. Wootters and W. H. Zurek, A single quantum cannot be cloned, Nature 299, 802-803 (1982).


12. A derivation of quantum theory from operational postulates, part I. (16.7.2014, download PDF)
The modern "reconstruction" approach has been pioneered by Lucien Hardy:
* L. Hardy, Quantum Theory From Five Reasonable Axioms, arXiv:0101012.
However, there is a long history of attempts in this direction; see the references in Hardy's paper and the other papers mentioned below. Maybe the most significant difference of the modern approach is the emphasis of finite-dimensional quantum theory.
The paper that I talked about in this lecture is the following:
* Ll. Masanes and Markus P. Müller, A derivation of quantum theory from physical requirements, New J. Phys. 13, 063001 (2011).
There is also a book chapter with a less technical summary of this result:
* M. P. Müller and Ll. Masanes, Information-theoretic postulates for quantum theory, to appear in "Quantum Theory: Informational Foundations and Foils", G. Chiribella and R. Spekkens (editors), Springer. arXiv:1203.4516.

Two other papers that roughly appeared at the same time are the following:
* B. Dakic and C. Brukner, Quantum Theory and Beyond: Is Entanglement Special?, in Deep Beauty: Understanding the Quantum World through Mathematical Innovation, Ed. H. Halvorson (Cambridge University Press), 365-392 (2011).
* G. Chiribella, G. M. D'Ariano, and P. Perinotti, Informational derivation of Quantum Theory, Phys. Rev. A 84, 012311 (2011).


13. A derivation of quantum theory from operational postulates, part II. (23.7.2014, download PDF)
Regarding the discussion in the end (spacetime versus quantum state space), see the following two papers:
* M. P. Müller and Ll. Masanes, Three-dimensionality of space and the quantum bit: an information-theoretic approach, New J. Phys. 15, 053040 (2013).
* B. Dakic and C. Brukner, The classical limit of a physical theory and the dimensionality of space, to appear in "Quantum Theory: Informational Foundations and Foils", Eds. G. Chiribella and R. Spekkens. arXiv:1307.3984.


Research / literature search questions (to get credit points)

1. [Simon Müller, Tobias Wintermantel] What is the Navascues-Pironio-Acín hierarchy, and what is a "semidefinite program"? Download PDF.
This is mainly about the following paper:
* M. Navascues, S. Pironio, and A. Acín, A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations, New J. Phys. 10, 073013 (2008).
To read about "semidefinite programming", you may have to find some more literature.

2. [Marcus Held, Jan Blume] The following two sources claim to use quantum states to send information faster than light - which we have learned is impossible. Download PDF.
* :-( R. Srikanth, Noncausal Superluminal Nonlocal Signalling, arXiv:quant-ph/9904075.
* :-/ J. Parisi and O. E. Rössler, Mit einem Sarfatti-Telegraphen zurück in die Vergangenheit?, press release by Oldenburg University (2001).
For at least one of these sources, work out in detail (!) why it doesn't work.
Note: just writing "but we've proven no-signalling in the lecture" is not enough: people can always doubt whether the assumptions underlying the mathematical proofs apply to their situation. Still: the proposed protocols don't work. Why?

3. [Alireza Beygi] Work out a detailed proof that quantum behaviors are macroscopically local, and that macroscopic locality implies the Tsirelson bound. Download PDF.
This refers mainly to lecture 5. See the references there. You may have to look also at the "hierarchy"-paper mentioned in question 1.

6. [Marius Krumm, Fabian Lauble] What is contextuality, and what is the principle of consistent exclusivity? Download PDF.
Unfortunately, I don't have time in my lectures to discuss contextuality, so if you want to learn more about this fascinating topic, you should work on this question! A good introduction is in Peres' book. Regarding consistent exclusivity, it is enough if you try to understand the proof in the following paper of why the maximum quantum violation of the KCBS inequality follows from that principle:
* A. Cabello, Simple explanation of the quantum violation of a fundamental inequality, Phys. Rev. Lett. 110, 060402 (2012).