From tornadoes to black holes:
How to survive an information catastrophe
[Perimeter Institute public lecture series]
Abstract:
Black holes are regions of space with gravity so strong that nothing can escape
from them, not even light. This isn't science fiction  there's even a gigantic
black hole at the center of our galaxy. It's hard to imagine a more effective
way to irrevocably erase and destroy a computer's hard drive than to drop it
into a nice big black hole. But is the information on that drive really gone
forever? Paradoxically, there's a good chance that not only does the information
come back, it comes back in the blink of an eye. This surprise return of the
information is based on the same principles that might someday make reliable
quantum computers a reality. In fact, engineers are already exploiting these
principles to help distribute software and stream video over the internet. And
that's where the tornadoes come in...
Holographic mutual information is monogamous
[Perimeter Institute conference on Relativistic Quantum Information]
Abstract:
I describe a special informationtheoretic property of quantum field theories with holographic duals: the mutual informations among arbitrary disjoint spatial regions A,B,C obey the inequality I(A:BC) >= I(A:B)+I(A:C), provided entanglement entropies are given by the RyuTakayanagi formula. Inequalities of this type are known as monogamy relations and are characteristic of measures of quantum entanglement. This suggests that correlations in holographic theories arise primarily from entanglement rather than classical correlations. Moreover, monogamy property implies that the RyuTakayanagi formula is consistent with all known general inequalities obeyed by the entanglement entropy, including an infinite set recently discovered by Cadney, Linden, and Winter; this constitutes significant evidence in favour of its validity.
Operators in multiuser information theory: A conjecture
[Banff Centre workshop on operator structures in quantum information]
Abstract:
Typical subspaces form the bridge between entropy formulas and the communications protocols of quantum information theory. In multiuser settings, unfortunately, the typical subspaces that appear naturally in any given problem often fail to usefully intersect, leading to many difficulties. In this talk, I’ll present a conjecture about the approximation of operators on tensor product spaces that, if true, resolves a number of open questions in quantum information theory. Some special cases of the conjecture and its
consequences, which I’ll list, are known to be true. A generalization of the conjecture can equally well be phrased in terms of minentropies, in which form it can be used to analyze the security of extractors against quantum adversaries.
From lowdistortion embeddings to information locking
[Perimeter Institute quantum information seminar]
Abstract:
I'll describe a connection between uncertainty relations, information locking and lowdistortion embeddings of L2 into L1. Exploiting this connection leads to the first explicit construction of entropic uncertainty relations for a number of measurements that is polylogarithmic in the dimension d while achieving an average measurement entropy of (1e) log d for arbitrarily small e. From there, it is straightforward to obtain the first strong information locking scheme that is efficiently computable using a quantum computer. This locking scheme can be interpreted as a method for encrypting classical messages using a key of size much smaller than the message length. Other applications include efficient encodings for amortized quantum identification over classical channels and new string commitment protocols.
Applications and desiderata for random matrices in quantum information
[Banff Centre workshop on sparse random structures]
Abstract:
As in “classical” computer science, the probabilistic method and randomized constructions are ubiquitous in quantum information. Because quantum mechanics is noncommutative, the random
objects of study are invariably matrices. Quantum information theory therefore provides a rich source
of random matrix problems. Applications range from the best known codes for sending quantum data
through noisy media to subroutines in quantum algorithms and new encryption procedures. The first step
in developing these ideas usually involves demonstrating that a very large random unitary transformation
selected according to the Haar measure accomplishes the appropriate task. The next, and often much
harder step, is to find an efficiently constructible replacement for the unwieldy Haarmeasure unitaries. I’ll
illustrate some of these applications, describe the progress that has been made on efficient constructions
and pose some open problems.
Black holes as mirrors
[UC Berkeley physics colloquium]
Abstract:
I'll discuss information retrieval from evaporating black holes, assuming that the internal dynamics of a black hole is unitary and rapidly mixing, and assuming that the retriever has unlimited control over the emitted Hawking radiation. If the evaporation of the black hole has already proceeded past the "halfway" point, where half of the initial entropy has been radiated away, then additional quantum information deposited in the black hole is revealed in the Hawking radiation very rapidly. Information deposited prior to the halfway point remains concealed until the halfway point, and then emerges quickly. These conclusions hold because typical local quantum circuits are efficient encoders for quantum errorcorrecting codes that nearly achieve the capacity of the quantum erasure channel. This estimate of a black hole's information retention time, based on speculative dynamical assumptions, is just barely compatible with the black hole complementarity hypothesis. Based on joint work with John Preskill.
Based on arXiv.org:0708.4025. Other versions of this talk available here and here.
The power of forgetting
[Perimeter Institute]
Abstract:
Thermodynamics places surprisingly few fundamental constraints on
information processing. In fact, most people would argue that it imposes
only one, known as Landauer's Principle: a process erasing one bit of
information must release an amount kT ln 2 of heat. It is this simple
observation that finally led to the exorcism of Maxwell's Demon from
statistical mechanics, more than a century after he first appeared.
Ignoring the lesson implicit in this early advance, however, quantum
information theorists have been surprisingly slow to embrace erasure as a
fundamental primitive. Over the past couple of years, however, it has
become clear that a detailed understanding of how difficult it is to erase
correlations leads to a nearly complete synthesis and simplification of
the known results of asymptotic quantum information theory. As it turns
out, surprisingly many of the tasks of interest, from distilling
highquality entanglement to sending quantum data through a noisy medium
to many receivers, can be understood as variants of erasure. I'll sketch
the main ideas behind these discoveries and end with some speculations on
what lessons the new picture might have for understanding information loss in real physical systems.
Based on quantph/0606225. Variants of this talk are available here and here.
Introduction to quantum Shannon theory
[Video/PDF][PPT]
Abstract:
This talk is the first half of a twohour crash course in quantum Shannon theory given at the Perimeter Institute in June 2005.
The communication cost of entanglement transformations
[Berkeley MSRI]
Abstract:
I discuss the amount of communication required for two parties to transform some given joint pure state into another one. Starting with exact conversions, I describe the necessary and sufficient conditions for such a transformation to be possible using a fixed number of either bits or qubits of communication. In the first case, the question can (nearly) be reduced to Horn's Problem, which was elegantly resolved by Klyachko and others in the 1990s. In the second case, the question can again be addressed using the techniques of symplectic geometry: the set of states accessible from a given input state by making use of a fixed number of qubits of communication can be identified with the moment polytope of an appropriate group action. A set of inequalities completely describing the polytope can then be extracted fromrecent work by Berenstein and Sjamaar. So far, no such detailed results exist for approximate conversions between states but an analysis using Renyi entropies can be used to demonstrate, for example, that the task of asymptotic entanglement dilution of n EPR pairs will require O(\sqrt{n}) bits of communication.
Based on quantph/0204092, quantph/0204093 and quantph/0410052.
Hiding quantum data
[Berkeley MSRI]
Abstract:
Recent work has shown how to use the laws of quantum mechanics to keep classical and quantum bits secret in a number of different circumstances. Among the examples are private quantum channels, quantum secret sharing and quantum data hiding. In this seminar I explain how a method for keeping two classical bits hidden in any such scenario can be used to construct a method for keepingone quantum bit hidden, and viceversa. In the realm of quantum data hiding, this provides a method for constructing bipartite and multipartite hiding schemes for qubits from the previously known constructions for hiding bits. The only constraints on the authorized sets for these multipartite hiding schemes are the same as those for quantum secret sharing, namely monotonicity and the nocloning theorem. The second half of the seminar is devoted to exploring the connection between approximate state randomization and data hiding. In particular, conjectures about approximate state randomization (ed.  since proved to be correct) imply the existence of new data hiding protocols.
Based on quantph/0207147. Proofs of the conjectures can be found in quantph/0307104.
