# Random Matrix Techniques in Quantum Information Theory

Conference Date:
Sunday, July 4, 2010 (All day) to Tuesday, July 6, 2010 (All day)
Scientific Areas:
Quantum Information

As in classical computer science randomized proofs and 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. One of the most important classes of problems in the mathematical aspects of quantum information theory is the study of data transmission through noisy quantum channels. A famous conjecture reduced the calculation of the channel capacity for classical data to the question of the additivity of minimum channel output entropy. The original conjecture was disproved by Hastings in 2008. Additivity questions are but the latest applications of random matrices in quantum information however. Others include benchmarking of experimental quantum computers as well as the design of optimal codes for numerous data transmission and cryptographic problems. The workshop will gather researchers from areas as various as quantum information theory quantum computing random matrix theory asymptotic convex analysis free probability theory and operator algebras. We believe that the recent resolution of the additivity conjecture provides an excellent opportunity to bring together for the first time specialists with widelyarying backgrounds in both physics and mathematics whose work does (or could!) lie at the intersection of quantum information and random matrices. Our goal would be to make a synthesis of the new research trends related to these problems while introducing audience of non-experts and graduate students to some of the most exciting recent multidisciplinary developments at the interface between physics and mathematics.

Andris Ambainis, University of Latvia

Fernando Brandao, Departamento de Fisica, Universidade Federal de Minas Gerais, Brazil

Benoit Collins, University of Ottawa

Bergfinnur Durhuus, University of Copenhagen

Alexander Elgart, Virginia Tech

Motohisa Fukuda, UC Davis

Aram Harrow, University of Bristol

Patrick Hayden, McGill University/Perimeter Institute

Marius Junge, University of Illinois

Chris King, Northeastern University

Debbie Leung, University of Waterloo

Ramis Movassagh, Massachusetts Institute of Technology

Ion Nechita, University of Ottawa

Alexandru Nica, University of Waterloo

Clément Pellegrini, Université de Toulouse III

Jérémie Roland, NEC Laboratories America

Mary Beth Ruskai, Tufts University

Stanislaw Szarek, Case Western Reserve University

Lorenza Viola, Darmouth College

Andreas Winter, University of Bristol

Deping Ye, University of Missouri

Karol Zyczkowski, Jagiellonian University & Polish Academy of Science

Ofer Zeitouni, University of Minnesota

Andris Ambainis, University of Latvia

Two random matrix problems inspired by quantum information

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.

Some limit theorems in operator-valued noncommutative probability

A famous result in classical probability - Hin\v{c}in's Theorem - establishes a bijection between infinitely divisible probability distributions and limits of infinitesimal triangular arrays of independent random variables. Analogues of this result have been proved by Bercovici and Pata for scalar-valued {\em free probability}. However, very little is known for the case of operator-valued distributions, when the field of scalars is replaced by a $C^*$-algebra; essentially the only result known in full generality that we are aware of is Voiculescu's operator-valued central limit theorem. In this talk we will use a recent breakthrough in the description of infinite divisibility of operator-valued distributions achieved by Popa and Vinnikov to prove a Hin\v{c}in-type theorem for operator-valued free random variables and to formulate a free - to - conditionally free Bercovici-Pata bijection. Time permitting, we will discuss in more detail relaations between the operator-valued free, Boolean and monotone central limits. This is joint work with Mihai V. Popa and Victor Vinnikov.

Fernando Brandao, Departamento de Fisica, Universidade Federal de Minas Gerais, Brazil

Hasting's counterexamples on the minimum output entropy additivity conjecture by measure concentration

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.

Benoit Collins, University of Ottawa

Random matrices and random quantum channels

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.

Bergfinnur Durhuus, University of Copenhagen

Hausdorff and spectral dimension of random graphs

We introduce a class of probability spaces whose objects are infinite graphs and whose probability distributions are obtained as limits of distributions for finite graphs. The notions of Hausdorff and spectral dimension for such ensembles are defined and some results on their value in koncrete examples, such as random trees, will be described.

Aram Harrow, University of Bristol

Minimum output entropy of quantum channels is hard to approximate

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.

Marius Junge, University of Illinois

Random techniques and Bell inequalities

In this talk we will give an overview of how different probabilistic and quantum probabilistic techniques can be used to find Bell inequalities with large violation. This will include previous result on violation for tripartite systems and more recent results with Palazuelos on probabilities for bipartite systems. Quite surprisingly the latest results are the most elementary, but lead to some rather surprsing independence of entropy and large violation.

Ramis Movassagh, MIT

Isotropic Entanglement

One of the major problems hindering progress in quantum many body systems is the inability to describe the spectrum of the Hamiltonian. The spectrum corresponds to the energy spectrum of the problem and is of out-most importance in accounting for the physical properties of the system. A perceived difficulty is the exponential growth of the Hamiltonian with the number of particles involved. Therefore, even for a modest number of particles, direct computation appears intractable.  This work offers a new method, using free probability and random matrix theory, of approximating the spectrum of generic frustrated Hamiltonians of arbitrary size with local interactions. In addition, we show a number of numerical experiments that demonstrate the accuracy of this method.

Clément Pellegrini, Université de Toulouse III

Random Quantum Repeated Interactions and Random Invariant states

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

Jérémie Roland, NEC Laboratories America

Anderson localization and adiabatic quantum optimization

Understanding NP-complete problems is a central topic in computer science. This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer's Hamiltonian.

We show that the statistics of the gaps can be analyzed in a novel way, borrowed from the study of quantum disordered systems in statistical mechanics. It turns out that due to a phenomenon similar to Anderson localization, exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. We show that this effect makes adiabatic quantum optimization fail, as the system gets trapped in one of the numerous local minima. We will also discuss recent developments including the effect of the exponential number of solutions and Hamiltonian path change.

Joint work with Boris Altshuler and Hari Krovi

Based on arXiv:0908.2782 and arXiv:0912.0746

Stanislaw Szarek, Case Western Reserve University

Hastings' additivity counterexample and a sharp version of Dvoretzky theorem.

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

Andreas Winter, University of Bristol

Approximate vs complete quantum information erasure: constructions and applications

It is a fundamental, if elementary, observation that to obliterate the quantum information in n qubits by random unitaries, an amount of randomness of at least 2n bits is required. If the randomisation condition is relaxed to perform only approximately, we obtain two answers, depending on the norm used to compare the ideal and the approximation. Using the "naive" norm brings down the cost to n bits, while under the more appropriate complete norm it is still essentially 2n.

After reviewing these facts and some constructions, we go on to explore the quantum information theoretical uses of the two notions of erasure. Most prominently, for a given quantum channel and its complementary channel, complete erasure is dual to correctability of the quantum noise; while approximate erasure is dual to the decodability of another task of quantum information, dubbed "quantum identification"

Deping Ye, University of Missouri

On the comparison of volumes of quantum states

Entangled (i.e., not separable) quantum states play fundamental roles in quantum information theory; therefore, it is important to know the size" of entanglement (and hence separability) for various measures, such as, Hilbert-Schmidt measure, Bures measure, induced measure, and $\alpha$-measure.

In this talk, I will present new comparison results of $\alpha$-measure with Bures measure and Hilbert-Schmidt measure. Employing these comparison results to the subsets of separable states and of states with positive partial transpose, we show that the probability of separability is very small, and the well-known Peres-Horodecki PPT Criterion as a tool to detect separability is imprecise for (even moderate) large dimension of Hilbert space.

This talk is based on my papers: J. Math. Phys. 50 (2009) 083502, and J. Phys. A: Math. Theor. in press.

Ofer Zeitouni, University of Minnesota

Singular values, complex eigenvalues and the single ring theorem

Limit laws and large deviations for the empirical measure of the singular values for ensembles of non-Hermitian matrices can be obtained based on explicit distributions for the eigenvalues. When considering the eigenvalues, however, the situation changes dramatically, and explicit expressions for the joint distribution of eigenvalues are not available (except in very special cases). Nevertheless, in some situations the limit of the empirical measure of eigenvalues (as a measure supported in the complex plane) can be computed, and it exhibits interesting features. I will describe some results along these line, part of a joint work with Alice Guionnet and Manjunath Krishnapur.

This workshop was co-sponsored by the Fields Institute.