Talks

Many results have been recently obtained regarding the power of hypothetical closed time-like curves (CTC’s) in quantum computation. Most of them have been derived using Deutsch’s influential model for quantum CTCs [D. Deutsch, Phys. Rev. D 44, 3197 (1991)]. Deutsch’s model demands self-consistency for the time-travelling system, but in the absence of (hypothetical) physical CTCs, it cannot be tested experimentally. In this paper we show how the one-way model of measurement-based quantum computation (MBQC) can be used to test Deutsch’s model for CTCs. Using the stabilizer formalism, we identify predictions that MBQC makes about a specific class of CTCs involving travel in time of quantum systems. Using a simple example we show that Deutsch’s formalism leads to predictions conflicting with those of the one-way model. There exists an alternative, little-discussed model for quantum time-travel due to Bennett and Schumacher (in unpublished work, see http://bit.ly/cjWUT2), which was rediscovered recently by Svetlichny [arXiv:0902.4898v1]. This model uses quantum teleportation to simulate (probabilistically) what would happen if one sends quantum states back in time. We show how the Bennett/ Schumacher/ Svetlichny (BSS) model for CTCs fits in naturally within the formalism of MBQC. We identify a class of CTC’s in this model that can be simulated deterministically using techniques associated with the stabilizer formalism. We also identify the fundamental limitation of Deutsch's model that accounts for its conflict with the predictions of MBQC and the BSS model. This work was done in collaboration with Raphael Dias da Silva and Elham Kashefi, and has appeared in preprint format (see website). Website: http://arxiv.org/abs/1003.4971

In this talk I shall describe a general formalism based on $AdS_2/CFT_1$ correspondence that allows us to systematically calculate the entropy, index and other physical observables of an extremal black hole taking into account higher derivative and quantum corrections to the action. I shall also describe precise microscopic computation of the same quantities for a class of supersymmetric extremal black holes and compare this with the prediction of $AdS_2/CFT_1$ correspondence.

In this talk I shall describe a general formalism based on $AdS_2/CFT_1$ correspondence that allows us to systematically calculate the entropy, index and other physical observables of an extremal black hole taking into account higher derivative and quantum corrections to the action. I shall also describe precise microscopic computation of the same quantities for a class of supersymmetric extremal black holes and compare this with the prediction of $AdS_2/CFT_1$ correspondence.

In this talk I shall describe a general formalism based on $AdS_2/CFT_1$ correspondence that allows us to systematically calculate the entropy, index and other physical observables of an extremal black hole taking into account higher derivative and quantum corrections to the action. I shall also describe precise microscopic computation of the same quantities for a class of supersymmetric extremal black holes and compare this with the prediction of $AdS_2/CFT_1$ correspondence.

The headline result of this talk is that, based on plausible complexity-theoretic assumptions, many properties of quantum channels are computationally hard to approximate. These hard-to-compute properties include the minimum output entropy, the 1->p norms of channels, and their "regularized" versions, such as the classical capacity. The proof of this claim has two main ingredients. First, I show how many channel problems can be fruitfully recast in the language of two-prover quantum Merlin-Arther games (which I'll define during the talk). Second, the main technical contribution is a procedure that takes two copies of a multipartite quantum state and estimates whether or not it is close to a product state. This is based on arXiv:1001.0017, which is joint work with Ashley Montanaro.

In this talk I will describe how random matrix theory and free probability theory (and in particular, results of Haagerup and Thorbjornsen) can give insight into the problem of understanding all possible eigenvalues of the output of important classes of random quantum channels. I will also describe applications to the minimum output entropy additivity problems.

In this talk we will explain how the main step technical steps in the proofs by Hastings and Hayden-Winter of the non-additivity of the minimal output von Neumann and $p$-Renyi entropy (for any $p>1$) can be reduced to a sharp version of Dvoretzky's theorem on almost spherical sections of convex bodies. This substantially simplifies their analysis, at least on the conceptual level, and provides an alternative point of view on these and related questions. Joint work with G. Aubrun and E. Werner

In 2008 Hastings reported a randomized construction of channels violating the minimum output entropy additivity conjecture. In this talk we revisit his argument, presenting a simplified proof. In particular, we do not resort to the exact probability distribution of the Schmidt coefficients of a random bipartite pure state, as in the original proof, but rather derive the necessary large deviation bounds by a concentration of measure argument. We prove non-additivity for the overwhelming majority of channels consisting of a Haar random isometry followed by partial trace over the environment, for an environment dimension much bigger than the output dimension.

Within the framework of quantum repeated interactions we investigate the large time behaviour of random quantum channel. We focus on generic quantum channels generated by unitary operators which are randomly distributed along the Haar measure. After studying the spectrum of these channels, we state a convergence result for the iterations of generic channels. This allows to define a set of random quantum states called ''asymptotic induced ensemble''.

In this talk, I describe two cases in which questions in quantum information theory have lead me to random matrices. In the first case, analyzing a protocol for quantum cryptography lead us to the following question: what is the largest eigenvalue of a sum of p random product states in (C^d)^{otimes k}, where k and p/d^k are fixed while d grows? When k=1, the Marcenko-Pastur law determines (up to small corrections) not only the largest eigenvalue ((1+sqrt{p/d^k})^2) but the smallest eigenvalue (min(0,1-sqrt{p/d^k})^2) and the spectral density in between. We use the method of moments to show that for k>1 the largest eigenvalue is still approximately (1+sqrt{p/d^k})^2 and the spectral density approaches that of the Marcenko-Pastur law, generalizing the random matrix theory result to the random tensor case. In the second case, attempting to design a quantum algorithm lead us to the following question. Consider a random matrix M in which entries in some set S are always 0 and other entries are picked i.i.d. from some distribution. What is the expected value of the condition number of this random matrix? We have shown that there are sets S such that, with high probability M is nonsingular but has a very high condition number (2^{sqrt(n)} where n is the dimension of the matrix M). The first part is a joint work with Aram Harrow and Matthew Hastings and has appeared as arxiv preprint 0910.0472.

We associate to any unoriented graph a random pure quantum state, obtained by randomly rotating a tensor product of Bell states. Marginals of such states define new ensembles of density matrices, which we study in the asymptotical regime of large Hilbert spaces. Limit eigenvalue distributions are computed, as well as average von Neumann entropies and purities. Fuss-Catalan distributions are identified as limits of the eigenvalue distributions of particular marginals. Finally, we discuss area laws for these random states. This is joint work with Benoit Collins and Karol Zyczkowski.