Quantum Information Theory: Present Status and Future Directions
Monday 23rd August 2004 to Friday 27th August 2004
10:10 to 11:00 
W Wootters (Williams College) Picturing qubits in phase space In this talk I present a discretephasespace description of a system of qubits, in which each phasespace axis is labeled by the elements of a finite field and the state of the system is represented by a real function on phase spacea discrete Wigner function. Each set of parallel lines in the phase space corresponds to an orthogonal basis for the state space, and bases corresponding to different sets of parallel lines are mutually unbiased. I discuss the representation of quantum gates in this framework, and the problem of recognizing entanglement 
INI 1  
11:30 to 12:20 
JI Latorre ([Barcelona]) Entanglement loss along renormalization group flows 
INI 1  
14:00 to 14:50 
J Oppenheim ([Cambridge]) Secure key from bound entanglement The general class of quantum states which are unconditionally private are introduced. This allows us to consider the production of a secure key within the same paradigm as entanglement theory by making one change  instead of distilling singlets we distill these private states. It is then shown that an arbitrarily secure key can be distilled from bound entangled states. In general the amount of distillable key is no greater than the relative entropy of entanglement. Related Links

INI 1  
15:30 to 16:20 
F Verstraete ([MPIGarching]) Quantum spin chains from the perspective of quantum information theory We study the concept of valence bond states from the perspective of entanglement theory. This leads to several generalizations with powerful applications for the simulation of quantum spin systems. In particular, we extend the powerful Density Matrix Renormalization Group (DMRG) simulation method to the cases of periodic boundary conditions, finiteT, timeevolution, and 2 dimensions. We also discuss the relationship between entanglement and correlations in those systems, leading to a natural definition of entanglement length. 
INI 1  
16:20 to 17:10 
L Vaidman ([TelAviv]) Quantum versus classical, qubits versus bits
Methods for measuring an integral of a classical field via local interaction of classical bits or local interaction of qubits passing through the field one at a time are analyzed. A quantum method, which has an exponentially better precision than any classical method we could see, is described. An alternative quantum method using only one particle is proposed.

INI 1 
09:20 to 10:10 
H Buhrman ([CWI]) Robust polynomials and quantum algorithms We define and study the complexity of robust polynomials for Boolean functions and the related faulttolerant quantum decision trees, where input bits are perturbed by noise. We show that, in contrast to the classical model of Feige et. al., every Boolean function can be computed by O(n) quantum queries even in the model with noise. This implies, for instance, the somewhat surprising result that every Boolean function has robust degree bounded by O(n). This joint work with Ilan Newman, Hein Roehrig, and Ronald de Wolf 
INI 1  
10:10 to 11:00 
J Kempe ([ParisSud]) The complexity of local Hamiltonians This is joint work with Alexei Kitaev and Oded Regev. Complexity theory formalises the notion of an _efficient_ algorithm. A major challenge for complexity theory is to understand the interrelation between classical and the newly emerging quantum complexity classes. The klocal Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It had been known that 3local Hamiltonian is QMAcomplete; whereas 1local Hamiltonian is in P, efficiently solvable and hence not believed to be QMAcomplete. The exact complexity of the 2local problem has so far been unknown. We will introduce rigorous perturbation theory techniques to complexity theory and show that 2local Hamiltonian is QMA complete. Our techniques also show that 2local _adiabatic_ computation on qubits is equivalent to standard quantum computation. We hope that our physics inspired technique might prove useful elsewhere in (quantum) computer science. We outline some open problems and future directions. Related Links

INI 1  
11:30 to 12:20 
M Mosca ([Waterloo]) Quantum algorithms and phase estimation 
INI 1  
15:30 to 16:20 
R Laflamme ([Perimeter Inst.]) NMR quantum information processing To follow 
INI 1  
18:45 to 19:30  Dinner at Wolfson Court (Residents Only) 
09:20 to 10:10 
MB Plenio ([Imperial College]) Entanglement \& area We revisit the question of the relation between entanglement, entropy, and area for harmonic lattice Hamiltonians which are the discrete version of real free scalar fields. For the cubic harmonic lattice Hamiltonian which yields the real Klein Gordon field in the continuum limit we establish a strict relationship between the surface area of a distinguished hypercube and the degree of entanglement between the hypercube and the rest of the lattice, without resorting to numerical means. We outline extensions of these results to longer ranged interactions, finite temperatures and for classical correlations in classical harmonic lattice systems. Related Links 
INI 1  
10:10 to 11:00 
N Cerf ([ULB]) Proposal for a loopholefree Bell test using homodyne detection In their seminal 1935 paper, Einstein, Podolsky, and Rosen advocated that if "local realism" is taken for granted, then quantum theory is an incomplete description of the physical world. The EPR argument gained a renewed attention in 1964 when John Bell derived his famous inequalities, which must be satisfied within the framework of any local realistic theory. The violation of Bell inequalities, predicted by quantum mechanics, has since then been observed in many experiments, thereby disproving the concept of local realism. So far, however, all these tests suffered from "loopholes" allowing a local realistic explanation of experimental observations by exploiting either the low detector efficiency or the timelike interval between the two detection events. Here, I will report on an experimentally feasible optical setup that potentially allows for a loopholefree Bell test by using highly efficient homodyne detectors. A nongaussian entangled state of two light beams is generated from a twomode squeezed vacuum by subtracting a single photon from each mode with the help of standard singlephoton detectors. A Bell violation exceeding 1% is achievable for a 6dB squeezed light source using singlephoton detectors with an efficiency as low as 10%, provided that the homodyning efficiency lies around 95%. Given the recent demonstration of photon subtraction from pulsed singlemode squeezed states, we envision that this proposal may lead to the first complete test of Bell violation in a foreseeable future. 
INI 1  
11:30 to 12:20 
P Knight ([Imperial College]) Entanglement and decoherence in coined quantum walks Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. We review the specific quantum properties of quantum walks and their sensitivity to decoherence. We then examine the entanglement properties of quantum walks in various dimensions (lines, 2D lattices and trees) using entropic characterizations generated from the subsystem density matrices of the walker positioncoin state correlations. 
INI 1 
09:20 to 10:10 
A Acin ([ICFO]) Quantum and secret correlations Quantum and secret correlations are two valuable resources in Quantum Information Theory and Cryptography, respectively. They both have the property of being monogamous: the more two parties share secret or quantum correlations, the less they are coupled to the environment. The analogies between these two resources become more evident if one compares the usual quantum (secret) correlation manipulation scenario: N parties share a quantum state rho_A1 AN (probability distribution P(A1,...,AN)) that is also entangled (correlated) to the environment (Eve). From an operational point of view, one would like to know 1) how many entangled bits (secret bits) are required for the preparation of the state (probability distribution) and 2) how many entangled bits (secret bits) can be extracted, or distilled, from the state (probability distribution). Exploiting these analogies, the following results can be proven: 1) All twoqubit entangled states allow a secure key distribution when Alice, Bob and Eve perform operations at the singlecopy level. 2) The preparation of a probability distribution requires entanglement if and only if secret bits are consumed in an alternative preparation using only classical means. This implies that all the entangled states, independently of their distillability properties, can be mapped into probability distributions containing secret correlations. 3) There exists a cryptographic analog of bound entanglement, known as bound information. As it happens for bound entanglement, bound information can be activated: the mixture of nondistillable probability distributions can lead to a distillable one. 
INI 1  
10:10 to 11:00 
HK Lo ([Toronto]) Decoy state quantum key distribution Quantum key distribution (QKD) allows two parties to communicate in absolute security based on the fundamental laws of physics. Up till now, it is widely believed that unconditionally secure QKD with the standard BennettBrassard (BB84) protocol is only possible at rather low key generation rate and short distances. Previously proposed methods (including singlephoton sources) to extend the distances of BB84 and increase key generation rate are mostly experimental and present daunting experimental challenges. Here, we present a simple theoretical idea that will achieve these goals by using only current technology. Our method is to develop substantially the decoy state idea of Hwang and combine it with standard entanglement distillation approach to security proofs. Our results show that secure QKD is possible at a key generation rate as high as $O (\eta)$ (as opposed to $O(\eta^2)$ in prior art) where $\eta$ is the overall transmission probability of the channel and fiberbased QKD can be made unconditionally secure over 100km. In summary, we can have the best of both worldsmaking the best use of our imperfect experimental apparatus and yet getting the strongest level of security unconditional security, which is the Holy Grail of quantum cryptography. Our method is, therefore, a significant step in bridging the big gap between the theory and practice of QKD. 
INI 1  
11:30 to 12:20 
N Gisin ([Geneva]) Simulation of singlet correlation without any communication, but using a weaker resource: a "nonlocal machine" The importance of quantum entanglement is by now widely appreciated as a resource for quantum information applications. A unit of entanglement has been identifies and named ebit; it consists of a pair of maximally entangled qubits, e.g. of a singlet: the same singlet that Bohm used in his version of the EPR paradox. A few years ago connection with communication complexity started to be studied, with question like how much communication is required to simulate an ebit? From Bell inequality we know that it is impossible to simulate a singlet without any communication even if one assumes that both parties share local hidden variables, or in modern terminology, share randomness. Recently, Tonner and Bacon proved that actually a single bit of communication suffice for perfect simulation. Independently from the above story, Popescu and Rochlich raised the following question: can there be correlation stronger than the quantum mechanical ones that do not allow one to signal? They answered by showing a hypothetical nonlocal machine that does not allow signaling, yet violates the CHSHbell inequality by the absolute maximal value of 4 (while quantum correlation achieve at most $2\sqrt{2}$. They concluded asking why Nature is nonlocal, but not maximally nonlocal, where the maximum would be only limited by the nosignaling constraint? It is straightforward to simulate the PR machine with a single bit of communication. Consequently, the PR nonlocal machine is a strictly weaker resource than a bit of communication. We show that singlets can be simulated using only one instance of the PR nonlocal machine. Hence, assuming that Nature is sparing with resources, one is be tempted to conclude that she is using something like the nonlocal machine. Finally, we raise the question whether correlations arising from partially entangled qubits can be simulated using only an ebit? 
INI 1  
14:00 to 14:50 
A Kent ([Cambridge]) Remarks on mistrustful quantum and relativistic cryptography I review some ideas on what cryptographic tasks might or might not be implementable with security guaranteed by special relativity and/or quantum theory. 
INI 1  
15:30 to 16:20 
S Massar ([ULB]) Provably secure experimental quantum bit string generation Coin Tossing is the problem in which two parties who do not trust each other want to generate a random coin. Quantum communication allows the parties to generate a coin with bias less than ½, which is impossible classically. However even quantum communication cannot guarantee that the bits are perfectly random. Bit string generation is the generalisation of coin tossing when the two parties want to generate a large number n of coins. We discuss the theory of quantum bit string generation and show that much better security is possible than for quantum coin tossing. We also report on an experiment in which a string of bits is generated which more random than is possible classically. 
INI 1  
16:20 to 17:10 
N Linden ([Bristol]) A new inequality for the von Neuman entropy Strong subadditivity of von Neumann entropy, proved in 1973 by Lieb and Ruskai, is a cornerstone of quantum coding theory. All other known inequalities for entropies of quantum systems may be derived from it. I will describe some work with Andreas Winter in which we prove a new inequality for the von Neumann entropy which is independent of strong subadditivity. This work sheds light on extremal types of entanglement for multiparty quantum states. 
INI 1 
09:20 to 10:10 
B Reznik ([TelAviv]) Vacuum entanglement The properties of vacuum entanglement of a free relativistic field and of a Linear Harmonicchain will be discussed. We shall also discuss a gedankenexperiment for detecting Bells inequalities violation in the vacuum, and a scheme for detecting groundstate entanglement in a linear ion trap. 
INI 1  
10:10 to 11:00 
AS Kholevo ([Steklov Maths Inst.]) Additivity problem: an overview A class of problems in quantum information theory, having simple formulation but still resisting general solution, concerns additivity properties of various quantities characterizing quantum channels, notably the "classical capacity", the "minimal output entropy" and the "entanglement of formation". All known results, including numerical work, are consistent with the conjecture that these quantities are additive with respect to tensor products of channels. A proof of this conjecture would have important consequences in quantum information theory. In particular, according to this conjecture, the classical capacity cannot be increased by using entangled inputs of the quantum channel. In this talk we review the current status of the additivity/multiplicativity problems, discuss relations between them and give a survey of relevant results and approaches. 
INI 1  
11:30 to 12:20 
S Lloyd ([MIT]) Quantum computation and quantum gravity This talk reviews known connections between quantum gravity and quantum information, including (a) entanglement and Hawking radiation, (b) teleportation and black hole evaporation, (c) bit creation during inflation, and (d) the holographic principle. After the review, I will present a theory of quantum gravity based on quantum computation that provides explicit models for all these phenomena within a framework that allows quantitative calculations. 
INI 1  
14:00 to 14:50 
A Winter ([Bristol]) Generic behaviour in quantum information theory: applications of the concentration of measure phenomenon In that branch of quantum information theory which generalises Shannon's communication theory, it is the rule (just as with Shannon) that information theoretically optimal constructions are not actually "constructive". Instead, the probabilistic method is used to show that some random way to build a code or protocol will succeed with positive probability (so that there actually exists a good code)  in fact, this probability will usually be close to 1. Thus, it is not surprising that quantitative laws of large numbers play a significant role in the theory, and in fact the most important ones are those which give exponential probability bounds on "large deviations": Cramer's and Azuma's inequality for the convergence of empirical means and martingales, as well as relatives of Talagrand's inequality have been used in classical information theory. This talk will describe the status of these tools and their applications in quantum information theory: I will show how the concentration of measure phenomenon on Euclidean spheres leads to strong statements for the unitary group, and to strong results regarding state randomisation, remote state preparation, data hiding, and information on the typical entanglement properties of random states. [Several collaborative papers with Abeyesinghe, Bennett, Hayden, Leung, Shor and Smith on quantph.] Furthermore, I will outline operator versions of Cramer's theorem [joint work with Ahlswede, IEEE IT 2002] and of (a simple variant of) Talagrand's isoperimetric inequality [work in progress], and illustrate those with some applications such as the quantum reverse Shannon theorem and a generalisation of a "local converse to the channel coding theorem" due in the classical case to Ahlswede and Dueck. 
INI 1  
15:30 to 16:20 
D Leung ([CALTECH]) Applications of randomized techniques in quantum information theory Quantum information theory is concerned with the asymptotic manipulation of quantum systems to perform useful information processing tasks. This talk will survey various communication capacities that have been proved in the past two years. Of particular focus is the usefulness of randomized techniques in these proofs. 
INI 1  
16:20 to 17:10 
V Vedral ([Imperial College]) High temperature macroscopic entanglement The main subject of my talk will be investigation of the possibility of having high temperature entanglement in the macroscopic (thermodynamical) limit. I will first introduce the notions of entanglement and classical correlations for a general state involving any number of subsystems. I will then develop the theory for calculating both classical and quantum correlations for totally symmetric pure states of any number of qubits, as well as any subset and mixture of these. These states are important as they feature in some high T superconducting models. In the second half of the talk, I will be discussing the role of entanglement in macroscopic solidstate systems providing examples from simple models such as the Ising and Heisenberg onedimensional spin chains. I will argue that these models cannot sustain high temperature entanglement entanglement only exists close to the very low (critical) temperature. Then I will look at the electron pairing of Yangs (in the Hubbard Model and related models) used in high T superconductivity. Electron pairing is described by totally symmetric states mentioned above and I plan to discuss the relationship between the existence of off diagonal long range order which ensures typical superconducting behaviour  and the existence of entanglement and classical correlations. The question of having macroscopic entanglement at high temperature is not only important practically, for information processing, but also has a fundamental significance, which I believe  may have a long term effect on fundamental physics. 
INI 1 