QIP · 2009

One of the basic problems in physics is approximating the ground state energy of a quantum many-body system. For arbitrary choice of local interactions, this problem is extremely difficult, even in one dimension where Aharonov, Gottesman, and Kempe and Irani showed that this problem is QMA-complete. However, many of the quantum ground states encountered in practice have a limited amount of entanglement. As I will explain, this makes it possible to efficiently represent the ground state of these systems on a classical computer. In the important case that the Hamiltonian has a spectral gap, I will explain a recent proof of an "area law" which bounds the entanglement entropy. This result implies that a certain promise problem for approximating the ground state energy of gapped one-dimensional Hamiltonians is in NP, while a similar problem for approximating the adiabatic evolution of such systems is in P. There are four different additivity conjectures in quantum information theory, all of which were shown to be equivalent by Shor in 2004. These include the additivity of the Holevo capacity for sending classical information over a quantum channel, and the additivity of the minimum output entropy of a quantum channel. These conjectures relate to whether or not entanglement between different inputs to a quantum channel is useful to increase classical capacity or reduce output entropy. I will present a counter-example to the minimum output entropy conjecture, which implies that all of these additivity conjectures are false. The counter-example is based on a random construction of a channel with a large environment dimension and an even larger system dimension. I will relate this channel to recent work on quantum expanders, and I will propose a slightly weaker additivity conjecture which would give us a two-letter formula for capacity of channels invariant under complex conjugation.

Communication over a noisy quantum channel introduces errors in the transmission that must be corrected. A fundamental bound on quantum error correction is the quantum capacity, which quantifies the amount of quantum data that can be sent. I will show how two quantum channels, each with a transmission capacity of zero, can have a nonzero capacity when used together. This unveils a rich structure in the theory of quantum communications, and points towards several new questions about communication and information in the physical world. This is work done jointly with Jon Yard.

We introduce a variant of Quantum Multi Prover Interactive Proofs (QMIP), where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a single prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap. The main idea is not to bound the information the provers exchange with each other, as in the classical case, but rather to prove that any "cheating" strategy employed by the provers has constant probability to diminish the entanglement between the verifier and the provers by a constant amount. Detecting such reduction gives us the soundness proof. Similar ideas and techniques may help help with other models of Quantum MIP, including the dual question, of non communicating provers with unlimited entanglement. Joint work with Michael Ben-Or and Haran Pilpel

In some of the earliest work on quantum mechanical computers, Feynman showed how to implement universal quantum computation by the dynamics of a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be a sparse matrix with all entries equal to 0 or 1, i.e., the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes

One of the basic problems in physics is approximating the ground state energy of a quantum many-body system. For arbitrary choice of local interactions, this problem is extremely difficult, even in one dimension where Aharonov, Gottesman, and Kempe and Irani showed that this problem is QMA-complete. However, many of the quantum ground states encountered in practice have a limited amount of entanglement. As I will explain, this makes it possible to efficiently represent the ground state of these systems on a classical computer. In the important case that the Hamiltonian has a spectral gap, I will explain a recent proof of an "area law" which bounds the entanglement entropy. This result implies that a certain promise problem for approximating the ground state energy of gapped one-dimensional Hamiltonians is in NP, while a similar problem for approximating the adiabatic evolution of such systems is in P.

This talk is about secret key distribution from correlations that violate Bell inequalities. A security proof can be obtained from the assumption that arbitrarily-fast signaling between different subsystems is impossible. This assumption is imposed at the level of the outcome probabilities given the choice of observables, therefore, the scheme remains secure in situations where the honest parties distrust their quantum apparatuses.