Information Primitives and Laws of Nature

A workshop 13-17 May 2008 at ETH Zürich.

This workshop saw theoretical computer science meet quantum physics to address two interrelated questions of overarching importance:
1. Why are the laws of nature quantum?
2. What are the fundamental possibilities and impossibilities of information processing?

Computer science and physics give two different ways of understanding the world. Consider for example a computation. From the perspective of computer science a particular protocol is carried out. This can be broken up into a set of primitive operations and the possibility of performing a given protocol hinges on whether each primitive protocol is possible.

The physics perspective would instead view the computer as a physical system and therefore governed by quantum theory. Thus from the perspective of physics, the fundamental possibilities and impossibilities of information processing derive from the laws of nature. Understanding this derivation is crucial for understanding the potential of quantum information science. Going in the other direction one can attempt to formulate our theory of nature in terms of information primitives. This may provide a derivation of quantum physics from operational restrictions such as no cloning. It is hoped that the physical content of such an axiomatization would be much clearer than the current abstract quantum axioms.

This workshop revolved around these questions, including addressing recent work on:
-Finding information theoretic considerations that explain why quantum correlations have their exact form.
-Fully axiomatizing quantum theory in terms of information primitives (c.f. the Fuchs-Brassard conjecture).
-Deriving given information primitives, such as key distribution, from a limited set of physical assumptions, rather than all of quantum theory.
-Considering more general notions of information.
-Studying mathematical frameworks for tackling these questions, such as generalized probabilistic theories.
-Information processing in operational foil theories such as Barrett's GNST.


Howard Barnum (Los Alamos)
Jonathan Barrett (Cambridge)
Cyril Branciard (Geneve)
Caslav Brukner (Wien)
Nicolas Brunner (Geneve)
Matthias Christandl (Cambridge/München)
Maurio D'Ariano (Pavia)
Torsten Franz (Braunschweig)
Chris Fuchs (Perimeter Institute)
Nicolas Gisin (Geneve)
Jonathan Oppenheim (Cambridge)
Terry Rudolph (Imperial)
Valerio Scarani (Singapore)
Ruediger Schack (Royal Holloway)
Volkher Scholz (Braunschweig)
Tony Short (Cambridge)
Rob Spekkens (Cambridge)
Ernst Specker (ETH Zurich)
Antoine Suarez (Cent. Quant. Phil., Zurich)
Alain Tapp (Montreal)
Ben Toner (CWI Amsterdam)
Alexander Wilce (Susquehanna)
Stephanie Wehner (Caltech)
Reinhard Werner (Braunschweig)
Hans Westman (Perimeter)
Jurg Wullschleger (Bristol)


Howard Barnum

Non-classicality without entanglement enables bit commitment

Jonathan Barrett 

Is quantum theory special?  

Matthias Christandl

The Classical and Quantum Finite de Finetti Theorems

Terry Rudolph

Data Tables and Ontological Models

Ben Toner

Coherent state exchange in multi-prover quantum interactive proof systems

We show that any number of parties can coherently exchange any one pure quantum state for another, without communication, given prior shared entanglement. Two applications of this fact to the study of multi-prover quantum interactive proof systems are given. First, we prove that there exists a one-round two-prover quantum interactive proof system for which no finite amount of shared entanglement allows the provers to implement an optimal strategy. More specifically, for every fixed input string, there exists a sequence of strategies for the provers, with each strategy requiring more entanglement than the last, for which the probability for the provers to convince the verifier to accept approaches 1. It is not possible, however, for the provers to convince the verifier to accept with certainty with a finite amount of shared entanglement. The second application is a simple proof that multi-prover quantum interactive proofs can be transformed to have near-perfect completeness by the addition of one round of communication.

Joint work with Debbie Leung and John Watrous.

Caslav Brukner

Physics of systems with limited information resources

Jonathan Oppenheim 

Generalized evolution laws

Alex Wilce

Teleportation Protocols for Abstract State Spaces

Slides (.pdf)

In a well-known generalization of classical probability theory, arbitrary compact convex sets serve as abstract state spaces for physical systems (with classical systems corresponding to simplices and quantum systems, to state spaces of $C^{\ast}$ algebras). One can define tensor products of such abstract state spaces, modeling composite systems subject to a no-signaling condition. Once this is done, many things one might have been inclined to regard as characteristically {\em quantum} phenomena -- notably, the general phenomenon of entanglement, as well as no-cloning and no-broadcasting theorems -- turn out to be quite generic features of all non-classical probabilistic theories. On the other hand, the existence of a teleportation protocol is a strong constraint, moving us closer to quantum theory. In this talk, after briefly summarizing the framework of abstract state spaces, I'll outline what we currently understand about teleportation in this setting.

Joint work with Howard Barnum, Jon Barrett and Matt Leifer.

Ernst Specker

Infuturabilia and Quantum Logic

Rob Spekkens

The power of epistemic restrictions in axiomatizing quantum theory: from trits to qutrits

Slides (.ppt)
Chris Fuchs

SICkening axioms for quantum theory

Reinhard Werner

Three Old Schools of Axiomatic Quantum Mechanics

Mauro D'Ariano

Matrix-algebra representation of probabilistic theories: the special case of Quantum Mechanics.

Paper (.pdf)

In all probabilistic operational theories the
"transformations" have a C*-algebra representation over the linear space spanned by "effects". The Choi-Jamiolkowski isomorphism is sufficient to restrict the operational algebra to the quantum one, allowing to derive a composition law for effects, and leading to a systematic routine to derive a quantum operator representation of probabilities. Possible candidates for operational principles for the Choi-Jamiolkowski isomorphism are discussed.

Ruediger Schack

Quantum Bayesianism, tomography, and random numbers

Slides (.pdf)
Nicolas Gisin

Towards understanding Quantum correlations

Slides .pdf
Jurg Wullschleger

Single-Serving Quantum Compression

Stephanie Wehner

The (quantum) moment problem: deriving bounds on (quantum) correlations

Slides (.pdf)

The relevant references:
1. The quantum moment problem and bounds on entangled multi-prover games
A. Doherty, Y.-C. Liang, B. Toner and S. Wehner, to appear in IEEE Conference on Computational Complexity '08, arXiv:0803.4373

2. Higher entropic uncertainty relations for anti-commuting observables
S. Wehner and A. Winter, To appear in Journal of Mathematical Physics, arXiv:0710.1185

3. Generalized non-local theories from relaxed uncertainty relations
W. van Dam, G. Ver Steeg and S. Wehner, In preparation.

Hans Westman

A Construction Method for Candidates of \psi-Epistemic Theories.

In deBroglie-Bohm theory the quantum state plays the role of a guiding field. We investigate whether this is a universal feature shared by all hidden variable theories, or if it is merely a peculiarity of deBroglie-Bohm theory. We exhibit a class of theories for which the quantum state plays the role, not as a guiding agent, but only as information about an underlying ontic state. We show that such theories are consistent with the Schrodinger equation if and only if there are positive solutions to a gigantic system of linear equations. We end by modeling quantum measurements of a qubit within such theories and discuss possible ramifications of Hardy's ontological excess baggage theorem.
Valerio Scarani

Cryptography and non-locality

Slides (.ppt)

The pioneering work by Barrett, Hardy and Kent stimulated the study of the link between the possibility of distributing non-local correlations and the possibility of establishing secure communication.

Two approaches have been explored:

(1) Eve is not constrained by quantum physics, only by no-signaling. The latest results imply that security cannot be guaranteed in the most general possible scenario; the minimal assumptions that have to be made are under study. The interest of this approach resides in the exploration of the ultimate requirements for unconditional composable security of communication.

(2) Eve is constrained by quantum physics but (contrary to usual security proofs of QKD) Alice and Bob have to work in a black-box scenario: they can only choose their input and receive an outcome. The bound for this "device-independent security" has been found against collective attacks. This approach relies on the exactness of quantum physics to derive the bound, but does not require the end users to have any knowledge of quantum (or even classical) physics.

Volkher Scholz

Tensor norms and Tsirelson's problem

Alain Tapp

A limit on nonlocality in any world in which communication complexity is not trivial

Slides (.ppt)

Bell proved that quantum entanglement enables two spacelike separated parties to exhibit classically impossible correlations. Even though these correlations are stronger than anything classically achievable, they cannot be harnessed to make instantaneous (faster than light) communication possible. Yet, Popescu and Rohrlich have shown that even stronger correlations can be defined, under which instantaneous communication remains impossible. This raises the question: Why are the correlations achievable by quantum mechanics not maximal among those that preserve causality? We give a partial answer to this question by showing that slightly stronger correlations would result in a world in which communication complexity becomes trivial.


G. Brassard, H. Buhrman, N. Linden, A. Méthot, A. Tapp et F. Unger, A limit on non-local correlations in any world where communication complexity is not trivial, Physical Review Letter, vol. 96, 250401, 2006.

Tony Short

No purification for two copies of a noisy entangled state.

Slides (.ppt)

I will show that two copies of a noisy entangled state cannot be purified into a single less noisy, and hence more entangled, state using local operations and classical communication. This result is quite general, requiring only that there exists some local `twirling'
operations that map all states onto the relevant family, and hence applies to Werner states in quantum theory, noisy PR-boxes in `box-world' (Generalised Non-Signalling Mechanics), and many other families of states in probabilistic theories.

In recognition of this workshop having been inspired by the Foils workshop 2007, the organizers of that workshop all chaired a session. They are: Jonathan Barrett, Tony Short, and Rob Spekkens. Furthermore ETH members Roger Colbeck, Oscar Dahlsten, Renato Renner, and Stefan Wolf all chaired a session.

We gratefully acknowledge generous support from the Centre for Theoretical Studies and additional support from QSIT.