Quantum Information

There are many results showing that the probability of entanglement is high for large dimensions. Recently, Arveson showed that the probability of entanglement is zero when the rank of a bipartite state is no larger than half the dimension of the smaller space. We show that that the probability of entanglement is zero when the rank of a bipartite state is no larger than half the maximum of the rank of its two reduced density matrices. Our approach is quite different from that of Arveson and uses a different measure. But both approaches show that the separable states lie in a lower dimensional manifold given a reasonable parameterization of the separable states. This is joint work with Elisabeth Werner, using on characterizations of the extreme points of qubit channels given by Ruskai, Szarek and Werner and the extreme points of entanglement breaking channels given by M. Horodecki, Shor and Ruskai.

A recent breakthrough in quantum computing has been the realization that quantum computation can proceed solely through single-qubit measurements on an appropriate quantum state - for example, the ground state of an interacting many-body system. It would be unfortunate, however, if the usefulness of a ground state for quantum computation was critically dependent on the details of the system\'s Hamiltonian; a much more powerful result would be the existence of a robust ordered phase which is characterized by the ability to perform measurement-based quantum computation (MBQC). To identify such phases, we propose to use nonlocal correlation functions that quantify the fidelity of quantum gates performed between distant qubits. We investigate a simple spin-lattice system based on the cluster-state model for MBQC, and demonstrate that it possesses a zero temperature phase transition between a disordered phase and an ordered \'cluster phase\' in which it is possible to perform a universal set of quantum gates.

This is a talk in two parts. The first part is on evolution of a system under a Hamiltonian. First, a general method for implementing evolution under a Hamiltonian using entanglement and classical communication is presented. This method improves on previous methods by requiring less entanglement and communication, as well as allowing more general Hamiltonians to be implemented. Next, a method for simulating evolution under a sparse Hamiltonian using a quantum computer is presented. When H acts on n qubits, and has at most a constant number of nonzero entries in each row/column, we may select any positive integer k such that the simulation requires O((log*n)t^(1+1/2k)) accesses to matrix entries of H. The second part of the talk is on adaptive measurements of optical phase. Standard measurement schemes, using each resource independently, lead to a phase uncertainty that scales as 1/sqrt(N). It has long been conjectured that it should be possible to achieve a precision limited only by the Heisenberg uncertainty principle, dramatically improving the scaling to 1/N. I present a Heisenberg-limited phase estimation procedure which has been demonstrated experimentally. We use multiple applications of the phase shift on unentangled single-photon states, and generalize Kitaev\\\'s phase estimation algorithm using adaptive measurement theory to achieve a standard deviation scaling at the Heisenberg limit.

We define a measure of the quantumness of correlations, based on the operative task of local broadcasting of a bipartite state. Such a task is feasible for a state if and only if it corresponds to a joint classical probability distribution, or, in other terms, it is strictly classically correlated. A gap, defined in terms of quantum mutual information, can quantify the degree of failure in fulfilling such a task, therefore providing a measure of how non-classical a given state is. We are led to consider the asymptotic average mutual information of a state, defined as the minimal per-copy mutual information between parties, when they share an infinite amount of broadcast copies of the state. We analyze the properties of such quantity, and find that it satifies many of the properties required for an entanglement measure. We show that it lies between the quantum- and the classical-conditioned versions of squashed entanglement. The non-vanishing of asymptotic average mutual information for entangled states may be interpreted as a signature of monogamy of entanglement.

I will present an efficient quantum algorithm for an additive approximation of the famous Tutte polynomial of any planar graph at any point. The Tutte polynomial captures an extremely wide range of interesting combinatorial properties of graphs, including the partition function of the q-state Potts model. This provides a new class of quantum complete problems. Our methods generalize the recent AJL algorithm for the approximation of the Jones polynomial; instead of using unitary representations, we allow non-unitarity, which seems counter intuitive in the quantum world. Significant contribution of this is a proof that non-unitary operators can be used for universal quantum computation.

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.

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 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