Quantum Physics

We introduce a technique for applying quantum expanders in a distributed fashion, and use it to solve two basic questions: testing whether a bipartite quantum state shared by two parties is the maximally entangled state and disproving a generalized area law. In the process these two questions which appear completely unrelated turn out to be two sides of the same coin. Strikingly in both cases a constant amount of resources are used to verify a global property.

The Elitzur-Vaidman bomb tester allows the detection of a photon-triggered bomb with a photon, without setting the bomb off. This seemingly impossible task can be tackled using the quantum Zeno effect. Inspired by the EV bomb tester, we define the notion of "bomb query complexity". This model modifies the standard quantum query model by measuring each query immediately after its application, and ends the algorithm if a 1 is measured.

We show that the bomb query complexity is asymptotically the square of the quantum query complexity. Moreover, we will show how this characterization inspires a general theorem relating classical and quantum query complexity, and derive new algorithms from this theorem.

After a brief motivation of this question, the presentation is divided in two parts. We first introduce the principle of quantum information causality, which states the maximum amount of quantum information that a transmitted quantum system can communicate as a function of its Hilbert space dimension, independently of any quantum physical resources previously shared by the communicating parties. The second part of the talk considers superdense coding within the framework of general probabilistic theories and addresses the question of why in quantum theory, no more than two bits can be communicated by transmission of a single, entangled, qubit. We introduce hyperdense coding in general probabilistic theories: superdense coding in which N

> 2 bits are communicated by transmission of a system  that locally

encodes at most one bit, and present protocols with N arbitrarily large. Our hyperdense coding protocols imply superadditive classical

capacities: two entangled systems can encode N > 2 bits, even though each system locally encodes at most one bit. Our protocols violate either a reversibility condition or tomographic locality.