Workshop on Physics and Information 2015

Paris, June 29-30 and July 1st, 2015


Understanding physics from the point of view of information led to the emergence of many new fields over the last years. These fields correspond to different approaches to the notion of information, from the perspective of mathematics, computer science and philosophy. This workshop aims to represent all of these and their interaction with quantum physics.


  • Maël Pégny (IHPST, Paris): Everything a Physicist Always Wanted to Know about Computation, but Never Dared to Ask

    In this synthetic presentation, I will try to give a state of the art of the various relations between computation theory and physics that have emerged in the recent literature, and explain why computation theory should be a topic of interest for physicists.

  • Gabriel Senno (Universidad de Buenos Aires, Argentina): Consequences of the Physical CTT over experimental setups in quantum physics

    We study the limitations that the physical Church-Turing thesis imposes when performing experimental verifications of quantum theory. First, we show that different preparations of the (theoretically) same proper mixed state need to be non-computable in order to be indistinguishable. Then, we show that using independent PRNGs to choose the inputs for a Bell tests is not enough to observe a proper Bell inequality violation. That is, we give a local model that reproduces any correlations arising from a Bell scenario in which the measurement choices were made following algorithms.

  • Ämin Baumeler (USI Lugano, Switzerland): Classical correlations without causal order

    An often made assumption in physical theories is the existence of a global time. If one relaxes this assumption and requires local validity of some theory and logical consistency only, then a larger set of correlations can be obtained - correlations without predefined causal order. Such theories have the advantage that causal relations emerge from the observed correlations. In a sense, these theories can be thought of as a natural extension of other theories by dropping an unnecessary assumption. Here, we look at classical correlations without predefined causal order (local validity of classical probability theory is assumed) and discuss some features these correlations have.

  • Cyril Branciard (Institut Neel, Grenoble, France): Does a quantum state represent reality, or just our knowledge of it?

    The status of the wave function has been the subject of active debates since the very birth of quantum theory. What is it? Does it represent reality, or our knowledge of it? A general framework has recently been developed, allowing one to address these questions formally. In late 2011 Pusey, Barrett and Rudolph (PBR) proved a breakthrough theorem, suggesting that the knowledge interpretation was not tenable [1]. I will review these results and present new developments, showing in particular that the knowledge interpretation cannot (fully) explain the indistinguishability of nonorthogonal quantum states [2].
    [1] M. F. Pusey, J. Barrett, T. Rudolph, Nat. Phys. 8, 475-478 (2012).
    [2] J. Barrett et al., Phys. Rev. Lett. 112, 250403 (2014); M. S. Leifer, Phys. Rev. Lett. 112, 160404 (2014); C. Branciard, Phys. Rev. Lett. 113, 020409 (2014); M. Ringbauer et al., Nat. Phys. 11, 249 (2015).

  • Miguel Navascués (Bilkent University, Ankara): Bounding the set of finite-dimensional quantum correlations

    (joint work with T. Vértesi)
    I will describe a simple method to derive high performance semidefinite programming relaxations for optimizations over complex and real operator algebras in finite dimensional Hilbert spaces. The method is very flexible, easy to program and allows the user to assess the behavior of finite dimensional quantum systems in a number of interesting setups. After proving the convergence of the scheme, I will present applications in quantum nonlocality, 1-way quantum communication complexity and temporal correlation scenarios. Then I will reveal an intriguing connection with Matrix Product States, an ansatz used in condensed matter physics to approximate the ground state of local Hamiltonians in one (spatial) dimension. Exploiting this connection, I analyze the complexity of the method for high relaxation orders and derive new positive semidefinite constraints with the potential to boost the speed of convergence of the scheme.

  • Jérémie Roland (ULB, Belgium): Quantum query complexity: Adversaries, polynomials and direct product theorems

    Quantum query complexity has recently seen a lot of progress. One of the most prominent results is certainly that the generalized adversary bound characterizes the bounded-error quantum query complexity for any function. This fundamental result however does not answer all questions about quantum query complexity as it suffers from two limitations. First, the result is non constructive, and there still exist functions for which we can prove a tight lower bound using the polynomial method, the other main lower bound technique, but for which the optimal adversary matrix is unknown. Secondly, it is sometimes necessary to prove lower bounds for exponentially low success probabilities, a regime where the generalized adversary method might not be tight. A typical example is proving a direct product theorem, which essentially states that for solving k instances of a problem in parallel, one cannot do much better than solving each instance independently.
    The goal of this talk will be to provide new techniques to tackle those limitations. More precisely, we will show that the multiplicative adversary method, a variation of the original adversary method, generalizes not only the generalized adversary method, but also the polynomial method, so that it essentially encompasses all known lower bound methods. Therefore, this provides a constructive approach to cast polynomial lower bounds into the adversary method framework. Moreover, since the multiplicative adversary method satisfies a strong direct product theorem and is at least as strong as the generalized adversary bound which is tight, this implies that the quantum query complexity of any function satisfies a direct product theorem.
    Based on joint work with Andris Ambainis, Loïck Magnin, Martin Rötteler and Troy Lee [CCC'11,arXiv:1012.2112] [CCC'12,arXiv:1104.4468] [STACS'13,arXiv:1209.2713]

  • Raymond Lal (University of Cambridge, UK): The topology of contextuality: a new perspective on quantum no-go theorems

    Contextuality is a key feature of quantum mechanics that provides an important non-classical resource for quantum information and computation. Recently, a unified treatment of contextuality in quantum theory has emerged, pioneered by Abramsky and Brandenburger, which subsumes no-go results such as Bell-type non-locality and the Hardy paradox. We can use this approach to show how an important class of contextuality arguments has a topological origin. More specifically, we show that 'all-vs-nothing' proofs of contextuality, such as the well-known Mermin-GHZ argument, are witnessed by cohomological obstructions.

  • Janet Anders (University of Exeter, UK): Information and thermodynamics

    I will give an overview over recent developments in quantum thermodynamics.

  • Joseph Bowles (University of Geneva, Switzerland) EPR steering and local models for entangled quantum states

    EPR steering is a form of nonlocality whereby one party (Alice) tries to convince another (Bob) that they hold an entangled state by making measurements on her half of the state in order to nonlocally "steer" Bob's half. At the level of definition, EPR steering is asymmetric since the roles played by the two parties are inequivalent - a feature not present in Bell nonlocality. This led to the natural question of whether one can find a state which exhibits "one-way steering", that is, a state that exhibits EPR steering in one direction (say from Alice to Bob) but which does not when the roles of the parties are reversed. Here, I will introduce the concept of EPR steering and present a positive solution to the above question [1].
    Related to this, I will discuss the classical simulation of entangled states, concentrating on a recent work which aims to quantify the minimum number of classical resources needed to simulate entanglement. I will present the first example [2] of an entangled quantum state which can be simulated with finite classical resources and some remaining related open questions.
    [1] Joseph Bowles, Tamás Vértesi, Marco Túlio Quintino, and Nicolas Brunner, Phys. Rev. Lett. 112, 200402 (2014)
    [2] Joseph Bowles, Flavien Hirsch, Marco Túlio Quintino, and Nicolas Brunner, Phys. Rev. Lett. 114, 120401 (2015)

  • Leonardo DiSilvestro (Telecom ParisTech, France): Quantum Protocols within Spekkens' Toy Model

    Quantum theory is believed to provide improvements both in computational power and security with respect to classical information theory. In order to better understand the origin of these improvements, we translate emblematic quantum protocols to Spekkens' toy model - a local hidden variable theory which is phenomenologically very close to quantum theory. Despite the toy model non being able to provide any computational speed up with respect to quantum theory, we see that it can still provide similar security statements as in the quantum case. We notice how the existence of anticommutation relations between toy measurements and toy transformations and the existence of `toy purifications' seems to be sufficient to implement many quantum protocols within the toy model. In particular, we show that error correction, secret sharing, and blind and verified computation are indeed possible in the toy model along with providing a proof of the impossibility of toy-bit commitment. Our results firstly suggest that purifications and anticommutaiton relations provide the structure behind the existence of these protocols within quantum theory; and secondly, the ability to perform blind and verified computation in the toy model strongly suggest that not only steering is a sufficient property for such a protocol, but that any probabilistic theory featuring purification is indeed apt to implement blind and verified computation.

  • William Matthews (University of Cambridge, UK): Capacities of Quantum Channels

    I will give an overview of various information carrying capacities of quantum channels and their properties, and discuss recent work [1] which demonstrates a difficulty in detecting whether a given channel has any capacity at all for transmitting quantum information.
    [1] "Unbounded number of channel uses may be required to detect quantum capacity" T Cubitt, D Elkouss, W Matthews, M Ozols, D Pérez-García, S Strelchuk

  • Petros Wallden (Univ. of Edinburgh, UK): Quantum Measure Theory and Contextuality

    Quantum measure theory is a generalisation of probability theory, where Kolmogorov's sum rule is replaced by a weaker condition that essentially rules-out higher-order interference. Standard quantum theory can be viewed as a special case of a quantum measure, which can be derived using the consistent histories approach to quantum theory. This talk has two parts. In the first part, when considering contextuality scenarios, we prove that the existence of a strongly-positive joint quantum measure on the set of counterfactual outcomes, limits the set of allowed correlations to (essentially) the set of "almost quantum" correlations. The existence of classical joint probability measure on the space of counterfactual outcomes implies that those correlations are non-contextual, and we can view the quantum measure analogue of this as a "quantum non-contextuality" condition. The second part of this talk, involves phrasing measurement-based quantum computation (MBQC) as a quantum measure, using the histories formalism. We discuss the power of contextuality in MBQC and put in a unified framework spatial contextuality (non-locality) and "temporal contextuality".

  • Frederic Grosshans (LAC, Orsay, France): A Tight Lower Bound for the BB84-states Quantum-Position-Verification Protocol

    Joint work with Jérémy Ribeiro.
    Preprint arxiv:1504.07171
    We use the entanglement sampling techniques developed by Dupuis, Fawzi and Wehner to find a lower bound on the entanglement needed by a coalition of cheater attacking the quantum position verification protocol using the four BB84 states in the scenario where the cheaters have no access to a quantum channel but share a (possibly mixed) entangled state $\Phi$. For a protocol using $n$ qubits, a necessary condition for cheating is that the max- relative entropy of entanglement $E_{max}(\Phi)\geq n-O(\log n)$. This improves previously known best lower bound by a factor $\sim 4$, and it is essentially tight, since this protocol is vulnerable to a teleportation based attack using $n-O(1)$ ebits of entanglement.

Click on a title to see the abstract


Mon 29/06 Tue 30/06 Wed 01/07
9:30 Matthew Anders Grosshans
10:30 Coffee break Coffee break Coffee break
11:00 Roland Baumeler DiSilvestro
12:00 Lunch Lunch Lunch
14:00 Pégny Branciard Wallden
15:00 Senno Lal Open session
16:00 Coffee break Coffee break
16:30 Navascués Bowles


The workshop will take place at Institut Henri Poincaré in Amphi DARBOUX.