Patrick Hayden: Online Seminars


From tornadoes to black holes:
How to survive an information catastrophe

[Perimeter Institute public lecture series]

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]



I describe a special information-theoretic 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 Ryu-Takayanagi 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 Ryu-Takayanagi 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]



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 min-entropies, in which form it can be used to analyze the security of extractors against quantum adversaries.


From low-distortion embeddings to information locking

[Perimeter Institute quantum information seminar]



I'll describe a connection between uncertainty relations, information locking and low-distortion 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 (1-e) 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]


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 Haar-measure 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]

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 "half-way" 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 half-way point remains concealed until the half-way point, and then emerges quickly. These conclusions hold because typical local quantum circuits are efficient encoders for quantum error-correcting 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  Other versions of this talk available here and here.



The power of forgetting
[Perimeter Institute]


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 high-quality 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 quant-ph/0606225.  Variants of this talk are available here and here.



Introduction to quantum Shannon theory


This talk is the first half of a two-hour crash course in quantum Shannon theory given at the Perimeter Institute in June 2005.



The communication cost of entanglement transformations
[Berkeley MSRI]

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 quant-ph/0204092, quant-ph/0204093 and quant-ph/0410052.

Hiding quantum data

[Berkeley MSRI]

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 vice-versa. 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 no-cloning 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 quant-ph/0207147. Proofs of the conjectures can be found in quant-ph/0307104.







Bellairs workshops
Online seminars
Curriculum vitae

CS site
McGill site
Contact information