Quantum Information

I look at the information-processing involved in a quantum computation, in terms of the difference between the Boolean logic underlying a classical computation and the non-Boolean logic represented by the projective geometry of Hilbert space, in which the subspace structure of Hilbert space replaces the set-theoretic structure of classical logic. I show that the original Deutsch XOR algorithm, Simon's algorithm, and Shor's algorithm all involve a similar geometric formulation. In terms of this picture, I consider the question of where the speedup relative to classical algorithms comes from.

In this talk I will expose different results concerning the properties of quantum many-body systems: on the one hand, I will introduce the concept of fine-grained entanglement loss together with its relation with majorization relations along parameter flows and Renormalization Group flows. The machinery of Conformal Field Theory will allow us to derive very general analytical properties, and some examples -like the XY quantum spin chain- will also be considered. On the other hand, I will describe results concerning the classical simulability of quantum many-body systems by means of Matrix Product States. In particular, I will present an approximated classical simulation of a quantum algorithm by adiabatic evolution solving hard instances of an NP-Complete problem up to 100 qubits.

I will discuss the design of degenerate quantum error correcting codes for an arbitrary Pauli channel. At noise levels slightly beyond those for which a random stabilizer code does not allow high fidelity transmission with a nonzero rate, our codes usually have a rate which is strictly positive. In fact, there exist Pauli channels for which our codes outperform a random stabilizer code whenever the random coding rate is less than 0.04, which is a couple of orders of magnitude larger than the previous examples of this effect. I'll also present a fairly straightforward explanation of why these codes work and discuss how their performance scales with block size and what this scaling suggests even better codes will look like.

The information spectrum approach gives general formulae for optimal rates of codes in many areas of information theory. In this talk I shall relate the information spectrum approach to Shannon information theory and explore its relationship to ``entropic'' properties including subadditivity, chain rules, Araki-Lieb inequlities, and monotonicity.

The concept of entanglement plays a central role in the field of strongly correlated quantum systems: it gives rise to fascinating phenomena such as quantum phase transitions and topological quantum order, but also represents a main obstacle to our ability to simulate such systems. We will discuss some new developments in which ideas, originating from the field of quantum information theory, led to valuable insights into the structure of entanglement in quantum spin systems and to novel powerful simulation methods

We consider the problem of bounded-error quantum state identification: given one of two known states, what is the optimal probability with which we can identify the given state, subject to our guess being correct with high probability (but we are permitted to output "don't know" instead of a guess). We prove a direct product theorem for this problem. Our proof is based on semidefinite programming duality and the technique may be of wider interest. Using this result, we present two new exponential separations in the simultaneous message passing model of communication complexity. Both are shown in the strongest possible sense: -- we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared randomness, but needs n^(1/3) communication if the parties don't share randomness, even if communication is quantum; -- we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared entanglement, but needs (almost) n^(1/3) communication if the parties share randomness but no entanglement, even if communication is quantum.

A swashbuckling tale of greed, deception, and quantum data hiding on the high seas. When we hide or encrypt information, it's probably because that information is valuable. I present a novel approach to quantum data hiding based this assumption. An entangled treasure map marks the spot where a hoard of doubloons is buried, but the sailors sharing this map want all the treasure for themselves! How should they study their map using LOCC? This simple scenario yields a surprisingly rich and counterintuitive game theoretic structure. A maximally entangled map performs no better than a separable one, leaving the treasure completely exposed. But non-maximally entangled maps can hide the information almost perfectly. Warning: contains pirates.

will discuss how to realize, by means of non-abelian quantum holonomies, a set of universal quantum gates acting on decoherence-free subspaces and subsystems. In this manner the quantum coherence stabilization virtues of decoherence-free subspaces and the fault-tolerance of all-geometric holonomic control are brought together.

Optical experiments led the way to quantum information with striking examples of Bell's inequality tests and entangled state synthesis. Early demonstrations of quantum communication proved that optics are important for quantum communication and more recent ideas about linear optic quantum computing raised hopes that this would also be true for computing. I will give an overview of the various elements that are required for optical QIP and the state-of-the-art characteristics. I will then specialize on sources of single photons and entangled photon pairs and show how they need to be adapted to the task at hand.

We show that the entropy resulting from the counting of microstates of non extremal black holes using field theory duals of string theories can be interpreted as arising from entanglement. The conditions for making such an interpretation consistent are discussed. First, we interpret the entropy (and thermodynamics) of spacetimes with non degenerate, bifurcating Killing horizons as arising from entanglement. We use a path integral method to define the Hartle-Hawking vacuum state in such spacetimes and discuss explicitly its entangled nature and its relation to the geometry. If string theory on such spacetimes has a field theory dual, then, in the low-energy, weak coupling limit, the field theory state that is dual to the Hartle-Hawking state is a thermofield double state. This allows the comparison of the entanglement entropy with the entropy of the field theory dual, and thus, with the Bekenstein-Hawking entropy of the black hole. As an example, we discuss in detail the case of the five dimensional anti-de Sitter, black hole spacetime.