  
Seminar
Abstracts  
 
Below are the abstracts for some of the seminars listed on the "Seminars & Workshops" page.  
 
2000 
2001  

 
2002 
2003  
  

2001 

Mar.
29: Special Seminar Title:
Lower
bounds on quantum computing Shor gave a polynomial time quantum algorithm for factoring integers, a problem which is suspected to be very hard classically. Since most of public key cryptography is based on hardness of factoring, building a quantum computer would undercut the foundations of today's cryptography. Another major achievement is Grover's quantum algorithm which can speed up the solution of an arbitrary exhaustive search problem. Given those developments, it is very important to understand the limitation of quantum computing. This can be done in the quantum query model where we restrict the algorithm to accessing the input by queries and count the number of queries needed to solve the problem. In this talk, I will present a new `quantum adversary' method for proving lower bounds on quantum algorithms in the query model. Using this method, I will show that Grover's algorithm is optimal both for the original search problem considered by Grover and several other related problems. Besides giving better lower bounds, the new method also allows to unify a number of results that were previously shown using a variety of different techniques. 

Apr
27: IQI Seminar Title: Theory (and practice) of noiseless quantum subsystems Abstract: Host:
John Preskill 

May
4: IQI Seminar Title: Quantum computation in linear bosonic and fermionic interferometers Abstract: Host:
John Preskill Title:
Hiding
classical data in quantum states Abstract: Host:
John Preskill Title: Some results about parallel quantum computation Abstract: Host:
John Preskill 

June
1: IQI Seminar Title: Entanglement and universal quantum computation Abstract: Host:
John Preskill 


August
3: IQI Seminar Title: Generation and detection of triggered single photons Abstract: Host:
Hideo Mabuchi 
August
24: IQI Seminar Title: Dynamical
and holonomic quantum computation with quantum optical systems Abstract: Host: Hideo
Mabuchi 


October
24: IQI Seminar Sean Hallgren, Caltech 3:00 p.m., 102 Steele Title: Efficient quantum algorithms for shifted quadratic character problems Abstract: We give efficient quantum algorithms for the Shifted Legendre Symbol Problem and some variants. The problems and their algorithms are different from previous work on quantum computation in that they do not appear to fit into the framework of the Hidden Subgroup Problem. There is some evidence that this is an intractable problem classically, and a closely related problem has been proposed as a cryptographic primitive. Host: John Preskill 
October
31: IQI Seminar Daniel Gottesman, Berkeley 3:00 p.m., 102 Steele Title: Quantum digital signatures Abstract: One of the central concepts of modern cryptography is the idea of a public key protocol, in which the same public key is distributed to many people, some of whom may be untrustworthy, without compromising the security of the scheme. Public keys offer a number of advantages over private keys, which become insecure if obtained by an enemy. In particular, public keys are much easier to distribute to their intended recipients, since they do not need to be protected against enemy access. While quantum key distribution also handles this problem by allowing the users to detect eavesdropping, it cannot help two people who do not already share a small amount of private key. In addition, quantum key distribution does not obviously share another advantage of public key protocols: they can be used to perform tasks beyond the traditional domain of private key cryptography. One such task is the digital signature, which protects a signed message against forgery. Anyone who has a copy of the public key can verify the message, so the recipient of a digital signature can later prove in court that it was correctly signed, if need be. I will describe a quantum digital signature protocol which serves as a model for combining the advantages of public keys with unconditional security. The price is that the public keys must now be quantum states, which are more difficult to handle and must have limited distribution. Host: John Preskill 

November
1: Preskill group meeting Title: Finding
unknown shifts and hidden cosets: or how to fix a quantum hubble space
telescope 
November
7: IQI Seminar Title: Quantum
communication complexity: some recent results Host: John
Preskill 
Title: Playing
games against theories: the statistical strength of arguments against
locality Host: John
Preskill 
November
21: Mathematical Physics Seminar Title:
Capacity of noisy quantum channels This talk
will begin with a gentle introduction to the different types of channel
capacity possible in quantum situations and the mathematical model for
noise. It will emphasize a view in which states are represented by points
on the Bloch sphere, and the noise If time
permits, recent progress on some open questions regarding the additivity
of product channels will be discussed, along with related question on
the additivity of maximal l_p norms. 
November
27: IQI Seminar Title: Generating
quantum states and quantum communication complexity We will discuss the communication complexity of the first problem and then show two implications of it for the second problem. The first is an example where quantum protocols can solve a certain problem (sampling disjoint subsets) with exponentially less communication than classical protocols. The second is proving lower bounds on quantum communication complexity of computing a function by proving lower bounds on the amount of communication needed to approximate a bipartite quantum state. In particular, this gives a simple proof of recent lower bounds on quantum communication complexity by Klauck (FOCS'01). The first result appeared in A. Ambainis, L. Schulman, A. TaShma, U. Vazirani, A. Wigderson. Quantum communication complexity of sampling. FOCS'98. The second result is new. Host: Leonard Schulman 
November
29: IQI Seminar


December
18 : IQI Seminar Title: Variational
principles of physics from the point of view of inductive inference 
2002


January
15: IQI Seminar Title: Distinguishing
separable and entangled states 
January
22 : IQI Seminar Title: Distillability
and Bell inequalities in N qubit systems

January
29 : IQI Seminar Title: How
much information is obtained by a quantum measurement? 
February 5 : IQI Seminar Alexei Kitaev, Caltech 3:00 p.m., 74 Jorgensen Title: Anyons
for quantum computation With less
trivial nonAbelian anyons, a degenerate state occurs when several particles
are positioned on the plane far apart from each other. This provides an
exciting possiblility of decoherenceprotected quantum memory. Readout
is performed by fusing two particles and detecting whether they annihilate
or not. (One can even compute with certain types of anyons by simply moving
them around. Such computation is faulttolerant due to its topological
nature). Host: John
Preskill 
February
12: IQI Seminar Dorit Aharonov, Hebrew University 3:00 p.m., 74 Jorgensen Title: How to generate complicated quantum superpositions with classical Markov chains Abstract: Better understanding of what quantum superpositions can or cannot be generated efficiently seems to be a crucial step toward designing new quantum algorithms. This is illustrated by the famous Graph isomorphism (GI) problem which can be reduced to the problem of state generation. In this talk I will discuss a new method for generating complicated quantum states which can be applied to a number of interesting cases of combinatorial flavor (though not for the state required for GI). The method builds upon classical Markov chains adapted to the setting of adiabatic computation. On the way, we will understand interesting connections between Markov chains and Hamiltonians. To warm
up, you can try thinking of the following mind boggling problem: 
February
14: IQI Seminar Alexei Kitaev, Caltech 4:00 p.m., 102 Steele Title: Quantum interactive proofs Abstract: An interactive proof is a game between two players in which they exchange a certain number of messages. One player, called the prover, is allpowerful, whereas his opponent, the verifier, performs a polynomial computation according to a given protocol. The outcome of the game is decided by the verifier (according to the protocol). I will consider a quantum analog of such games. It will be shown that the version of the game with twosided error (for prover's probability to win) is equivalent a game with onesided error. Any protocol with a polynomial number of messages can be simulated by a protocol with just 3 messages. The class QIP of problems that are reducible to such games lies between PSPACE and EXP. Host: Leonard Schulman 
February
19: IQI Seminar Daniel Terno, Technion, Israel Institute of Technology 3:00 p.m., 74 Jorgensen Title: Quantum information and relativity theory Abstract: Quantum information theory results from the union of ordinary information theory with quantum mechanics. Usually the physical systems that are analyzed by this theory are described by nonrelativistic quantum mechanics. Relativity theory is involved only in terms of the limits it imposes, and is viewed as something that one should peacefully coexist with. However, there is nothing in the mathematical structure of quantum information theory that prevents its application to relativistic systems, nonabelean gauge theories and even field theories in curved spacetimes. Merging of relativity and quantum information requires reassessing some basic tools, but it also has some fascinating applications. Host: John Preskill 
February
26: IQI Seminar Luming Duan, Caltech 3:00 p.m., 74 Jorgensen Title: Implementation of quantum repeaters and longdistance quantum communication through laser manipulation of atomic ensembles Abstract: Quantum communication holds the promise for absolutely secure transmission of secret messages and faithful transfer of unknown quantum states. Photonic channels appear to be very attractive for physical implementation of quantum communication. However, due to losses and decoherence in the channel, the communication fidelity decreases exponentially with the channel length. We describe a scheme that allows one to implement robust quantum communication over long lossy channels. The scheme involves laser manipulation of atomic ensembles, beam splitters, and singlephoton detectors with moderate efficiencies, and therefore fits well the status of the current experimental technology. We show that the communication efficiency scales polynomially with the channel length thereby facilitating scalability to very long distances. Host: John Preskill 
March 12 : APh Seminar Eugenio Del Re, University of L'Aquila 1:30 p.m., 139 Moore Title: Unconventional nonlinearity in optical quantum information technology Abstract: The unique qualities that characterize quantum information technology, and render it a fundamental objective for applications, appear distinctively tied to phenomena whose signature lies in their intrinsic nonlinear character. The abandonment of linear single particle processes, in striking contrast to a formalistic view of quantum physics, is imposed whenever a useful quantum information component is designed. Possibly selfevident in atom based schemes, the role of nonlinearity is more subtle and essential in the effort aimed at using optical technology to create robust and feasible quantum devices. This is in sharp contrast to a general effort aimed at realizing basic functions, such as quantum teleportation and conditional gates, with wholly linear systems. This altogether erroneous strategy rests on the formal analogy between a modal description of single particles and nonlocal entanglement, while no entanglement can characterize a single photon. Furthermore, in efforts where nonlinearity and multiparticle processes are correctly implemented, the devices simply cannot work, this being connected to a presumed, but unfounded, restriction of nonlinear processes to a limited number of optical modes. In discussing these issues, we formulate a general picture which can possibly bring to the important goal of achieving a concrete implementation of a useful optical quantum device, such as a conditional gate or teleporter, a picture in which nonlinearity in highly unconventional conditions plays a fundamental role. 
March
12: IQI Seminar 
April 9: IQI Seminar Andrew Landahl, Caltech 3:00 p.m., 74 Jorgensen Title: Quantum search by measurement Abstract: We propose a quantum algorithm for solving combinatorial search problems that uses only a sequence of measurements. The algorithm is similar in spirit to quantum computation by adiabatic evolution, in that the goal is to remain in the ground state of a timevarying Hamiltonian. Indeed, we show that the running times of the two algorithms are closely related. We also show how to achieve the quadratic speedup for Grover's unstructured search problem with only two measurements. Finally, we discuss some similarities and differences between the adiabatic and measurement algorithms. l 
April
16: IQI Seminar Oded Regev, Institute for Advanced Study, Princeton 3:00 p.m., 74 Jorgensen Title: Quantum computation and lattice problem Abstract: We present the first explicit connection between quantum computation and lattice problems. Namely, we show an algorithm that solves the $\tilde{\Theta}(n^3)$uniqueSVP under the assumption that a certain quantum problem has a solution. Moreover, using quantum reductions, we prove an average case to worst connection which is better than the known results. 
April
23: IQI Seminar Patrick Hayden, Caltech 3:00 p.m., 74 Jorgensen Title: Trading quantum and classical resources in data compression Abstract: Schumacher's quantum source coding theorem states that the optimal rate of compression for a source of quantum states is given by the von Neumann entropy of the source's average density operator. In this seminar, I'll present a refinement of Schumacher's theorem that accounts separately for the quantum and classical resources consumed. In particular, a simple formula can be used to calculate the minimal quantum resource at a given classical bit rate, both when the compressor is given the identity of the input states as classical information and when she hasn't. (The answers, as it turns out, are strikingly different.) Among the applications of the result are a solution to the optimal remote state preparation problem and new results on the tradeoff between information gain and state disturbance in quantum measurement. I'll end by describing a probabilityfree version of the compression theorem that can be interpreted as an answer to the question: "How many classical bits does a qubit cost?" Joint work
with Richard Jozsa and Andreas Winter. 
April
30: IQI Seminar Greg Kuperberg, UC Davis 3:00 p.m., 74 Jorgensen Title: A tracial quantum central limit theorem Abstract: Many traditional results in probability theory take fresh meaning in quantum probability theory, either as more difficult results, or falsehoods, or open research problems. One example is the central limit theorem. I will discuss a new central limit theorem in quantum probability theory. It has the same conclusion as the classical central limit theorem, but it has more content in the multivariate case. It arose as a conjecture in connection with a classical probability theory question, namely Johansson's theorem on the distribution of the shape of a random word in a fixed alphabet as its length goes to infinity. Reference: arXiv:mathph/0202035 Host: John Preskill 

May
14: IQI Seminar Debbie Leung, IBM Watson Research Center 3:00 p.m., 74 Jorgensen Title: Quantum computation by measurements (only) Abstract: We derive from teleportation a useful technique to perform unitary gates by measuring part of a larger Hilbert space. This technique is useful in many areas, including fault tolerant quantum gate construction and a measurement model of quantum computation. We will focus on the second application, and derive very simple sets of measurements that allow universal quantum computation. Host: John Preskill 
May
24: IQI Seminar Ignacio Cirac, Max Planck Institute for Quantum Optics, Germany 3:00 p.m., 74 Jorgensen Title: Gaussian maps: characterization and applications Abstract: Gaussian states may play an important role in the field of quantum information, as recent experiments have demostrated. In the case of optical systems, these states can be created, manipulated, and detected using current technology (beam splitters, squeezers, homodyne detection, etc). All these devices correspond to Gaussian maps; that is, they transform Gaussian states into Gaussian states. It is not know, however, whether they can implement all transformations with such a property or not. In fact, only trace preserving Gaussina transformations have been properly mathematically characterized [1]. In this talk I will report on a recent work [2] in which we have characterized all Gaussian transformations and showed that all of them can be implemented with current technology. In the case of multipartite systems we have also determined which Gaussian ransformations can be implemented locally with the help of classical communications. As an application, we have shown that Gaussian states cannot be distilled using Gaussian transformations, which have strong implications in the utility of these states for long distance quantum communication. Finally, I will mention other results regarding Gaussian positive (but not completely positive) transformations. [1] B. Demoen,
P. VAnheuverzwijn, and Verbeure, Lett. Math. Phys. 2, 161 (1977). 

June
4: IQI Seminar Jonathan Dowling, JPL 3:00 p.m., 74 Jorgensen Title: Projective Measurements and Linear Optics: For Fun and Profit Abstract: Heisenberglimited measurement protocols can be used to gain an increase in measurement precision over classical protocols. Such measurements can be implemented using, e.g., optical MachZehnder interferometers and Ramsey spectroscopes. We address the formal equivalence between the MachZehnder interferometer, the Ramsey spectroscope, and the discrete Fourier transform. Based on this equivalence we introduce the quantum "Rosetta stone''. Large photonnumber path entanglement is an important resource for Heisenberglimited measurement protocols. We present a general constructive protocol to create any large photon number pathentangled state based on the conditional detection of single photons. The influence of imperfect detectors is considered and an asymptotic scaling law is derived. Another
important application of projective measurements in linear optics is the
interferometer that signals the presence of a single photon in a particular
input state (c_00> + c_11> + c_22>) without destroying it.
This quantum nondemolition device can be used to create practical, efficient,
quantum repeaters, Host: John
Preskill 
June
11: IQI Seminar Cristopher Moore, University of New Mexico and Alexander Russell, University of Connecticut 3:00 p.m., 74 Jorgensen Title: Quantum Walks on the Hypercube Abstract: So far almost all known quantum algorithms fall into two families, generalizations of Shor's factoring and of Grover's search. Given that for many classical problems (such as Satisfiability and Permanent) the best known algorithms are based on a classical random walk, it makes sense to look at quantum walks too  especially since on some graphs (like the line or cycle) it is known that quantum walks mix quadratically faster than their classical cousins. Thus quantum walks are a potential third family of quantum algorithms which may outperform classical computers. In this
paper we will introduce the basic ideas of quantum walks and mixing times,
and will present recent results on the ndimensional hypercube. We show
that this walk is very close to uniform after (pi/4) n steps, even though
this is less than the diameter of the graph. We will discuss possible
quantum algorithms for the Knapsack problem, and open Host: Leonard Schulman 
June
18: IQI Seminar Frank Verstraete, KU Leuven, Belgium 3:00 p.m., 74 Jorgensen Title: Quantum steering Abstract: In response to the famous paper of EinsteinPodolskyRosen about quantum nonlocality, Schrodinger gave a rigorous description of how measurements performed on one part of a pure entangled state affect the other part. His major finding was that "all conceivable decompositions of the (local density operator) of the second system are just realized by all the possible measuring programmes that can be carried out on the first one" (the same observation was done more then 50 years later by HughstonJozsaWootters). Therefore Schrodinger coined the term "quantum steering", as the first observer can (probabilistically) steer the second system in a particular direction. Although Schrodinger found his onclusion "repugnant to some physicists including the author", experiments have proven the validity of his arguments. In this seminar, it will be shown how to generalize the results of quantum steering to the case where both parties share a mixed state, and we will discuss its relevance in the field of quantum information theory. Host: John
Preskill 

July
16: IQI Seminar Masato Koashi, SOKEN, School of Advanced Sciences, Japan 3:00 p.m., 74 Jorgensen Title: What is possible without disturbing partially known quantum states? Abstract: Quantum mechanics pose fundamental restrictions when one reads out information from a quantum system. The most basic rule is well knownif one reads out information from a quantum system in an unknown initial state, the quantum state of the system will change. If the initial state is partially known, some operations can be done without introducing any disturbance on the original quantum system. One of the fundamental questions here is the following: What kind of information can be extracted, and what cannot be, without changing the state? This problem is related to quantum cryptography as well as the physical feasibility of cloning (making a copy of the original) and imprinting (catching a trail without affecting theoriginal) of partially known quantum states. We present a principle that gives a definite distinction between the operations that preserve the states of the system and those that disturb the states. The principle is derived by alternately applying a fundamental property of classical signals and a fundamental property of quantum ones. The principle can be cast into a simple form by using a decomposition of the relevant Hilbert space, which is uniquely determined by the set of possible states. The decomposition implies the classification of the degrees of freedom of the system into three parts depending on how they store the information on the initially chosen state: one storing it classically, one storing it nonclassically, and the other one storing no information. Then the principle states that the nonclassical part is inaccessible and the classical part is readonly if we are to preserve the state of the system. The principle
can also be applied to problems of data compression and teleportation,
in which the input state is almost faithfully reproduced in the output.
For a rather general source including mixed states, the blind optimal
compression rates for various scenarios Host: John
Preskill 
July
30: IQI Seminar Peter Stelmachovic, Slovak Academy of Sciences, Slovakia 3:00 p.m., 74 Jorgensen Title: Local operations, subspaces and a measure of entanglement Abstract: In the course of the development of the Quantum Information Theory it turned out that the entanglement (pure quantum correlations) is an essential ingredient in many protocols which have some advantage in comparison with their classical analogies. In order to quantify resources necessary to perform a certain task we need a measure for classical as well as quantum resources. Thus a quest for a measure of entanglement began. Undoubtedly, entanglement as well as a measure of entanglement are interesting not only from the point of view of the computation but also from the point of view of the interpretation of quantum mechanics, phase transitions etc. The list of various proposals for a such measure is rather extensive but so far no one has introduced a measure that is universal, in the sense of applicability to any possible system, as well as computationaly reasonable. However, does such measure exist at all? I show you that the entanglement between two arbitrary subsystems of a given system in a pure state can be completely expressed with help of the entanglement shared between just twodimensional subspaces of the Hilbert spaces corresponding to the two subsystems. Furthermore, I extend the definition for mixed states and obtain a lower bound of the entanglement of formation and a measure of distillable entanglement. The measure constructed is universal and "computational'' and reproduces all results so far which means that in the case of pure states and two twodimensional systems it is a measure of entanglement. Host:
John Preskill 


September
24: IQI Seminar Allen Knutson, Berkeley 2:00 p.m., 74 Jorgensen **note time change** Title: Constraining spectra with puzzles Abstract: Given two Hermitian matrices with known eigenvalues, what are the possibilities for the spectrum of the sum? For example, the largest eigenvalue of the sum is easily seen to be at most the sum of the two largest eigenvalues individually. It turns out that all of the constraints are linear inequalities, and we will give a complete list in terms of "puzzles''. There is an analogous question for the product of two unitary matrices, which contains the Hermitian question as one "corner''. We will state a conjectural puzzle answer to this too, so far exhaustively checked up to 12x12 matrices. This work
is joint with Terry Tao of UCLA. 
September
27: IQI Special Seminar
*Friday* 

October
8: IQI Seminar Geza Giedke, Max Planck Institute for Quantum Optics, Germany 3:00 p.m., 74 Jorgensen Title: Entanglement generation and Hamiltonian simulation in continuous variable systems Abstract: Several recent experiments have demonstrated the promise of atomic ensembles for quantum teleportation and quantum memory. In these cases the collective internal state of the atoms is well described by continuous variables $X_a, P_a$ and the interaction with the optical field by a quadratic Hamiltonian $X_aX_l$. We show how this interaction can be used optimally to create entanglement and spin squeezing and derive conditions for the efficient simulation of quadratic Hamiltonians and the engineering of all Gaussian operations. Host: John Preskill 
October
15: Physics Graduate Student Seminar Ben Toner, Caltech 5:00 p.m., 107 Downs Title: Bell tolls: measuring the communication cost of quantum correlations Abstract: Bell's theorem states that the behavior of entangled quantum systems cannot be modeled by any classical local hidden variables theory. Simulation is possible, however, if we augment the local hidden variables with a classical communication channel between separate parties. But how much communication is required to reproduce quantum correlations? I answer this question for the case of projective measurements on an entangled Bell pair state, for which the communication cost, or "Bell toll," is just a single bit of communication. This sharpens Bell's theorem for Bell pairs and leads to a new equivalence between quantum and classical resources: "correlations on a Bell pair'' = "shared randomness'' + "one bit of communication.'' 
October
16: IQI Seminar **Wednesday** Eric Rains, AT&T LabsResearch 3:00 p.m., 74 Jorgensen Title: A semidefinite program for distillable entanglement Abstract: We consider a refinement of distillable entanglement: for a given state $\rho$ (or $n$ copies of such a state), and a given output dimension $K$, what is the greatest fidelity with which $\rho$ can be converted to a maximally entangled state of dimension $K$? In the case of p.p.t. (positive partial transpose) operations, this fidelity of distillation can be expressed as the solution to a certain semidefinite program. The theory of semidefinite programming thus leads to a number of interesting consequences; moreover, in particularly symmetric cases (e.g., multiple copies of isotropic or Werner states), the semidefinite program reduces to a linear program, and is therefore particularly tractable. In the case of antisymmetric Werner states, we can explicitly solve the linear program, and thus obtain the p.p.t. distillable entanglement of these states. Host: John Preskill 
October
22: IQI Seminar We also
propose an entanglement concentration scheme which uses only the effects
of quantum statistics of indistinguishable particles. This establishes
the fact that useful quantum information processing can be accomplished
by particle statistics alone. Host: John Preskill

October
29: IQI Seminar Host: John Preskill 

November
5: IQI Seminar John Watrous, University of Calgary 3:00 p.m., 74 Jorgensen Title: Generalizations of Tsirelson's Inequality Abstract: In this talk I will discuss twoplayer cooperative games of incomplete information, which provide a framework in which various aspects of nonlocality can be investigated. These games are also interesting since they arise in the study of multiprover interactive proof systems. Several examples of games are known for which entanglement allows the players to win with probability higher than is possible with a classical strategy. An important task for the study of multiprover interactive proof systems is to prove good upper bounds on the success probabilities of quantum strategies for various games. These upper bounds may be viewed as generalizations of Tsirelson's Inequality, which bounds the extent to which entanglement allows the CHSH Inequality to be violated. I will present some examples of such generalizations of Tsirelson's Inequality, and discuss other aspects and open questions concerning quantum strategies for twoplayer cooperative games. Host: John Preskill 
November
12: IQI Seminar Howard Barnum, LANL 3:00 p.m., 74 Jorgensen Title: Generalizations of Entanglement to Lie groups and convex cones Abstract: Unentangled pure states on a bipartite system are exactly the coherent states with respect to the group of local transformations. What aspects of the study of entanglement are applicable to generalized coherent states? Conversely, what can be learned about entanglement from the wellstudied theory of coherent states? With these questions in mind, we characterize unentangled pure states as extremal states when considered as linear functionals on the local Lie algebra. As a result, a relativized notion of purity emerges, showing that there is a close relationship between purity, coherence and (non)entanglement. To a large extent, these concepts can be defined and studied in the even more general setting of convex cones of states. Based on the idea that entanglement is relative, we suggest considering these notions in the context of partially ordered families of Lie algebras or convex cones, such as those that arise naturally for multipartite systems. The study of entanglement includes notions of local operations and, for informationtheoretic purposes, entanglement measures and ways of scaling systems to enable asymptotic developments. We propose ways in which these may be generalized to the Liealgebraic setting, and to a lesser extent to the convexcones setting. One of our original motivations for this program is to understand the role of entanglementlike concepts in condensed matter. We discuss how our work provides tools for analyzing the correlations involved in quantum phase transitions and other aspects of condensedmatter systems. Host: John Preskill 
November
19: IQI Seminar Adrian Kent, University of Cambridge 3:00 p.m., 74 Jorgensen Title: Quantum and relativistic Bit Commitment Abstract: Bit Commitment is a simple classical cryptographic primitive which turns out not to be so simple in the quantum world. One source of confusion is that there are at least three different possible definitions of quantum bit commitment, each with some motivation. I review here the state of our (or at least my) current understanding of what is and is not possible in the direction of bit commitment secure against quantum attacks, focussing in particular on cheatsensitive bit commitment protocols and on protocols based on relativity. Host: John Preskill 
November
26: IQI Seminar Daniel Gottesman, Berkeley 3:00 p.m., 74 Jorgensen Title: Quantum authentication and uncloneable encryption Abstract: Suppose someone sends you a quantum state. How can you tell if the state has been tampered with en route? This task is called "authentication". There are good solutions known for classical information; I will describe how to do it for quantum information. There is a substantial difference between authentication for classical and quantum information: while classical authentication can be done by just appending a tag to the original message, quantum authentication requires you to encrypt the quantum state as well. One application of quantum authentication is to send unclonable encrypted *classical* messages: an eavesdropper not only cannot learn the message, but she cannot even copy it to study later without revealing her presence. Host: John Preskill 

December
3: IQI Seminar Viv Kendon, Imperial College, UK 3:00 p.m., 74 Jorgensen Title: Is Decoherence useful in quantum walks? Abstract: Quantum walks have been studied recently in the quantum information community because of the possibility of developing algorithms that use them to obtain a speed up over analogous classical algorithms. I will talk about how decoherence affects discrete (in space and time) quantum walks. Like any quantum process, they are highly sensitive to decoherence, however, the effect of a small amount of decoherence is to enhance the properties of the quantum walk that are interesting for the development of quantum algorithms. Specifically, with the right amount of the right sort of decoherence, one can obtain a highly uniform distribution on the line, a very fast mixing time on the cycle, and more reliable hitting times across the hypercube. Host: John Preskill 
December
10: IQI Seminar Robert Raussendorf, LudwigMaximilians University Munich 3:00 p.m., 74 Jorgensen Title: Computational model underlying the oneway quantum computer Abstract: We have demonstrated that a class of entangled multiparticle states, the cluster states, can serve as oneway quantum computers (QCc). The QCc is a scheme of universal quantum computation that consists only of onequbit measurements on the cluster state, performed in a certain temporal order and appropriately chosen bases. The measurement outcomes are individually random but correlated. Therefore meaningful quantities can be extracted from them. The computational model underlying the QCc is different from the network model of quantum computation in which a set of qubits, the quantum register, is usually regarded as the carrier of information. The information processed with the QCc are the measurement outcomes and thus for the QCc the algorithmic information is classical. The QCc is nevertheless quantum mechanical as it uses a highly entangled cluster state as the central physical resource. For the QCc the physics part and the logic part of quantum computation are clearly separated. Much of the network terminology is abandoned since in case of the QCc no proper meaning can be assigned to these constructs. The QCc has no quantum input, no quantum output, no quantum register and it does not consist of quantum gates. In the first part of the talk, I will very briefly discuss universality of the QCc. To demonstrate universality it is shown that a QCc can efficiently simulate any quantum logic network. Second, I will give reasons why the network model is not adequate to describe the QCc in every respect. These observations led us to replace the network model as an explanation of how the QCc works by the computational model described in the third part of my talk. Host: John Preskill 
2003


January
7: IQI Seminar Jens Eisert, Imperial College, UK 3:00 p.m., 74 Jorgensen Title: The story of the preparation of entangled Gaussian states Abstract: Quantum information over socalled continuous variables offers a promising alternative to its finitedimensional counterpart: teleportation with continuous variables has been performed experimentally, the generation of Gaussian entangled states has been discussed theoretically and experimentally realised, and several cryptographic schemes have been introduced. In this talk I present techniques that help to assess what transformations are possible in such continuousvariable systems with realistic means. The main part of the talk will be concerned with Gaussian operations, which correspond to those operations that can be implemented by means of optical elements such as beam splitters, phase shifts and squeezers, together with homodyne detection. Of central interest will be the question whether Gaussian states can be prepared even over large distances. Surprisingly, it turns out that Gaussian states can not be distilled with Gaussian operations. One may be tempted to think that this observation renders the preparation and distribution of highly entangled Gaussian states impossible. In the last part of the talk, however, I will present strategies that circumvene this difficulty with feasible means in optical systems. 
January
13: IQI Special Seminar **Monday** Michael Freedman, Microsoft Research 1:30 p.m., 139 Moore Title: 2D lattice models leading to "designer anyons" Abstract: Simple local Hamiltonians produce degenerate ground space manifolds (gsm) which encode the topology of imbedded loops on a surface. We will describe some such models H and see how they lead to a study of TemperleyLieb categories (TLC). There is a complete mathematical classification of the anyonic systems ( = TQFTs) which can arise as a "quotient" of a TLC. In some cases instability of H suggests that these quotient TQFTs would be the better candidate to describe the gsm of a physical system with effective Hamiltonian approximately = H. Such physical systems would be central charge = 0 anyonic systems and lie in a family which begins: Z2gauge theory, Pfaffian phase, a universal system for quantum computation, ... . For more information see the posting: "A magnetic model with a possible ChernSimons phase on quantph", author: Freedman. 
January
14: IQI Seminar Aram Harrow 3:00 p.m., 74 Jorgensen Title: Gentle tomography and universal quantum data compression Abstract: I will discuss some new twists of two old problems in quantum information theory. Quantum state tomography is the task of estimating a quantum state when we are given many copies of it. A useful variant is gentle tomography, which attempts to estimate the state without causing very much damage to the copies that we are given. The other issue I will discuss is quantum data compression. Using gentle tomography, I will describe a simple algorithm for quantum data compression that is efficient (running time polynomial in the length of the input) and universal (the algorithm does not rely on knowledge of the source being compressed). This is joint work with Seth Lloyd and Charlie Bennett. 
January
21: IQI Seminar Debbie Leung 3:00 p.m., 74 Jorgensen Title: Remote state preparation Abstract: Remote state preparation is a task that achieves quantum communication using entanglement and classical communication. It differs from teleportation in that the sender is given an extra resource: the classical description of the state to be transmitted. In the talk,
we first review how this extra resource enables the tradeoff between the
required amount of entanglement and classical communication. Then, we
focus on protocols that use no back communication. We discuss protocols
that consume only half of the classical communication required in teleportation.
Finally, we establish a onetoone correspondence between a subclass of
remote state preparation protocols to private Joint work
with C. Bennett, P. Hayden, P. Shor, and A. Winter. 
January
28: IQI Seminar Sougato Bose, Caltech 3:00 p.m., 74 Jorgensen Title: Qubit assisted probing of microcoherences in macroscopic systems Abstract: I will describe a general scheme through which the coherence between microscopically distinct states of a macroscopic object can be probed. The system consists of a qubit coupled to a harmonic oscillator measuring apparatus. Parameter domains for some potentially feasible implementations will be described. As a second part of the talk, I will describe interfrometric ways to prepare internal degrees of identical objects in entangled states, and how it might help to explore the loss of the ability of identical objects to behave indistinguishably as they are made more macroscopic. (The second part of the talk is based on work done in collaboration with D. Home). 

February
4: IQI Seminar 
February
11: IQI Seminar Jonathan Oppenheim, The Hebrew University 3:00 p.m., 74 Jorgensen Title: An introduction to Information Space Abstract: The interplay between two basic quantities  quantum communication and local information  is investigated. The former resource is closely related to entanglement, and the later resource is related to the local properties of the quantum information. The two resources, treated like phase variables, form "Information Space". These variables can even be considered to be complementary, in the sense that using one resource destroys the other. Here we
also consider both formation and distillation processes, and plot them
in Information Space. The resulting diagrams allow us to classify states.
Finally it is shown that we can observe phaselike transitions when correlations
become classical. 
February
18: IQI Seminar Michael Keyl, TUBraunschweig 3:00 p.m., 74 Jorgensen Title: Estimating quantum states with covariant observables Abstract: In [PRA 64 (2001) 052311] a measurement scheme was proposed, which operates on N systems, all prepared according to the same density operator \rho, and which approximately yields the spectrum of \rho. In this talk I will show how this scheme can be generalized to get an estimation strategy for the full density matrix. The construction uses observables which are covariant with respect to unitary transformations of the input state \rho. I will analyze the large deviation behavior of the estimators (i.e. the decay of error probabilities as N goes to infinity) and ask whether (and in which sense) the scheme is optimal. 
February
25: IQI Seminar Dirk Schlingemann, TUBraunschweig 3:00 p.m., 74 Jorgensen Title: Infinitely entangled states Abstract: For states in infinite dimensional Hilbert spaces entanglement quantities like the entanglement of distillation can become infinite. This leads naturally to the question, whether one system in such an infinitely entangled state can serve as a resource for tasks like the teleportation of arbitrarily many qubits. We show that appropriate states cannot be obtained by density operators in an infinite dimensional Hilbert space. However, using techniques for the description of infinitely many degrees of freedom from field theory and statistical mechanics, such states can nevertheless be constructed rigorously. We explore two related possibilities, namely an extended notion of algebras of observables, and the use of singular states on the algebra of bounded operators. As applications we construct the essentially unique infinite analogue of maximally entangled states, and the singular state used heuristically in the fundamental paper of Einstein, Rosen and Podolsky. 

March
11 : IQI Seminar Michael Westmoreland, Denison University 3:00 p.m., 74 Jorgensen Title: Is the Holevo Capacity Additive? Abstract: We review the properties of ensembles that maximize the classical capacity of a quantum channel (Holevo Capacity). We discuss the issue of additivity: Is the capacity of a product channel the sum of capacities of the component channels or does entanglement increase the capacity of the product channel? We discuss the cases where the answer is known. We show the connection between this question of additivity and other additivity issues in quantum information theory such as the additivity of minimum output entropy and the additivity of the entanglement of formation. 
March
18: IQI Seminar JM Geremia, Caltech 3:00 p.m., 74 Jorgensen Title: Entanglement and dynamics in symmetric spin systems Abstract: We investigate manyparticle entanglement in symmetric spin 1/2 systems paying particular attention to both the microscopic structure of the entanglement and its robustness to entanglementdamaging processes. In order to gain a better physical picture of manyparticle quantum correlations, we develop a systematic approach for computing bipartite entanglement measures for many different partitions of the initial symmetric spin state. By comparing measures such as the entanglement entropy, entanglement of formation, and logarithmic negativity across all size scales, we are able to reconstruct a detailed picture of the full manyparticle entanglement. Additionally, by repeating our analysis after removing (tracing) particles from the spin system, it is possible to quantify the robustness of the entanglement to particle loss. By exploiting computationally attractive features of symmetric states, we are able to compute entanglement measures for systems with 10^3 particles without any explicit asymptotic approximations. Our analysis provides useful scaling rules for dynamically generated entangled states (such as spinsqueezed states). Finally, we connect our analysis to our ongoing experiments involving a symmetric ensemble of laser cooled Cs atoms. 
March
2021: Communications EE Tutorial Alexander Barg, Harvard University 10:00 a.m.12:00 p.m., 080 Moore Title: Tutorial on quantum error correction Quantum error correction is a new exciting subject at the interface of computer science and coding theory. The origins of the problem lie in the area of quantum computations which are performed on a hypothetical device called a quantum computer. Quantum computers operate with states of quantum systems which encode instances of a search problem. A huge advantage of quantum computation over classical computation is an ability to operate on state superpositions, effectively performing actions on all instances of the problem at a time. An obstacle in the way of implementing quantum algorithms is decoherence errors which can alter the amplitudes and/or phases of the states. It is at this point that quantum error correction comes to rescue, providing a mechanism of recovering the original states from errors. We will begin with recalling classical communication channels and their capacity and outlining the range of problems addressed by classical coding theory. In the quantum world the notion of a bit is replaced by a twostate quantum system, or qubit. We discuss a model of multibit quantum systems and basic operations performed on them. The next part concerns decoherence errors. We discuss what kind of errors can occur to the states and what it means to correct them. Since errors can be continuous, the notion of error bases emerges naturally. Once we know how to correct errors from the basis, we can correct arbitrary unitary errors. This also takes us naturally to the concept of a quantum code, its "length", dimension and "minimum distance". In the final
part our goal will be to define a subclass of quantum errorcorrecting
codes, the socalled stabilizer or symplectic codes. A stabilizer code
Q is constructed from a pair of classical codes C<C' over >GF(4)
whose weight enumerators correspond to the weight enumerators of Q. Bio: 
March
27: IQI Group Meeting 

April
1: IQI Seminar Pawel Wocjan, University of Karlsruhe 3:00 p.m., 74 Jorgensen Title: Mutual simulation of Hamiltonian dynamics on interacting quantum systems Abstract: We address the problem of simulating pairinteraction Hamiltonians in n node quantum networks where the subsystems are qudits. We show that any pairinteraction can be used to simulate any other by applying sequences of appropriate local control sequences. Conditions on time optimal simulation are formulated in terms of spectral majorization of and ranks of matrices characterizing the coupling parameters. Efficient schemes for decoupling and time reversal can be constructed from orthogonal arrays. For general simulation tasks upper bounds can be obtained from properties of the underlying interaction graphs that characterize the coupling topologies between the subsystems. As an application we discuss methods that could help to implement adiabatic quantum computing by physically reasonable Hamiltonians like shortrange interactions. We construct a nearestneighbor Hamiltonian whose ground states encode the solutions to the NPcomplete problem INDEPENDENT SET in cubic planar graphs. This Hamiltonian can be easily simulated by Ising interactions between adjacent particles on a 2D rectangular lattice. We describe the required pulse sequences. 
April
8: IQI Seminar Lev Ioffe, Rutgers 3:00 p.m., 74 Jorgensen Title: Implementation of discrete lattice gauge theories with topologically protected degenerate ground states in Josephson Junction arrays and their possible use as ideal qubits Abstract: I discuss a new class of Josephson arrays which have nontrivial topology and exhibit a novel quantum state at low temperatures characterized by a topological order parameter. The low energy states of these systems are described by the lattice gauge theory with discrete group. I focus on two specific arrays designs that allow the easiest implementation: of abelian gauge groups the one that can be described as a topological superconductor and the other that is a topological insulator. The ground state of the topological superconductor is characterized by long range order in a two Cooper pair condensate and by a discrete topological order parameter. The excited states are gapful and carry charge 2e. There are two types of vortices in this array: the usual ones and the halfvortices, both having a large energy in the superconductive state. The ground state of the topological insulator has only topological order parameter, it can be viewed as a superfluid liquid of usual vortices in which the gap of halfvortices is preserved. The variation of the external magnetic field leads to a quantum phase transition between these two states. Both these arrays have 2^K degenerate ground states, with K being the number of global holes in the array. This degeneracy is exact in the thermodynamic limit or in finite arrays it is 'protected' from the external perturbations (and noise) by the topological order parameter and a spectral gap. In the ideal conditions the low order effect of the external perturbations on this degeneracy is exactly zero; deviations from ideality lead to exponentially small effects of perturbations. I argue that this system provides a physical implementation of an ideal quantum computer with a built in error correction and discuss possible experiments to test these proposals. Finally, I discuss general properties of nonabelian lattice gauge theories and their theoretical advantages for quantum computation. I show how these theories can be implemented in ideal Josephson junctions arrays.

April
10: IQI Special Seminar **Thursday** Greg Kuperberg, UC Davis 2:00 p.m., 156 Jorgensen Title: A
subexponentialtime quantum algorithm for the dihedral hidden subgroup
problem 
April
10: Preskill Group Meeting Greg Kuperberg, UC Davis 5:30 p.m., 156 Jorgensen Title: Hybrid
quantum memory and its capacity 
April
15: IQI Seminar Robin BlumeKohout, LANL 3:00 p.m., 74 Jorgensen Title: Decoherence
from an unstable environment 
April
22: IQI Seminar Michael Wolf, Max Planck Institute for Quantum Optics 3:00 p.m., 74 Jorgensen Title:
Entanglement of formation for Gaussian states 
April
29: IQI Seminar Ben Schumacher, Caltech 3:00 p.m., 74 Jorgensen Title: Sharable, Copyable, Classical Abstract: Classical information can be freely copied, but the "no cloning" theorem tells us that quantum information cannot. To what extent does this observation capture the entire distinction between the classical and quantum realms? This talk will discuss joint work with Reinhard Werner on two related ideas: the possible existence of copies ("sharable information") and the ability to make copies ("copyable information"). We will see how to characterize sharable and copyable states, and explore some useful examples of states with limited sharability. 

May
6: IQI Seminar Ashish Thapliyal, Berkeley 3:00 p.m., 74 Jorgensen Title: Multipartite maximally entangled states, minimal entanglement generating sets and entropic inequalities Abstract: Maximally entangled states are central to the theory of bipartite entanglement. Naturally, one would hope that generalizing the concept of maximally entangled states would lead to an increased understanding of multipartite entanglement. In this talk we will define multipartite maximally entangled states and show an elegant construction for such states. Then we will show that these maximally entangled states must be members of a minimal entanglement generating set ("entanglement basis"). Finally, we will show that these maximally entangled states and other similar states are intimately related to the question of existence of new entropic inequalities. 
May
20: IQI Seminar Gerard Milburn, University of Queensland 3:00 p.m., 74 Jorgensen Title: Quantum entanglement and fixed point bifurcations Abstract: Entanglement in nonlinear bipartite system can be associated with a fixed point bifurcation in the classical description. In a non dissipative system a fixed point can be associated with a quantum stationary state, usually a ground state. Using the example of coupled giant spins we show that, when the fixed point undergoes a supercritical pitchfork bifurcation, the corresponding quantum state achieves a maximum amount of entanglement. By way of contrast, we consider a molecular BEC system that experiences a different kind of bifurcation. In a dissipative system a fixed point becomes an attractor and we consider entanglement in the corresponding quantum steady state. 
May
22: Physics
Research Conference 
May
27: IQI Seminar Stephen Bartlett, Macquaire University, Australia 3:00 p.m., 74 Jorgensen Title: Restrictions to quantum information processing Abstract: New questions and possibilities in quantum information processing (QIP) often arise when we (or nature) place restrictions on what we can do. In fact, one of the most intensely studied restrictions, that of LOCC, is responsible for much of the rich structure in QIP including entanglement. I'll discuss two significant restrictions for bipartite QIP: the lack of a shared reference frame, and the existence of superselection rules. Both of these restrictions lead to interesting (and maybe surprising) results, and can be placed in a generalised framework that gives insight into other types of restrictions. 

June
3: IQI Seminar Daniel Terno, Perimeter Institute 3:00 p.m., 74 Jorgensen Title: Quantum information and special relativity Abstract: Relativistic effects affect nearly all notions of quantum information theory. The standard definition of a reduced density matrix fails for photon polarization because the transversality condition behaves like a superselection rule. We can however define an effective reduced density matrix which corresponds to a restricted class of positive operatorvalued measures. There are no pure photon qubits, and no exactly orthogonal qubit states. Reduced density matrices for the spin of massive particles are welldefined, but are not covariant under Lorentz transformations. The spin entropy is not a relativistic scalar and has no invariant meaning. The vacuum behaves as a noisy channel, even if the detectors are perfect. The distinguishability of quantum signals and their entanglement depend on the relative motion of observers, and the description of channels by completely positive maps is an approximation. 

July
8: IQI Seminar Michael Nielsen, University of Queensland 3:00 p.m., 74 Jorgensen Title: Entanglement and correlation in ground states of manybody systems Abstract: How can we characterize the entanglement and, more generally, the correlations in the ground state of a complex, manybody quantum system? In this talk I will discuss several very general results relating correlations to (a) the energy gap between the ground and first excited states, and (b) the strength of the interactions in the system. I will also describe a simple class of states  states of nondegenerate quantum errorcorrecting code  which cannot be ground states of any local Hamiltonian. These results illustrate the idea that techniques from quantum information science may be useful in understanding the properties of complex manybody quantum systems. 
July
15: IQI Seminar Gerardo Ortiz, LANL 3:00 p.m., 74 Jorgensen Title: Entanglement as an observerdependent concept Abstract: Entanglement is a uniquely quantum phenomenon whereby a pure state of a composite quantum system may cease to be determined by the states of its constituent subsystems. On the other hand, since entanglement is a property inherent to quantum states and is strongly related with quantum correlations, one would expect that the entanglement present in the ground state of a system changes substantially at a quantum phase transition. Characterizing and quantifying entanglement of those quantum states is at the core of a full understanding of the nature of phase transitions in matter. I will start this talk describing a generalization of entanglement based on the idea that entanglement is relative to a distinguished subspace of observables rather than a distinguished subsystem decomposition. A pure quantum state is entangled relative to such a subspace if its expectations are a proper mixture of those of other states. Many informationtheoretic aspects of entanglement can be extended to the general setting, suggesting new ways of measuring and classifying entanglement in multipartite systems. By going beyond the distinguishablesubsystem framework, generalized entanglement also provides novel tools for probing quantum correlations in strongly interacting manybody systems. I will make use of the notion of generalized entanglement to identify and characterize some quantum phase transitions. I will present a measure of multiparticle entanglement that plays the role of a disorder parameter in the case of broken symmetry phase transitions and show how to apply these concepts to models of interest in condensed matter physics. 
July
17 : Preskill Group Meeting Nicolas Cerf, University of Brussels, Belgium 5:30 p.m., 156 Jorgensen Title: Nongaussian quantum cloning of gaussian states Abstract: It has been known for some time that a phaseindependent amplifier can be used to clone all coherent states with a fidelity of 2/3. The underlying map is the optimal *gaussian* map for cloning. Surprisingly, it can be shown that some *nongaussian* cloning map gives rise to a 2.5 % improvement on this fidelity. The possible implications of this result on the nongaussian attacks of continuousvariable QKD protocols will be briefly discussed. 
July
22: IQI Seminar Dieter Jaksch, Oxford 3:00 p.m., 74 Jorgensen Title: Protected qubits and decoherence free subspaces for chains of neutral atoms Abstract: First I give a short review of proposals for quantum computing with neutral atoms in optical lattices and magnetic microstructures. One of them is based on controlled coherent collisions between two particles while the other scheme relies on strong dipoledipole interactions between two Rydberg atoms. I will then show how this strong interaction can be used to demonstrate protected quantum memory in 1D chains of atoms. I discuss the implementation of one and twoqubit gates for protected qubits. It turns out that single qubit operations are possible by dynamically crossing a quantum phase transition and amount in entanglement operations for these chains of atoms. Two qubit gates can be performed by controlled interactions between the chains. Finally I will extend this model by showing how to encode qubits in decoherence free subspaces of these chains of atoms and will discuss the implementation of one and two qubit gates those states. 
July
29: IQI Seminar Andrew Childs, MIT 3:00 p.m., 74 Jorgensen Title: Spatial search by quantum walk Abstract: Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of N items laid out in d spatial dimensions can be searched in time of order sqrt(N) for d>2, and in time of order sqrt(N) poly(log N) for d=2. We consider an alternative search algorithm based on a continuous time quantum walk on a graph. The case of the complete graph gives the continuous time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that sqrt(N) speedup can also be achieved on the hypercube. We show that full sqrt(N) speedup can be achieved on a ddimensional periodic lattice for d>4. In d=4, the quantum walk search algorithm takes time of order sqrt(N) poly(log N), and in d<4, the algorithm provides no speedup. Joint work
with Jeffrey Goldstone. 

September
2: IQI Seminar Michael BenOr, Hebrew University 3:00 p.m., 74 Jorgensen Title: An optimal security proof for the BB84 QKD Protocol Abstract: We present a simple security proof for the standard quantum key distribution scheme by Bennett and Brassard (BB84). Our proof is based on the oneway quantum communication complexity of 2universal hash functions, and a Disturbance/AdversaryInformationCompression tradeoff for this protocol. With these, we can show that with twoway classical error correction and privacy amplification, the BB84 protocol can tolerate a bit error rate of up to the optimal 25% (and 33% for the corresponding six state protocol). Joint work
with HoiKwong Lo 
September
9: IQI Seminar Emina Soljanin, Bell Labs 3:00 p.m., 74 Jorgensen Title: Frames in quantum and classical information theory Abstract: Several quantum and classical communications systems (e.g., quantum communications driven by memoryless sources, packet transmission over lossy networks, and multi user communications by CDMA) deal with surpassingly similar problems of the mathematical frame theory for different reasons. We look into how some of the questions have been solved in different areas as well as the questions that are still unanswered. In particular, we discuss frame problems associated with (possibly correlated) quantum memoryless sources. 
September
23: IQI Seminar Scott Aaronson, Berkeley 3:00 p.m., 74 Jorgensen Title: Multilinear formulas and skepticism of quantum computing Abstract: Several researchers, including Leonid Levin, Gerard 't Hooft, and Stephen Wolfram, have argued that quantum mechanics will break down before the factoring of large numbers becomes possible. If this is true, then there should be a natural set of quantum states that can account for all experiments performed to date, but not for Shor's factoring algorithm. We propose as a candidate the set of states expressible by a polynomial number of additions and tensor products. Using a recent lower bound on multilinear formula size due to Raz, we then show that states arising in quantum errorcorrection require n^{Omega(log n)} additions and tensor products even to approximate, which incidentally yields the first superpolynomial gap between general and multilinear formulas. More broadly, we introduce a complexity classification of pure quantum states, and prove many basic facts about this classification. Our goal is to refine vague ideas about a breakdown of quantum mechanics into specific hypotheses that might be testable in the near future. 
September
25: Information Sciences Seminar Robert Calderbank 11:00 a.m., 74 Jorgensen Title: Quantum computers and cellular phones Abstract: We explore the connection between quantum error correction and wireless systems that employ multiple antennas at the base station and the mobile terminal. These subjects share a common mathematical foundation, which is the combinatorics of binary quadratic forms, that is to say orthogonal geometry. We shall describe how the wireless industry is making use of a mathematical framework developed by Radon and Hurwitz about a hundred years ago. 

October
7 : IQI Seminar Philippe Pouliot, Queen Mary, University of London 3:00 p.m., 74 Jorgensen Title: Quantum information processing with oxygen impurities in silicon Abstract: We propose the system of oxygen impurities in silicon as a possible architecture for quantum computation and information processing. In theory, up to 5 qubits could be defined on one oxygen atom. There are good prospects for scalability, and for a long decoherence time. Much could readily be done with present technology, and operating temperatures need not be very cold. We will review the 50 years of remarkable research on this system, and sketch an experimental and theoretical program for developing a working quantum computer. 
October
14: IQI Seminar Rob Spekkens, Perimeter Institute 3:00 p.m., 74 Jorgensen Title: In defense of the view that quantum states are states of knowledge Abstract: I present a toy theory that is based on a simple informationtheoretic principle, namely, that when one has maximal knowledge of a system, one's knowledge is quantitatively equal to one's ignorance. The object analogous to the quantum state in the theory is a uniform probability distribution over hidden states. Because the theory is, by construction, local and noncontextual, it does not reproduce quantum theory. Nonetheless, a wide variety of quantum phenomena have analogues within the toy theory that admit simple and intuitive explanations. Such phenomena include: the noncommutativity of measurements, interference, no information gain without disturbance, the multiplicity of pure state decompositions of a mixed state, the distinction between twoway and intrinsic threeway entanglement, the monogamy of pure entanglement, no cloning, teleportation, dense coding, mutually unbiased bases, locally immeasurable product bases, unextendible product bases, the possibility of key distribution, the impossibility of bit commitment, and many others. The diversity and quality of these analogies provides compelling evidence for the view that quantum states are states of knowledge rather than states of reality, and that maximal knowledge is incomplete knowledge. A consideration of the phenomena that the toy theory fails to reproduce, notably, violations of Bell inequalities and the existence of a KochenSpecker theorem, provides clues for how to proceed with a research program wherein the quantum state being a state of knowledge is the idea upon which one never compromises.

October
21: IQI Seminar Igor Devetak, IBM 3:00 p.m., 74 Jorgensen Title: Recent progress in quantum Shannon theory Abstract: The task of quantum Shannon theory is to find asymptotic conversion rates between various quantum or classical resources, expressed in terms of quantum information theoretical quantities such as von Neumann entropy, quantum mutual information and coherent information. The first part of the talk concerns an operational connection between quantum privacy and quantum coherence. Protocols for oneway entanglement generation and distillation are obtained from particular protocols for secret key generation and distillation, respectively, by "making them coherent". In the second part it will be shown that many of the known resource interconversion protocols (such as quantum information transmission, entanglement distillation and entanglement assisted communication) may be organized into a "family" in which the children protocols descend from the parents via teleportation or superdense coding. Moreover, the parent protocols may be recovered from the children by "making them coherent". 

November
4: IQI Seminar Guifre Vidal, Caltech 3:00 p.m., 74 Jorgensen Title: Efficient simulation of 1D quantum systems on a lattice Abstract: We describe a numerical method to efficiently simulate the time evolution, according to a Hamiltonian made of local interactions, of quantum spin chains and systems alike. The efficiency of the scheme depends on the amount of the entanglement involved in the simulated evolution. Numerical analysis suggests that this method can be used, for instance, to study timedependent properties of the ground state and low energy excitations in generic onedimensional quantum manybody systems. 
November
11: IQI Seminar Daniel Gottesman, Perimeter Institute 3:00 p.m., 74 Jorgensen Title: The minimum distance problem for twoway entanglement purification Abstract: Entanglement purification protocols (EPPs) with oneway classical communications are equivalent to quantum errorcorrecting codes. The problem of designing such codes has been studied both for maximum likelihood decoding for large block sizes and asymptotically high fidelity, and in the minimum distance variant, usually for fixed small block sizes, in which the number of allowed errors is strictly bounded. EPPs using twoway classical communications are known to be substantially more powerful than oneway EPPs for the maximum likelihood decoding problem, at least as far as allowable error rate. We study the analogue of the minimum distance problem for twoway EPPs, in which Alice and Bob wish to extract at least k EPR pairs from an initial set of n pairs, given that errors have occurred on no more than t of the original pairs. We show that twoway EPPs can be better than any quantum errorcorrecting code in this scenario, and give examples of twoway EPPs that exceed both the quantum Hamming bound and the quantum Singleton bound. We also show that twoway EPPs in this minimum distance scenario can asymptotically achieve the quantum Hamming bound with a fixed fraction of errors, whereas the best known lower bound on the existence of quantum codes is the quantum GilbertVarshamov bound, allowing only half the error rate for the same data rate. This is joint work with Andris Ambainis. 
November
12: Special IQI Seminar 
November
13: Group Meeting The arguments
break down for the nonabelian hidden subgroup problem, and for the special
case of the dihedral group, we give explicit expressions for the optimal
measurement to distinguish between the subgroups given one random coset
state. This measurement cannot be expressed in terms of the Fourier basis,
which suggests that to find a quantum algorithm for the nonabelian hidden
subgroup problem we may have to look beyond the Fourier transform.

November
18: IQI Seminar 
November
20: Group Meeting Dave Bacon, Caltech 5:30 p.m., 156 Jorgensen Title: A cornucopia of efficient quantum transforms Abstract: I will discuss two efficient implementations of transformations useful for quantum information. The first is a generic transformation which can be used to exploit symmetries present in a quantum problem. This transformation is a generalization of the Kitaev phase estimation circuit and generalizes the swap test. The second transformation I will discuss is the Schur basis change. This basis change is from the computational basis of n qudits to the basis corresponding to fully reducing the representation of the permutation group given permuting these n qudits (and similarly reducing the dual action of U(d) acting identitally on all n qudits.) This transformation has many uses in quantum information theory including specturm estimation, universal entanglement concentration, and universal compression. 
November
25: IQI Seminar CANCELLED Dorit Aharonov, Hebrew University 3:00 p.m., 74 Jorgensen Title: On the universality of adiabatic quantum computation Abstract: Adiabatic quantum computation has attracted considerable attention recently, but its computational power was unclear. I will explain a recent result which clarifies the question showing that adiabatic computers with local Hamiltonians are as powerful as conventional quantum computers. The result holds even in the physically realistic setting in which the particles in the adiabatic system are set on a two dimensional grid with nearest neighbor interactions. The result provides an alternative language to study quantum computation: the langauge of spectral gaps and ground states. This raises the hope for borrowing tools from the extensive physics and mathematical literature on spectra analysis to attack the difficult challenges in quantum computation, and also makes these challenges accessible to a wider audience. Joint works with van Dam, Kempe, Landau, Lloyd, Regev and TaShma. 

January
13: IQI Seminar Anatoli Polkovnikov, Harvard 3:00 p.m., 74 Jorgensen Title: Dynamics of interacting bosons in an optical lattice Abstract: This talk focuses on some aspects of nonequilibrium behavior of interacting bosons confined in a periodic potential. I will start from a particular example of dynamical restoration of coherence in a system, initially in the Mott insulating state, after a sudden increase of the tunneling amplitude. I will argue that the time evolution can be described using the classical GrossPitaevskii equations of motion, given that we choose appropriate initial conditions. In the second example I will analyze behavior of the condensate near the point of classical instability and will show that quantum fluctuations can drive the system into a macroscopically entangled ("Schrödinger cat") state. Integrating classical equations of motion would be again sufficient to describe the dynamics. Using these two examples as a motivation, I will write a formal expansion in quantum fluctuations for the time evolution of an arbitrary observable in a system of interacting bosons. In the first order I will recover classical GrossPitaveskii result. In the second order the evolution will be still described by GrossPitavskii equations with the initial conditions distributed according to the Wigner transform of the initial density matrix. The further corrections will arise in the form of nonlinear response of the observable to an infinitesimal perturbation of the field along its classical trajectory and will be interpreted as quantum scattering events. At the end of the talk I will discuss the validity of the expansion using several exactly solvable examples and give an outlook to the possible extensions of this work. 
January
20: IQI Seminar Chetan Nayak, UCLA 3:00 p.m., 74 Jorgensen Title: A class of P,Tinvariant topological phases of correlated electrons Abstract: I will describe an approach to understanding the effective field theories associated with some P,Tinvariant topological phases of correlated electrons, which have possible application to faulttolerant quantum computation. This approach suggests a strategy for constructing microscopic models which admit such phases, which is elucidated with some examples. 
February
17: IQI Seminar Aram Harrow, MIT 3:00 p.m., 74 Jorgensen Title: Coherent communication of classical messages Abstract: We define "coherent communication" in terms of a simple primitive, show it is equivalent to the ability to send a classical message with a unitary or isometric operation, and use it to relate other resources in quantum information theory. Using coherent communication, we are able to generalize superdense coding to prepare arbitrary quantum states instead of only classical messages. We also derive singleletter formulae for the classical and quantum capacities of a bipartite unitary gate assisted by an arbitrary fixed amount of entanglement per use. 
February
24: IQI Seminar Rainer Blatt, University of Innsbruck 3:00 p.m., 74 Jorgensen Title: Quantum information processing with trapped Ca+ ions Abstract: Trapped strings of cold ions provide an ideal system for quantum information processing. The quantum information can be stored in individual ions and these qubits can be individually prepared, the corresponding quantum states can be manipulated and measured with nearly 100% detection efficiency. With trapped Ca+ ions a DeutschJozsa algorithm was implemented and the CiracZoller gate operation was realized. Bell states of two ions are deterministically produced and using a decoherence free subspace they exhibit lifetimes of half a second. With three ions W and GHZ states are prepared and their decoherence is investigated. 
February
27: IQI Special Seminar Miklos Santha, University of Paris 1:00 p.m., 74 Jorgensen Title: Quantum and classical query complexities of local search are polynomially related Abstract: Let $f$ be an integer valued function on a finite set $V$. We call an undirected graph $G(V,E)$ a {\em neighborhood structure} for $f$. The problem of finding a local minimum for $f$ can be phrased as: for a fixed neighborhood structure $G(V,E)$ find an input $x\in V$ such that $f(x)$ is not bigger than any value that $f$ takes on some neighbor of $x$. The complexity of the algorithm is measured by the number of questions of the form "what is the value of $f$ on $x$?'' In this article we show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This is joint work with Mario Szegedy. 

March
2: IQI Seminar Norbert Lütkenhaus, University of ErlangenNürnberg 3:00 p.m., 74 Jorgensen Title: Quantum correlations for communication tasks Abstract: Practical Quantum Communication protocols can be understood as having two phases: first, the generation of classical data, and second, a public communication protocol that accomplishes the desired task using the correlated classical data. The prime example is quantum key distribution. We investigate the borderline between classically and quantumly correlated classical data. The investigation is based only on actual observable data coming from a restricted set of actually implemented measurements 
March
5: IST Special Seminar Debbie Leung, Caltech 2:00 p.m., 80 Moore Title: "Quantum information" theory  Quantum "information theory" or Quantum (information) theory ? Abstract: Quantum information theory is concerned with the ultimate information processing capabilities of quantum mechanical systems. We exploit quantum features to achieve information processing tasks that are impossible classically, but as we are pushing the limits of quantum systems to process information, we found ourselves in some vast unexplored territory of quantum theory. Examples of such coenrichment of information theory and quantum theory will be given in the seminar: (1) the task of locking information turns out to be related to the entropic uncertainty principle and also related to the security of quantum key distribution, (2) teleportation (communicating quantum states by a classical channel and entanglement) turns out to enable quantum computation using measurements only, (3) optimal "teleportation" of quantum states known to the sender turns out to be related to failure in approximating quantum evolutions and also related to encryption of quantum states, and key reuse in encryption. Bio: Debbie Leung received her B.S. degree at Caltech in 1995, and a Ph.D. in physics from Stanford in 2000. She has been a postdoctoral fellow at the IBM T.J. Watson Research Center and the Mathematical Sciences Research Institute. Since 2003, she has been the Richard C. Tolman Prize Postdoctoral Scholar in Theoretical Physics at Caltech. 
March
9: IQI Seminar HoiKwong Lo, University of Toronto 3:00 p.m., 74 Jorgensen Title: Communication complexity and security of quantum key distribution Abstract: Various techniques have been applied to prove the security of the standard quantum key distribution protocol invented by Bennett and Brassard (BB84). In particular, BenOr has provided such a security proof for BB84 using communication complexity. His proof works for a bit error rate as high as 6.2 percent. Here, we simplify BenOr's proof and extend it to a bit error rate of 11 percent for BB84 with only oneway classical communications. This error rate coincides with ShorPreskill's result. We remark that, in the security proofs of QKD, a random coding argument can be replaced by a communication complexity argument. In fact, the two arguments give equivalent results. [This is
joint work with Michael BenOr.] 
March
16: IQI Seminar Sergey Bravyi, Caltech 3:00 p.m., 74 Jorgensen Title: Entanglement theory for fermionic modes Abstract: We apply a subsystemindependent generalization of entanglement developed by Barnum, Knill, and Ortiz to a system of fermionic modes. In this approach unentangled states describe noninteracting fermions and can be transformed into the 'product' form by an appropriate Bogolyubov transformation. Operations generated by pairwise interactions and measurements of occupation numbers of individual modes are analogues of LOCC operations in the standard entanglement theory. We call them Gaussian operations. Efficient classical simulation schemes for Gaussian operations are discussed. We show how to quantify fermionic entanglement by constructing functionals monotone under Gaussian operations. It turns out that amount of classical memory needed to describe a quantum state grows only polynomially with a number of fermionic modes provided that entanglement is bounded by a constant. 
March
17: IST Seminar Patrick Hayden, Caltech 4:00 p.m., 070 Moore Title: Quantum Communication: A real Enigma Abstract: The invention of quantum cryptography in the 1980s demonstrated that the laws of quantum mechanics can be exploited to develop unconditionally secure cryptography. The discovery of teleportation a decade later then provided a natural way of building an encrypted, authenticated channel out of quantum entanglement. These pivotal advances suggested the existence of an intrinsic connection between communication and privacy in quantum mechanics that has recently been solidified from a number of directions. In this seminar, I'll survey some of the ideas underlying these recent advances. First, I'll sketch how an improved method for encrypting quantum states leads directly to a correspondingly more efficient variant of teleportation. Next, I'll indicate how to build an intrinsically secure quantum channel, that is, one that is authenticated and encrypted at a negligible cost. Finally, I'll give a very brief account of how the connection between communication and privacy has been exploited in quantum Shannon theory, both as a unifying principle and a technical tool. Bio: Patrick
Hayden is currently a Sherman Fairchild Prize Postdoctoral Scholar in
the Caltech physics department. He completed his doctorate in physics
at Oxford University as a Rhodes Scholar in 2001 and received an undergraduate
degree with joint honours in mathematics and physics from McGill University
in 1998. His current research interests were foreshadowed at an early
age; as a highschool student, he spent summers working for an operating
systems company with the oddly prescient name Quantum Software Systems. 
March
30: IQI Seminar Iordinis Kerenidis, Berkeley 3:00 p.m., 74 Jorgensen Title: Exponential separation of quantum and classical oneway communication complexity Abstract: We give the first exponential separation between quantum and boundederror randomized oneway communication complexity. Specifically, we define the Hidden Matching Problem and prove that its quantum oneway communication complexity is $O(\log n)$, yet any randomized oneway protocol with bounded error must use $\Omega({\sqrt{n}})$ bits of communication. No asymptotic gap for oneway communication was previously known. The hidden matching problem also provides the first exponential separation between Simultaneous messages with public coins and quantum Simultaneous Messages. 
April2004


April
6: IQI Seminar Andreas Winter, University of Bristol, UK 3:00 p.m., 74 Jorgensen Title: Random quantum channels and notions of quantum information transfer Abstract: I will disucss a set of random variables, taking values in quantum channels, which seem to be interesting in their own right but also have interesting connections to the task of "identification via quantum channels". We are able to show that the capacity of a qubit for this task is, surprisingly, 2, as is the capacity of an ebit (with negligible additional communication). There is also the related notion of quantum state identification, which will be discussed. Recent progress on identification capacities for feedback channels are presented. The talk is based on recent preprints 0401060, 0403233. 
April
13: IQI Seminar Vlatko Vedral, Imperial College London, UK 3:00 p.m., 74 Jorgensen Title: Thermodynamics of entanglement and entanglement in thermodynamics Abstract: In the first part of my talk I plan to discuss our understanding of entanglement via its analogy with the concept of entropy in thermodynamics. This approach will be based on ordering of physical states depending on their conversion into each other using some allowed set of operations. The allowed operations in thermodynamics are adiabatic processes, while for entanglement manipulations they are local operations and classical communication. In the second half of my talk I will discuss the notion of entanglement in typical solid state systems. There are several motivations for this. One is that we would (fundamentally) like to know if entanglement persists in macroscopic systems and at high temperatures. The second is to learn if this entanglement affects thermodynamical behaviour of the system, such as its magnetic susceptibility for example. Finally, we would like to be able to know if this kind of thermal entanglement can be used for information processing. I present some simple examples throughout my talk and show how general calculations proceed. 
April
20: IQI Seminar Markus Greiner, University of Colorado 3:00 p.m., 74 Jorgensen Title: Observation of resonance condensation of fermionic atom pairs Abstract: The realization of fermionic superfluidity in a dilute gas of atoms, analogous to superconductivity in metals, is a longstanding goal of ultracold gas research. Beyond being a new example of this fascinating quantum phenomenon, fermionic superfluidity in an atomic gas holds the promise of adjustable interactions and of the ability to tune continuously from BCStype superfluidity to BoseEinstein condensation (BEC). I will talk about recent experiments, where we have converted a Fermi sea of atoms into a molecular BEC. Furthermore we have created a condensate of fermionic atom pairs in a regime where no twoparticle bound molecular state exists, thereby entering the BECBCS crossover regime. The experiments open the intriguing possibility to address questions of modern solid state physics with an atomicphysics system. 
April
27: IQI Seminar David Poulin, Perimeter Institute, CAN 3:00 p.m., 74 Jorgensen Title: Macroscopic observables Abstract: We study macroscopic observables defined as the total value of a physical quantity over a collection of quantum systems. We show that previous results obtained for {\em infinite} ensemble of identically prepared systems lead to incorrect conclusions for finite ensembles. In particular, the measurement of a macroscopic observable significantly disturbs the state of any finite ensemble. However, we show how this disturbance can be made arbitrarily small when the measurement of the macroscopic observable are of finite accuracy. We demonstrate a tradeoff between state disturbance and measurement accuracy as a function of the size of the ensemble. Using this tradeoff, we show that the histories generated by a sequence of finite accuracy macroscopic measurements always generate a consistent family in the absence of large scale entanglement, for sufficiently large ensembles. Hence, macroscopic observables operate as {\em Abelian} variables provided that their accuracy is coarser than the quantum correlation lengthscale of the system. The role of these observable is also discussed in the context of NMR quantum information processing and bulk quantum state tomography. 
May2004


May
4: IQI Special Seminar Vwani Roychowdhury, UCLA 3:00 p.m., 114 E Bridge Title: Algorithmic cooling of spins: A practicable method for increasing polarization Abstract: An efficient technique to generate spin ensembles that can be highly polarized by external magnetic fields is a holy grail in Nuclear Magnetic Resonance (NMR) spectroscopy, with significant potential impact in a number of scientific and medical disciplines. Since spin ensembles have fixed steadystate polarization biases that increase inversely with temperature, spins exhibiting high polarization biases are considered cool, even when their environment is warm. Existing spin cooling methods are highly limited in their efficiency and usefulness. Algorithmic cooling is a promising new spincooling technique that employs datacompression methods in open systems. We discuss recent developments in algorithmic cooling techniques that can potentially cool spins even on short molecules. Such realistic algorithmic cooling could lead to breakthroughs in highsensitivity NMR spectroscopy in the near future, and to the development of scalable NMR quantum computers in the far future. 
May
7: IQI Special Seminar Dominic Berry, Macquarie University, Australia 3:00, 156 Jorgensen Title: Postprocessing single photon sources via linear optics and photodetection Abstract: Triggered singlephoton sources produce the vacuum state with nonnegligible probability, but produce a much smaller multiphoton component. I describe a method for increasing the probability of a single photon in a single mode using a chain of beam splitters. This method has the drawbacks that it introduces a significant multiphoton component, and it can not be used to increase the probability for a single photon above 1/2. These drawbacks only hold for incoherent photon sources. If the photon sources produced pure states rather than incoherent superpositions, it would be possible to obtain a perfect single photon output. I also present an analysis of the impact of experimental limitations, including distinguishable photons, inefficient detectors, dark counts, and multiphoton components in the inputs. 
May
11: IQI Seminar Christopher King, Northeastern University 3:00 p.m., 74 Jorgensen Title: Applications of matrix inequalities in quantum information theory Abstract: This talk will review some of the proofs of the additivity conjecture for product channels, emphasizing the role played by matrix inequalities. In addition to the LiebThirring inequality, other less wellknown inequalities will be discussed, and some directions indicated for future research. 
May
21: IQI Special Seminar Akira Furusawa, University of Tokyo 3:00 p.m., 114 E Bridge Title: Quantum teleportation and its applications Abstract: We succeeded in the realization of quantum teleportation of continuous variables at Kimble Lab in 1998. We are continuing to do this type of experiments at University of Tokyo. In 1998, the teleported state was a coherent state, which is a kind of classical state in the sense of GlauberSudarshan Pfunction. We have succeeded in the teleportation of a squeezed state, which is a nonclassical state. To make a quantum teleportation network among three parties, we have succeeded in preparing a fully inseparable tripartite continuousvariable state by combining three independent squeezed vacuum states. By using the tripartite entangled state, we have succeeded in making a quantum teleportation network among three parties, in which quantum teleportation between two parties is performed with the help of the third party. Our teleportation fidelity between every pair in the network is about 0.64. Note that the fidelity in 1998 was 0.57 even though the experiment was performed on the teleportation between two parties with bipartite entanglement. We are now trying to do entanglement swapping, which is teleportation of entanglement. I will show our present status. 
June2004


June
14: IQI Seminar Toby Cubitt, Max Planck Institute 3:00 p.m., 74 Jorgensen Title: Entanglement flow in multipartite systems Abstract: Entanglement has become well established as a physical quantity, on a par with energy or entropy. Though we still do not fully understand how to quantify or characterize entanglement ("entanglement statics"), people have already started to move from studying statics to studying dynamics: how entanglement behaves in evolving quantum systems. I will discuss our recent investigations of entanglement dynamics in multipartite systems (quantph/0404179). We have shown that it is possible to establish a quantitative concept of entanglement flow: both flow through individual particles, and flow along general networks of interacting particles. The results give quite general quantitative relations between the rate at which entanglement can flow and the entanglement already existing in the system. As an example application, we have used the results to derive lower bounds on the time required to entangle the end qubits in a chain (or more precisely, on the scaling of the time with the length of the chain). But perhaps more importantly, the results also give some qualitative insight into how entanglement flows through multipartite systems. 
June
22: IQI Seminar Isaac Chuang, MIT 3:00 p.m., 74 Jorgensen Title: The threshold for ion trap quantum computation Abstract: Largescale classical computing systems are robust because component failure probabilities are negligible. However, decoherence errors inherent in accessible physical implementations will likely require quantum computing systems to adopt a different approach, in which robustness is provided by careful design and engineering. I present our case study of one specific implementation, using trapped ions as qubits. We obtain the threshold for fault tolerance from a detailed numerical simulation of an O(1000) qubit system, using actual experimental values from NIST for logic gate, movement, measurement, and control failure probabilities. 
November2004


November
2: IQI Seminar Gil Refael, UCSB 3:00 p.m., 74 Jorgensen Title: Entanglement entropy of random critical points in one dimension Abstract: For quantum critical spin chains without disorder, it is known that the entanglement of a segment of N>>1 spins with the remainder is log N times a prefactor determined by the central charge of the associated conformal field theory. For a class of strongly random quantum spin chains, the same logarithmic scaling holds for mean entanglement at criticality and defines a critical entropy equivalent to central charge in the pure case. This effective central charge is obtained for Heisenberg, XX, and quantum Ising chains using a realspace renormalization group approach. In my talk I'll introduce the realspace RG as it applies to the relevant models, review the derivation of the entanglement entropy, and discuss its consequences. 
November
4: Group Meeting Robert Raussendorf 5:30 p.m., 156 Jorgensen Title: Longrange entanglement in noisy cluster states Abstract: In realistic physical systems, decoherence represents a formidable but surmountable obstacle to the creation of entanglement among far distant particles. Devices such as quantum repeaters and faulttolerant quantum computers are being envisioned in which the entanglement length (=range of entanglement) is infinite, provided the noise is below a critical level. But can an infinite entanglement length be found in generic physical systems subjected to noise, too? This is indeed the case, and I will provide an example in my talk. I describe a phase transition for longrange localizable entanglement in a noisy threedimensional cluster state. The partially decohered state is modeled by the thermal state of a suitable translationinvariant shortrange Hamiltonian. We find that the temperature at which the entanglement length changes from infinite to finite is nonzero. This is joint work with Sergey and Jim. 
November
9: IQI Seminar David Poulin, University of Waterloo 3:00 p.m., 74 Jorgensen Title: Exploring quantum control with quantum information processors Abstract: I will present two quantum algorithms which measure dynamical properties of quantum systems, namely their form factors and fidelity decay rate. These quantities  which emerged from the field of quantum chaos  are indicators of dynamical stability which is a crucial prerequisite to control the evolution of these quantum systems, i.e. to construct quantum computers out of them. Furthermore, the algorithms can be performed on quantum information processors with a single pure qubit (DQC1). This questions the common wisdom that entanglement is the source of quantum computational speedup. I will also use these quantum algorithms to establish a direct relation between dynamical stability and decoherence, and illustrate how entanglement is "not" a prerequisite to decoherence. 
January2005


January
11: IQI Seminar Michal Hordecki, University of Gdansk, Poland 3:00 p.m., 74 Jorgensen Title: Thermodynamical cost of erasure of correlations in quantum systems Abstract: I will present recent results on evaluating so called "quantum deficit"  minimal entropy production necessary for bringing a state of distributed quantum systems to product form, by local operations and classical comunication. Thermodynamical interpretation of quantum deficit in terms of drawing work by local heat engines in Hamiltonian framework will be provided. The bounds for quantum deficit obtained will be compared with bounds on distillable entanglement. Definition of thermodynamical cost of erasing entanglement will be introduced and lower and upper bounds for such cost provided. The cost of erasure of entanglement will be considered as a candidate for entanglement measure based destroying entanglement, rather than using it. 
January
20: IQI Special Seminar Michael Freedman, Microsoft Research 1:30 p.m., 239 Moore Title: Reflection positivity for smooth manifolds fails in dimension four and higher Abstract: I will discuss an abstract pairing in all dimensions which lands in formal combinations of manifolds. There are some pretty attractive open problems in dimension=3. In dimension 4 putting together some mostly old knowledge implies that hcobordant 4manifolds can not be distinguished by unitary TQFTs (obeying reasonable gluing axioms.) 
February2005


February
1: IQI Seminar Stefano Pironio, Caltech 3:00 p.m., 74 Jorgensen Title: Bell inequalities and the communication cost of simulating nonlocality Abstract: To reproduce nonlocal correlations in a classical scenario, communication must occur between the parties. We show that lower bounds on this communication can be obtained from the amount by which nonlocal correlations violate Bell inequalities. Further, we demonstrate that to each set of nonlocal correlations is associated an optimal Bell inequality such that the corresponding bound on the communication is tight. We conclude by presenting some applications of these results. 
February
15: IQI Seminar Jon Yard, Stanford University 3:00 p.m., 74 Jorgensen Title: Capacity theorems for quantum multiple access channels Abstract: Suppose that two independent senders, Alice and Bob, have access to different parts of the input of an arbitrary quantum channel with a single receiver Charlie. I will present in detail two theorems which partially characterize the rates at which both senders can simultaneously transmit independent classical and quantum information. The first theorem provides a multiletter characterization of the rates at which it is possible for Alice to send classical information while Bob sends quantum information. An example of a channel for which this region has a singleletter characterization is also given. The second theorem is a multiletter characterization of the rates at which Alice and Bob can each send quantum information. This characterization represents a recent improvement over that contained in the original version of quantph/0501045. I conclude by mentioning a full fourdimensional characterization of the rates at which both senders can simulaneously send classical and quantum information. This is
joint work with Igor Devetak and Patrick Hayden. 
March2005


March
1: IQI Seminar 
March
15: IQI Seminar Rolando Somma, Los Alamos National Laboratory 3:00 p.m., 74 Jorgensen Title: Generalized entanglement as a resource for efficient computation Abstract: About two years ago, we have introduced a notion we call Generalized Entanglement (GE), which differs from the traditional concept in that it does not refer to a particular subsystem decomposition [1]. This notion is general in the sense that it depends on a preferred (chosen) set of observables and can be applied to any quantum physical setting, regardless of its nature or particle statistics. In this talk I will review the basics of GE presenting some useful applications to manybody systems, such as the study of the groundstate correlations in the spin1/2 anisotropic XY chain in presence of an external magnetic field [2]. Moreover, I will show new results on how GE can be used as a resource for more efficient computation by means of deterministic quantum algorithms. [1] H. Barnum,
E. Knill, G. Ortiz, L. Viola (2002), PRA v.68 p.032308 (2003).

March
29: IQI Seminar Matthias Christandl, University of Cambridge 3:00 p.m., 74 Jorgensen Title: The spectra of quantum states and representation theory Abstract: Determining the relationship between composite systems and their subsystems is a fundamental problem in quantum physics. In this talk I will consider the spectra of a bipartite quantum state and its two marginal states. To each spectrum one can associate representations of the symmetric group defined by Young diagram whose normalised row lengths approximate the spectrum. I will show that, for allowed spectra, the representation of the composite system is contained in the tensor product of the representations of the two subsystems. This gives a new physical meaning to representations of the symmetric group. It also introduces a new way of using the machinery of group theory in quantum informational problems, which we illustrate by two simple examples. This is joint work with Graeme Mitchison and available at quantph/0501090.

April2005


April
5: IQI Seminar Jiannis Pachos, University of Cambridge 3:00 p.m., 74 Jorgensen Title: Quantum information with optical lattices Abstract: Optical lattices are an ideal physical setup for simulating quantum systems with great control accuracy and long decoherence times. Considering this setup we present implementations based on global addressing and on one way quantum computation. We also discuss quantum simulations of exotic systems as well as we probe new directions towards realizing topological quantum computation. 
April
19: IQI Seminar Jiri Vala, UC Berkeley 3:00 p.m., 74 Jorgensen Title: Topological phases for quantum computation: their properties and physical realization Abstract: Topological quantum computation provides natural fault tolerance, thereby circumventing the need for demanding concatenation of error correcting codes. Crucial and also very challenging steps in implementation of topological quantum computation are identification and physical realization of topological phases, universal for quantum computation, in quantum many body systems. I will present
a methodology for calculation of spectral properties of quantum lattice
systems, namely the ground state degeneracy and the spectral gap, dependence
of which on the lattice system topology are important indicators of topological
phases. Preliminary calculations indicate good scaling and convergence
properties that will allow a range of calculations to localize topological
phases in the phase diagram of studied systems. I will also discuss some
aspects of physical realization of topological phases with a particular
focus on an extended Hubbard model that has been proposed by Freedman,
Nayak and Shtengel (condmat/0309120, Phys. Rev. Lett. 94, 066401 (2005)). 
May2005


May
6: IQI Special Seminar Jim Harrington, LANL 2:00 p.m., 156 Jorgensen Title: Enhancing practical security of quantum key distribution with a few decoy states Abstract: The security of quantum key distribution (QKD) protocols such as BB84 rely on singlephoton sources, but present implementations primarily utilize weak coherent pulses, which can produce vulnerable multiphoton signals. The decoy state method, introduced by Hwang [PRL 91, 057901 (2003)] and made rigorous by Lo et al. [quantph/0411004], provides a way to characterize the quantum communication channel with current technology detectors by varying the signal intensities and thus identify how many singlephoton signals entered the sifted key. In this work, we present how to incorporate finite statistics into this approach and present a specific decoy state protocol that should be straightforward to implement in freespace QKD. 
May
10 : IQI Seminar David Fattal, Stanford 3:00 p.m., 74 Jorgensen Title: Bipartite entanglement in the stabilizer formalism Abstract: In this talk, I will show that bipartite stabilizer states of arbitrary quantum systems (qubits, qudits, continuous variable) can be compactly described in terms of a canonical set of Pauli operators that make their entanglement properties transparent. We work in a stabilizer algebra rather than group, which allows to treat the qubit, qudit or CV case on an equal footing. 
May
17 : IQI Seminar Seth Lloyd, MIT 3:00 p.m., 74 Jorgensen Title: A theory of quantum gravity based on quantum computation Abstract: A theory of quantum gravity based on quantum computation is proposed. In this theory, fundamental processes are described in terms of quantum information processing: the geometry of spacetime is a construct, derived from the underlying quantum computation. Explicit mechanisms are provided for the backreaction of the metric to computational 'matter,' blackhole evaporation, holography, and quantum cosmology. 
May
24: IQI Seminar Andrew Silberfarb, University of New Mexico 3:00 p.m., 74 Jorgensen Title: Quantum state reconstruction via continuous measurement Abstract: We consider how to use a continuous quantum measurement on an ensemble of atoms to reconstruct the quantum state of a system. The conditions under which such a reconstruction is possible and feasible are presented. Additionally preliminary experimental results for the reconstruction of a spin 3 system are presented. 
May
31: IQI Seminar Tien Kieu, Swinburne University of Technology 3:00 p.m., 74 Jorgensen Title: Quantum adiabatic computation: From Hilbert's tenth problem to the SuperfluidMott insulator quantum phase transition Abstract: We present quantum adiabatic computation (QAC) as an alternative model to that of the standard quantum computation with qubits and quantum gates. The application of QAC to the recursively noncomputable Turing halting problem, or its equivalence which is Hilbert's tenth problem, reveals its potential computational capability beyond that of Turing machines. We outline such a quantum adiabatic algorithm and discuss its key ingredients. Also mentioned are some unfounded prejudices against the algorithm as well as some potential difficulties in the physical implementation. We end the talk by pointing out a surprising and interesting connection between the algorithm and the superfluidMott insulator quantum phase transition. 
June2005


June
7: IQI Seminar Cristopher Moore, University of New Mexico 4:30 p.m., 74 Jorgensen Title: Multiregister Fourier sampling and subexponentialtime algorithms for the Hidden Subgroup Problem Abstract: The Hidden Subgroup Problem is of fundamental interest in quantum computing; it offers essentially the only known family of algorithms which are exponentially faster than their classical counterparts, and an algorithm for the HSP on the symmetric group would allow us to solve Graph Isomorphism. Recent work by Kuperberg, Regev, and Bacon, Childs and van Dam have shown that the HSP for the dihedral group, and some other families of nonabelian groups, can be reduced to a random case of a classical combinatorial problem such as Subset Sum, and a similar worstcase to averagecase reduction for Graph Isomorphism would be very exciting. I will describe two recent results obtained in joint work with Alex Russell: first, an explicit (though not necessarily efficient) multiregister measurement for an important case of the HSP over arbitrary groups, in which each subset of the registers yields some information about the hidden subgroup; and second, a general Subset Sumrelated approach to building subexponentialtime algorithms for the HSP on a class of nonabelian groups, which ties together several recent approaches to the HSP. I will conclude by commenting on the obstacles we face in trying to apply this technique to the symmetric group. 
June
8: IST Seminar Alexander Russell, University of Connecticut 4:00 p.m., 74 Jorgensen Title: The symmetric group defies Fourier sampling: Finding hidden subgroups requires nonseparable measurement Abstract: We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem. Specifically, we show that the hidden subgroup problem over the symmetric group cannot be efficiently solved by strong Fourier sampling, even if one may perform an arbitrary POVM on the coset state. These results apply to the special case relevant to the Graph Isomorphism problem. We will discuss extensions of these results to entangled sampling and other groups of interest. 
June
29: Group Meeting Jonathan Barrett, Perimeter Institute 5:30, 156 Jorgensen Title: Nonlocality and secrecy Abstract: I will describe a connection between correlations that are nonlocal, in the sense of violating a Bell inequality, and secrecy. I will then show how this can be used to construct a quantum key distribution scheme that is secure even against eavesdroppers who can break the laws of quantum mechanics. The constraint is that any postquantum theory exploited by the eavesdropper must satisfy the no signalling principle. 
July2005


July
12: IQI Seminar Nicolas Cerf, University of Brussels 3:00, 74 Jorgensen Title: Capacity of bosonic Gaussian channels with memory Abstract: The bosonic quantum channels have recently attracted a growing interest, motivated by the hope that they open a tractable approach to the generally hard problem of evaluating quantum channel capacities. These studies, however, have always been restricted to memoryless channels. Here, it is shown that the classical information transmission rate of a bosonic Gaussian channel with memory can be significantly enhanced if entangled symbols are used instead of product symbols. For example, the capacity of a photonic channel with 70%correlated thermal noise of 1/3 the shot noise is enhanced by about 11% when using 3.8dB entangled light with a modulation variance equal to the shot noise. 
July
19: IQI Seminar Henri Verschelde, Ghent University 3:00, 74 Jorgensen Title: A tour of variational quantum field theory Abstract: We discuss the general problems encountered when trying to apply the variational principle to quantum field theory. We look at different ways to get around these problems and argue that recent advances in applying MPS (matrix product states) to condensed matter theory might provide a good general purpose variational technique for quantum field theory. 
July
20: IST Seminar Paul Rothemund, Caltech 3:00, 74 Jorgensen Title: DNA Origami Abstract: A key goal for bottomup nanofabrication has been to generate structures whose complexity matches that achieved by topdown methods. Towards this goal, DNA nanotechnology provides an attractive route. Here I describe a method for folding long single strands of DNA into arbitrary two dimensional target shapes using a raster fill technique. Selfassembled in a onepot reaction from the 7 kilobase genome of phage M13mp18 and more than 200 synthetic oligodeoxynucleotides, the shapes are roughly 100 nm in diameter and nearly 5 megadaltons in mass. (For comparison the eukaroytic ribosome, one of nature's most complex molecular machines, is 4.2 megadaltons in mass.) Experimental shapes approximate target shapes, such as a 5pointed star, with a resolution of 3.5 to 6 nm and may be decorated by arbitrary patterns at 6 nm resolution to form words or images. Enabled
by a program for laying out complicated designs and, utilizing inexpensive
unpurified oligodeoxynucleotides, this method helps move DNA nanotechnology
from the realm of research towards that of engineering. The ability to
create arbitrary shapes provides a new route to the bottomup nanofabrication
of complex nanoscale devices and instruments. Physicists and materials
scientists should be able to use DNA origami to arrange optical, electronic,
and mechanical components into novel materials or even an integrated "nanolaboratory"
of their choosing. Biologists may be able to use these structures to position
proteins and other biomolecules in precise arrangements to study their
coupling. Indeed these structures may be thought of as a versatile "nanobreadboard",
a simple platform for creating arbitrary nanostructures. 
July
26: IQI Seminar

August2005


August
2: IQI Seminar
Our goal is to improve the molecules' identification process by using the computing device to run "data compression" algorithms that reduce the entropy of certain spins. A bit with lower entropy is considered "cooler", and it provides a better signal when used for identifying molecules. Shannon's entropy bound tells us that the total entropy of the spins in a molecule is preserved. Therefore, cooling one spin is done at the expense of heating the others. Our "Algorithmic Cooling" employs data compression methods in *open systems*, thus reducing the entropy of spins far beyond Shannon's bound. Cooling of short molecules is experimentally feasible  we recently cooled spins of a threebit quantum computer beyond Shannon's entropy bound at the Technion NMR lab.

September2005


September
27: IQI Seminar

September
30: Special Condensed Matter Physics Seminar 
October2005


October
4: IQI Seminar The proof of a threshold for stabilizer operations proceeds similarly to the original threshold proof of Aharonov and BenOr (for codes of distance at least five). They recursively define a good code block to be a block with at most one bad subblock. We instead say a good block has a bad subblock with only a small probability. Thus instead of inducting forward on the error state of the system, we induct on a probability distribution over errors in the system. For magic
states distillation, we give a new method based on repeated distillation
of the parity code and its dual, similar to algorithmic cooling, which
slightly improves the set of distillable ancillas. 
October
11: IQI Seminar

October
18: IQI Seminar In a recent work with Jones and Landau, we derive an explicit, combinatorial algorithm that approximates the Jones polynomial for any primitive root of unity of order k. The algorithm is polynomial in the number of strands and crossings in the braid, and in k. The algorithm is based on a bunch of known mathematical results of about 20 years old, and in particular on Jones's unitary representation of the braid group. Our contribution is mainly in the understanding of how to adapt these pieces to the quantum computation setting, and to combine them together into a quantum algorithm. Due to the results of Freedman, Larsen and Wang, this algorithm solves a problem that is complete for quantum computation, namely, it is the hardest problem that can be solved by a quantum computer, up to polynomial reductions. It would be interesting to understand how to extend this algorithm in various directions, possibly in the context of approximating hard problems, such as the important challenge of approximating the partition function of the Potts model. I will explain the algorithm, and mention further directions. No understanding of any of the words in the abstract will be assumed...

October
25: IQI Seminar

November2005


November
1: IQI Seminar Pawel Wocjan, Caltech 3:00 pm, 74 Jorgensen Title: On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems Abstract: We consider an approach to deciding isomorphism of rigid nvertex graphs (and related isomorphism problems) by solving a nonabelian hidden shift problem on a quantum computer using the standard method. Such an approach is arguably more natural than viewing the problem as a hidden subgroup problem. We prove that the hidden shift approach to rigid graph isomorphism is hard in two senses. First, we prove that Omega(n) copies of the hidden shift states are necessary to solve the problem (whereas O(n log n) copies are sufficient). Second, we prove that if one is restricted to singleregister measurements, an exponential number of hidden shift states are required. 
November
8: IQI Seminar Wim van Dam, UCSB 3:00 pm, 74 Jorgensen Title: Quantum computing, zeroes of zeta functions & approximate counting Abstract: In this talk I describe a possible connection between quantum computing and Zeta functions of finite field equations that is inspired by the 'spectral approach' to the Riemann conjecture. The assumption is that the zeroes of such Zeta functions correspond to the eigenvalues of finite dimensional unitary operators of natural quantum mechanical systems. To model the desired quantum systems I use the notion of universal, efficient quantum computation. Using eigenvalue estimation, such quantum systems are able to approximately count the number of solutions of the specific finite field equations with an accuracy that does not appear to be feasible classically. For certain equations (Fermat hypersurfaces) I show that one can indeed model their Zeta functions with efficient quantum algorithms, which gives some evidence in favor of the proposal. Ref.: arXiv:quantph/0405081 
November
15: IQI Seminar Patrick Hayden, McGill University 3:00 pm, 74 Jorgensen Title: Quantum information's first family, revisited Abstract: It's been almost two years since Devetak, Harrow and Winter introduced their "mother" and "father" protocols into quantum information theory. In their paper, almost all of the many varieties of capacity and distillation protocols that had been previously been devised in quantum information theory were organized into two sets of children, those descended from the mother and those descended from the father. In this talk, I'll sketch a new and very simple proof of the mother protocol. Along the way, she'll reveal herself to be even more powerful than previously thought. In addition to generating optimal entanglement distillation protocols, I'll show how she provides a straightforward proof of the HorodeckiOppenheimWinter negative information result and can be used as a building block for the distributed compression of quantum data. In her new, more powerful form, the mother protocol even generates the father. The original two sets of children are thereby reduced to one and our understanding of quantum information theory is radically simplified: by starting with a single maximally quantummechanical protocol and transforming it in a few simple ways we can accomplish most of the tasks of interest in twoparty quantum information processing. 
November
22: IQI Seminar Yaoyun Shi, University of Michigan 3:00 pm, 74 Jorgensen Title: Simulating quantum computation by contracting tensor networks Abstract: Are quantum computers truly more powerful than classical ones, or any quantum computation can be simulated efficiently classically? While most of us believe the former, the possibility for the latter is not yet ruled out in theory. In this talk, I will present a general classical algorithm for simulating quantum computation. The treewidth of a graph is a useful combinatorial measure on how close the graph is to a tree. We prove that a quantum circuit with T gates whose underlying graph has treewidth d can be simulated classically in TO(1)*exp(O(d)) time, which, in particular, is polynomial in T if d = O(logT). Among many implications, we show efficient simulations for quantum formulas, defined and studied by Yao (Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 352361, 1993), and for logdepth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also extend the result to show that oneway quantum computation of Raussendorf and Briegel (Physical Review Letters, 86:51885191, 2001), a universal quantum computation scheme very promising for its physical implementation, can be efficiently simulated by a randomized algorithm if its quantum resource is based on a smalltreewidth graph. To our knowledge, this work makes the first connection of treewidth and quantum computation, and our simulation results appear difficult to obtain using previous methods. This is
a joint work with my colleague Igor Markov. 
November
29: IQI Seminar Federico Spedalieri, JPL 3:00 pm, 74 Jorgensen Title: Highfidelity linear optical quantum computing with polarization encoding Abstract: We show that the KLM scheme [Knill, Laflamme and Milburn, Nature {\bf 409}, 46] can be implemented using polarization encoding, thus reducing the number of path modes required by half. One of the main advantages of this new implementation is that it naturally incorporates a loss detection mechanism that makes the probability of a gate introducing a nondetected error, when nonideal detectors are considered, dependent only on the detector darkcount rate and independent of its efficiency. Since very low darkcount rate detectors are currently available, a highfidelity gate (probability of error of order $10^{6}$ conditional on the gate being successful) can be implemented using polarization encoding. The detector efficiency determines the overall success probability of the gate but does not affect its fidelity. This can be applied to the efficient construction of optical cluster states with very high fidelity for quantum computing. 
December2005


December
6: IQI Seminar Shengyu Zhang, Princeton 3:00 pm, 74 Jorgensen Title: New upper and lower bounds for randomized and quantum Local Search Abstract: The Local Search problem, which finds a local minimum of a blackbox function on a given graph, is of both practical and theoretical importance to many areas in combinatorial optimization, complexity theory and quantum computing. In this paper, we give both new lower and upper bound techniques for randomized and quantum query complexities of Local Search. The lower bound technique works for product graphs. Applying the technique to the Boolean hypercube B^n and the constant dimensional grids [n]^d, two particular types of product graphs that recently draw much attention, we get the following tight results: RLS(B^n)
= Theta(2^{n/2} n^{1/2}) where RLS(G)
and QLS(G) are the randomized and quantum query complexities of Local
Search on G, respectively. These improve the previous results by Aaronson
[STOC'04], and Santha and Szegedy [STOC'04]. (paper available at the author's homepage: www.cs.princeton.edu/ ~szhang ) 
December
13: IQI Seminar Dave Bacon, University of Washington 3:00 pm, 74 Jorgensen Title: Wasting away in hidden subgroup ville Abstract: Recently there has been a flurry of exciting activity in understanding quantum algorithms for the nonabelian hidden subgroup problem. In this talk I will discuss a variant of this problem, which I call the hidden subgroup conjugacy problem and how this problem is related to the recent progress in the hidden subgroup problem. If this talk is successful, everyone will leave the talk thinking of working on this variant of the hidden subgroup problem. Which is much better than just wasting away in hidden subgroup ville. 
December
20: IQI Seminar The socalled
de Finetti representation theorem can be seen as a solution to this problem.
Basically, it states that the assumption on the independence can be replaced
by a weaker assumption, namely that the probability distribution of the
outcomes of infinitely many This result has been generalized to the quantum case. More precisely, it has been shown that any quantum state on infinitely many subsystems which is invariant under permutations of the subsystems is a mixture of product states. In the talk, we show that the same is (approximately) true if one considers quantum states on only finitely many subsystems. This has many interesting implications. In particular, it leads to a new understanding of the security of quantum cryptography.

January2006


January
10: IQI Seminar Matthew Hastings, Los Alamos National Laboratory 3:00 pm, 74 Jorgensen Title: LiebSchultzMattis in higher dimensions Abstract: In 1961, Lieb, Schultz, and Mattis showed the absence of a gap in a class of onedimensional spin chains: chains with halfinteger spin per unit cell and SU(2)invariant shortrange interactions. This basic result has guided research on spins chains ever since. For example, the discovery of the Haldane gap in chains with integer spin was surprising as it indicated a fundamental difference between integer and halfinteger spins. Since then, there has been much work searching for higher dimensional extensions of this result, in particular due to possible connections to hightemperature superconductivity. The clearest statement of the basic physical reasons to expect such an extension are due to Misguich et. al, who argued that any such system would either have longrange spin order, and hence have gapless spin wave excitations, or else would have a class of topological excitations with vanishing gap. Thus, showing this result in higher dimensions would connect directly to recent ideas on topological order in quantum systems. I will sketch my recent proof of this result, emphasizing connections to these basic physical ideas. In the process, I will derive various results about locality of correlation functions in these systems. 
January
17: IQI Seminar David PerezGarcia, Max Planck Institute for Quantum Optics 3:00 pm, 74 Jorgensen Title: The world of Matrix Product States: a work in progress Abstract: Matrix Product States (MPS) have been proven to be very useful in the understanding of classical simulation of quantum systems in 1D. Moreover, in 2D, fenomena like criticality, topological behavior, universal one way quantum computers and NPhardness appear even in the simplest cases. This nontrivial behavior contrasts with the simple representation that one has for the MPS, and encourages us to study MPS in depth: how powerful are they? How can they be constructed in a lab? Which are their basic properties? Apart from the 1D case with open boundary conditions or an infinite chain, very few is known about the structure of MPS. They aim of our work (still in progress) will be to understand and try to solve the above questions, and maybe others. Work in collaboration with: F. Verstraete, M. Wolf and I. Cirac 
January
24: IQI Seminar Robin BlumeKohout, Caltech 3:00 p.m., 74 Jorgensen Title: Accurate quantum state estimation via "Keeping the Expert Honest" Abstract: I'll present a new general procedure for estimating the density matrix produced by an apparatus. Our most important result is a unique measure of an estimate's goodness  or "honesty". We derive it from the simple observation that lying isn't nice, and shouldn't be rewarded. Rather surprisingly, this leads to a unique procedure for analyzing measurement data. Since our procedure is different from the prevailing technique (tomography plus MaximumLikelihood Estimation), I'll try to point out why our "Honest State Estimation" is better than MLE. Finally, I'll outline a practical method for doing it. This talk should (I hope) be of especial interest to experimentalists working with fewquanta systems. 
January
31: IQI Seminar Scott Parkins, University of Auckland 3:00 p.m., 74 Jorgensen Title: Dicke quantum phase transition in an optical cavity QED system Abstract: The Dicke Model of an ensemble of twostate atoms interacting collectively with a single quantized mode of the electromagnetic field (without the standard rotating wave approximation) exhibits a zerotemperature quantum phase transition to a superradiant state at a critical atomcavity coupling strength; characteristic order parameters are the mean photon number and atomic inversion. Here I put forward a proposal based on multilevel atoms and cavitymediated Raman transitions to realise an effective Dicke system operating in the phase transition regime. Cavity fluorescence provides a measurable output channel from the system and its properties display a variety of signatures of critical behavior in the transition regime. The scheme appears feasible with existing experimental parameters in both the fewatom and manyatom limits and offers possibilities for investigations of quantum entanglement around phase transitions. Variations of the scheme also enable one to engineer a variety of effective interactingspin systems which also exhibit quantum phase transitions and critical behavior of entanglement. 
February2006


February
7: IQI Seminar Andrew Cross, MIT 3:00 p.m., 74 Jorgensen Title: A bound on the accuracy threshold for trappedion quantum computing Abstract: Quantum systems with finite coherence times can be used to perform arbitrarily long quantum computations if the decoherence rate is less than the accuracy threshold. This threshold has been shown to scale inversely with the scale factor "radius" r of a logical qubit when gates are only permitted to interact neighboring qubits. However, while r can be estimated from theory, its precise value in an explicit geometry (with realistic local interactions) has never been calculated before. I will describe a planar geometry based on experimentally demonstrated elements of a trappedion quantum computer, in which r is determined, allowing a good estimate for the threshold to be found. Qubits are placed onto this geometry to reduce the distance between qubits that frequently interact. Faulttolerant gates using nondeterministic ancilla preparation networks for the [[7,1,3]] code are scheduled to reduce the number of qubit movement operations. Pessimistically assuming a maximum number of ancilla preparation attempts, the scale factor r is found to be less than 460. On the other hand, if storage failure rates are neglected, the threshold is found to be greater than 10^{6}, suggesting a scale factor of no less than 20 for this geometry and errorcorrection network Joint work
with Tzvetan Metodi and Isaac Chuang. 
February
14: IQI Seminar Krysta Svore, Columbia University 3:00 p.m., 74 Jorgensen Title: A bound on the accuracy threshold for trappedion quantum computing Abstract: We consider a model of quantum computation in which the set of operations is limited to nearestneighbor interactions on a 2D lattice. For this model we design a faulttolerant coding scheme using the concatenated $[[7,1,3]]$ Steane code. Our architecture is potentially applicable to iontrap and solidstate quantum technologies. We calculate a lower bound on the faulttolerance threshold for our local model using a detailed analytical failure probability map. Our analysis represents the first detailed lower bound calculation for both the nonlocal and local settings that accounts for all types of locations present in a quantum circuit. We obtain a rigorous lower bound around 1.7 x $10^{5}$ for the local setting, where memory errors are set to onetenth of the failure probability of gates, measurement, and preparation, and around 3.3 x $10^{5}$ for the analogous nonlocal setting. In addition, we derive a tighter lower bound for the nonlocal setting given in \cite{AGP:thresh} of $4.3 \times 10^{5}$. Joint work
with David DiVincenzo and Barbara Terhal, IBM 
February
21: IQI Seminar Jonathan Walgate, University of Calgary 3:00 p.m., 74 Jorgensen Title: Two distinct indistinguishability results Abstract: Multipartite quantum states can become physically indistinguishable when the parties sharing them are restricted to local operations orchestrated via classical communication (LOCC). This holds true even for orthogonal states, which are always distinguishable using a joint measurement, implying that some physical information about the system is not localized in its parts. The study of local indistinguishability is the study of this information. In this talk I will prove two simple theorems, the first primarily concerning product states and the second entangled states. In each case a straightforward result leads to some counterintuitive phenomena.
First, I prove there is a limit to local indistinguishability. All sets of pure quantum states, no matter how complex, can be rendered perfectly locally distinguishable when correlated to an ancilla in a complementary set of nonorthogonal states. This theorem implies an odd phenomenon: the optimal global and local protocols for distinguishing the same set of orthogonal product states may involve different kinds of measurements, performed upon different subspaces. Subspaces that are globally irrelevant can become locally indispensable.
Second, I prove that orthogonal sets of pure quantum states are completely locally indistinguishable only if all the states are entangled. This phenomenon is exhibited by the complete Bell basis, but also by incomplete subsets of GHZ bases, which have their own curious local structure. 
February
28: IQI Seminar Joseph F. Traub, Columbia University 3:00 pm, 74 Jorgensen Title: Qubit complexity of continuous problems Abstract: For the foreseeable future the number of qubits will be a crucial computational resource. We show how to lower bound the qubit complexity using the classical query complexity. We use this result to present a simple problem which cannot be solved on a quantum computer in the standard quantum setting with deterministic queries but can be solved on a classical computer using randomized queries (Monte Carlo). This suggests introducing a quantum setting with randomized queries. We apply this setting to high dimensional integration and to path integration. In particular, there is an exponential improvement in the qubit complexity of path integration using the quantum setting with randomized queries. We end by
discussing future directions and where to learn more. 
March2006


March
3: IQI Special Seminar Luming Duan, University of Michigan 4:00 p.m., 74 Jorgensen Title: Quantum simulation of manybody physics with ultracold atoms Abstract: Coherent control of ultracold atoms provides a powerful platform for quantum simulation of strongly correlated manybody physics. In this talk, I will show how to describe strongly interacting fermionic atoms (under a Feshbach resonance) in an optical lattice, how to introduce competition to probe more exotic quantum phases, and how to reconstruct the full correlation function of ultracold atoms through Fourier sampling of the timeofflight images. At the end of the talk, I will also briefly discuss probabilistic quantum computation, its associated error threshold and implementation. 
March
21: IQI Seminar Sergey Bravyi, IBM, Watson Research Center 3:00 pm, 74 Jorgensen Title: Local Hamiltonians and ArthurMerlin games Abstract: Evaluation of the ground state energy of quantum manybody systems with local interactions is a problem of great importance for many areas of physics. A suitably formalized decision version of this problem is known as "Local Hamiltonian Problem" (LHP). We study complexity of LHP in a special case when all interactions have nonpositive matrix elements in the standard product basis. It is shown that this LHP belongs to the complexity class AM  a probabilistic analogue of NP with two rounds of communication between a prover and a verifier. Apart from that, we prove that ground states of some translationinvariant Hamiltonians within the specified class obey the area law for entanglement entropy. Our proof is based on the KirkwoodThomas description of a ground state. This is a joint work with Barbara Terhal and David DiVincenzo. 
March
28: IQI Seminar Carlos Mochon, Perimeter Institute 3:00 pm, 74 Jorgensen Title: Hamiltonian oracles Abstract: Hamiltonian oracles are the continuum limit of the standard unitary quantum oracles. In addition to being a potentially useful tool in the study of standard oracles, Hamiltonian oracles naturally introduce the concept of fractional queries and are amenable to study using techniques of differential equations and geometry. As an example of these ideas we shall examine the Hamiltonian oracle corresponding to the problem of oracle interrogation. This talk is intended for all those who wish to apply their knowledge of differential geometry without the risk of creating an event horizon. 
April
4: IQI Seminar Matthias Christandl, University of Cambridge 3:00 p.m., 74 Jorgensen Title: Oneandahalf quantum de Finetti theorems Abstract: We prove a new kind of quantum de Finetti theorem for representations of the unitary group U(d). Consider a pure state that lies in the irreducible representation U_{mu+nu} for Young diagrams mu and nu. U_{mu+nu} is contained in the tensor product of U_mu and U_nu; let xi be the state obtained by tracing out U_nu. We show that xi is close to a convex combination of states Uv, where U is in U(d) and v is the highest weight vector in U_mu. When U_{mu+nu} is the symmetric representation, this yields the conventional quantum de Finetti theorem for symmetric states, and our method of proof gives nearoptimal bounds for the approximation of xi by a convex combination of product states. For the class of symmetric Werner states, we give a second de Finettistyle theorem (our 'half' theorem); the de Finettiapproximation in this case takes a particularly simple form, involving only product states with a fixed spectrum. Our proof uses purely group theoretic methods, and makes a link with the shifted Schur functions. It also provides some useful examples, and gives some insight into the structure of the set of convex combinations of product states. This is joint work with Robert Koenig, Graeme Mitchison, Renato Renner and available at quantph/0602130. 
April
11: IQI Seminar Cindy Regal, JILA, University of Colorado 3:00 p.m., 74 Jorgensen Title: Studying the BCXBEC crossover regime with a Fermi gas of ^{40}K atoms Abstract: Recent years have seen the emergence of an intriguing Fermi system achieved with ultracold atomic gases. With these systems it is possible to widely tune the swave interatomic interaction strength using a Feshbach resonance. Of particular interest is the strongly interacting regime (1 < 1/kF a < 1) where a crossover between BCS theory of superconductivity and BoseEinstein condensation (BEC) of molecules occurs. Recently experiments with 6Li and 40K have succeeded in studying many aspects of this superfluid Fermi system. In my talk I will present recent experiments we have performed at JILA on this Fermi system using 40K. I will focus on studies of the phase diagram of the system as well as a measurement of the momentum distribution of a Fermi gas in the BCSBEC crossover. 
April
13: IQI Special Seminar Martin Zwierlein, MIT 1:30 p.m., 308 Firestone Title: Observation of hightemperature superfluidity in a gas of fermionic atoms Abstract: Ultracold quantum degenerate Fermi gases provide a remarkable opportunity to study strongly interacting fermions. In contrast to other Fermi systems, such as superconductors, neutron stars or the quarkgluon plasma of the early Universe, these gases have low densities and their interactions can be precisely controlled over an enormous range. A major goal has been the realization of superfluidity in a gas of fermions. Our observation of vortex lattices in a strongly interacting rotating Fermi gas provide definitive evidence for superfluidity. By varying the binding energy between fermion pairs, we have studied the crossover from a BoseEinstein condensate of molecules to a BardeenCooperSchrieffer superfluid of loosely bound pairs. Scaled to the density of electrons in a solid, this new form of superfluidity would occur already far above room temperature. Recently, we have extended these studies to interacting Fermi gases with imbalanced spin populations and observed a quantum phase transition at a critical imbalance, which is the Pauli limit of superfluidity. 
April
25: IQI Seminar YiKai Liu, UCSD 3:00 p.m., 74 Jorgensen Title: Two Results on the Consistency of Local Density Matrices Abstract: Suppose we have an nqubit system, and we are given a collection of local density matrices rho_1,...,rho_m, where each rho_i describes a subset C_i of the qubits. We say that rho_1,...,rho_m are "consistent" if there exists some global state sigma (on all n qubits) that matches rho_1,...,rho_m on the corresponding subsets C_1,...,C_m. We prove two results about the consistency problem. First, if rho_1,...,rho_m are consistent with some state sigma > 0, then they are also consistent with a "Gibbs state" of the form sigma' = (1/Z) exp(M_1+...+M_m), where each M_i is a Hermitian matrix acting on the subset C_i. This was previously proved by Jaynes (1957) in the context of the maximumentropy principle; here we give a somewhat different proof, using properties of the partition function. Second,
we show that the consistency problem is QMAhard; in particular, we give
a randomized polytime Turing reduction from the Local Hamiltonian problem.
We do not know of any way to get this result using only a mapping reduction.
This gives an interesting example of a computationally hard problem in
the class QMA (which is the quantum analogue of NP). 
May
2: IQI Seminar Mason Porter, Caltech 3:00 p.m., 74 Jorgensen Title: BoseEinstein Condensates in Optical Lattices and Superlattices Abstract: BoseEinstein condensates (BECs), formed at extremely low temperatures when particles in a dilute gas of bosons condense into the ground state, have generated considerable excitement in the atomic physics community, as they provide a novel, experimentallycontrollable regime of fundamental physics. In this talk, I will discuss my research on the macroscopic dynamics of coherent structures in BECs loaded into optical lattice and superlattice potentials, for which I employ methods from dynamical systems and perturbation theory. Using Hamiltonian perturbation theory, I will give an analytical construction of wavefunctions (observed in recently reported experiments) whose spatial periodicity is an integer multiple of the lattice period. I will also discuss BECs in superlattice potentials and how to manipulate solitary waves controllably with appropriate temporal adjustments of such potentials. Time permitting, I will briefly discuss more recent work on parametric excitation of BECs and work in progress on BECs with inhomogeneous (spacedependent) scattering lengths. 
May
9: IQI Seminar Seth Lloyd, MIT 3:00 p.m., 74 Jorgensen Title: Quantum gravity from quantum computation: observational consequences Abstract: This talk reviews the recently proposed theory of quantum gravity based on quantum computation, and discusses the theory's predictions for the back reaction of the metric to computational `matter,' black hole evaporation, holography, and quantum cosmology. 
May
26: CMP Seminar Michael Levin, MIT 12:00 p.m., 107 Downs Title: Probing order beyond the Landau paradigm Abstract: For many years, it was thought that Landau's theory of symmetry breaking could describe essentially all phases and phase transitions. Then, in 1982, the limitations of Landau theory were exposed in a dramatic way with the discovery of the fractional quantum Hall (FQH) effect. The FQH states contain a new kind of order  known as "topological order"  that is fundamentally beyond the Landau paradigm. Topological order cannot be understood using symmetry breaking, order parameters, or long range order. This poses an interesting theoretical problem: these states must contain some kind of structure that is responsible for their unusual physical properties. But what is this structure and how can we probe it without order parameters? In my talk, I will describe recent progress in answering this question. I will show that topological order is intimately connected with nonlocal quantum entanglement. I will introduce a new quantity  called "topological entropy"  that measures precisely this nonlocal entanglement. 
June
6: IQI Seminar Serge Massar, University of Brussels 3:30 p.m., 74 Jorgensen Title: Fiber optics protocols for quantum communication Abstract: We show how the techniques developed for long distance quantum key distribution in optical fibers can be used to demonstrate other quantum information processing and communication protocols. We present a fiber optics realization of the DeutschJozsa and BernsteinVazirani algorithms. We describe a method, called "error filtration", for reducing errors in quantum communication channels, and present an experimental implementation thereof. We discuss the cryptographic primitive of string flipping, and present an experimental implementation which has higher security than achievable using any classical protocol. 
June
13: IQI Seminar Dominik Janzing, University of Karlsruhe 3:00 p.m., 74 Jorgensen Title: Molecular heat engines and their similarity to logical circuits Abstract: I consider hypothetical molecular heat engines that extract work from a pair of quantum systems having different temperatures by performing a unitary transformation on the joint system. In this setting, thermodynamically optimal heat engines correspond to transformations that can be quite complex, and the ability to extract work on the molecular level is closely related to the ability to compute. This link is particularly clear when both quantum systems consist of several twolevel systems (bits). In the generic case, the extractable work can be maximized only by Boolean functions that correspond to proper multibit operations. This implies lower bounds on their logical depth. For a pair of three level systems with appropriate level spacing one can show that the optimal heat engine is a universal gate for classical computation. Finally, the optimal heat engine on several twolevel systems with different energy gaps solves the NP complete problem KNAPSACK. The results
indicate that there is a tradeoff relation between complexity and thermodynamical
efficiency of molecular heat engines. 
June
20: IQI Seminar Peter Love, Haverford College 3:00 pm, 74 Jorgensen Title: Quantum computation for quantum chemistry Abstract: The major known applications of quantum computation are factoring, unstructured search and simulation of quantum systems. In this talk I shall discuss the application of quantum computation to problems in quantum chemistry. I will show under what conditions quantum computers can perform full configuration interaction (FCI) calculations of ground state energies of molecules efficiently. Possible future experimental implementations of these calculations for small molecules will also be described. 
June
27: IQI Seminar Tobias Osborne, University of Bristol 3:00 pm, 74 Jorgensen Title: Simulating quantum spin systems Abstract: There are only a handful of efficient heuristics to find ground state properties of quantum spin systems which appear to work well in practice. One particularly wellknown example is the densitymatrix renormalisation group (DMRG). Unfortunately, however, little is known about the correctness and worstcase complexity of the DMRG and relatives. In this talk I'd like to discuss the computational complexity of the problem of computing certifiable approximations to the ground state of a quantum spin system. I'll describe recent results based on the LiebRobinson bound and quasiadiabatic continuation that show that one can provably obtain a representation of the ground state of a class of lowdimensional quantum spin systems with polynomial computational resources. 
Oct
3: IQI Seminar Stephen Hsu, University of Oregon 3:00 pm, 74 Jorgensen Title: Discreteness and the origin of probability in quantum mechanics Abstract: Attempts to derive the Born rule, either in the Many Worlds or Copenhagen interpretation, are unsatisfactory for systems with only a finite number of degrees of freedom. In the case of Many Worlds this is a serious problem, since its goal is to account for apparent collapse phenomena, including the Born rule for probabilities, assuming only unitary evolution of the wavefunction. For finite number of degrees of freedom, observers on the vast majority of branches would not deduce the Born rule. However, discreteness of the quantum state space, even if extremely tiny, may restore the validity of the usual arguments. 
Oct
17: IQI Seminar Rolando Somma, LANL 3:00 pm, 74 Jorgensen Title: Optimal quantum measurements Abstract: The standard method to obtain expectation values of observables and unitary operators of a quantum system consists of preparing many copies of the desired state, and measuring the corresponding quantity by coupling the quantum system to an apparatus. The precision of the measured value using this method is known to scale as 1/sqrt(N), where N indicates the number of copies (experiments). In this talk, I will show that, with a minimal prior knowledge about the operator whose expectation value is to be measured, such a precision can be increased to 1/N. For this purpose, I will consider different variations of the phase estimation algorithm according to the quantity that is to be measured. These algorithms are particularly useful for simulating quantum systems on quantum computers, enabling efficient measurement of observables and correlation functions. 
Oct
24: IQI Seminar Paul Goldbart, University of Illinois 3:00 pm, 74 Jorgensen Title: Superconducting quantum interference eevices at the nanoscale Abstract: SQUIDs, and other superconducting circuitry, can now be fabricated at the nanoscale by depositing suitable metals on to individual molecules, such as DNA and carbon nanotubes [1]. In this talk I shall describe how nanoscale superconducting devices are made and how they operate. I shall pay particular attention to the intrinsic electrical resistance of these devices, especially their sensitivity to magnetic fields and patterns of supercurrent. These particular features hint at possible uses of nanoscale SQUIDs, such as for mapping the phase of the superconducting order parameter and testing for superconducting correlations in novel materials and settings [3]. As we shall see, simple models, rooted in the classic approaches to electrical resistance in Josephson junctions and superconducting wires, are capable of providing a quantitative understanding of the properties of nanoscale SQUIDs [2]. [1] D.S.
Hopkins, D. Pekker, P.M. Goldbart and A. Bezryadin, Quantum interference
device made by DNA templating of superconducting nanowires, Science 308,
176265 (2005). 
October
27: CMP Seminar Jason Petta, Princeton 12:00 pm, 107 Downs Title: Preparing, manipulating and measuring quantum states on a chip Abstract: Semiconductor quantum dots are versatile systems for studying few electron physics. In this talk I will describe our recent experimental efforts to coherently control spin states in a few electron double quantum dot. By separating a spin singlet state onchip, we measure an ensemble averaged spin dephasing time T2* of 10 ns, limited by the contact hyperfine interaction with the GaAs host nuclei. We develop quantum control techniques based on the exchange interaction to correct for hyperfine dephasing. Coherent spin state rotations are achieved, including spin SWAP. By using a spinecho pulse sequence based on the exchange interaction we extend the spin coherence time, T2 beyond 1.2 microseconds. Current efforts to implement a twoqubit gate and to control the coupling between the electron and nuclear spin systems will be presented. 
Oct
31: IQI Seminar Iordanis Kerenidis, CNRSUniversity of Paris 3:00 pm, 74 Jorgensen Title: Quantum vs. classical oneway communication complexity Abstract: The first exponential separation between quantum and randomized oneway communication complexity was proved by BarYossef, Jayram, Kerenidis [BJK04] for the Relational Hidden Matching Problem. They proved that the quantum oneway communication complexity of this relation is O(log n), yet any randomized oneway protocol with bounded error must use Omega(\sqrt{n}) bits of communication. It was an open question to prove a similar exponential separation for a partial function instead of a relation. Here, we
define a boolean version of the Hidden Matching Problem and give a tight
lower bound of Omega(\sqrt{n}) for its randomized oneway communication
complexity. Since there is a quantum oneway protocol of O(log n) qubits
for this problem, we obtain an exponential separation of quantum and classical
oneway communication complexity for partial functions. I will also
describe some implications of our result for the bounded storage model
of cryptography and privacy amplification in key distribution protocols.
This is joint work with Dmitry Gavinsky, Julia Kempe, Ran Raz and Ronald
de Wolf. 
Nov
7: IQI Seminar Jake Taylor, MIT 3:00 pm, 74 Jorgensen Title: Quantum control of coupled spins in a mesoscopic environment Abstract: Isolated spins in solid state devices are promising systems for implementing ideas from quantum information science. However, any solid state system will be coupled to nearby degrees of freedom, such as the lattice nuclear spins of the host material. In this talk we explore approaches for robust control of localized spin systems in such a mesoscopic environment, with a focus on electron spins in quantum dots and color centers. We develop methods for mitigating decoherence, improving quantum operations, using the nuclear spin environment as a resource, and engineering longrange interactions. Finally, implications for the realization of faulttolerant quantum information processing will be discussed. 
November
14: IQI Seminar Steve Flammia, University of New Mexico 3:00 pm, 74 Jorgensen Title: What's Entanglement Good For? Abstract: Entanglement is one of the most studied features of quantum mechanics and in particular quantum information. Yet its role in quantum information is still not clearly understood. Results such as (R. Josza and N. Linden, Proc. Roy. Soc. Lond. A 459, 2011 (2003)) show that entanglement is necessary, but stabilizer states and the GottesmanKnill theorem (for example) imply that it is far from sufficient. I will discuss two aspects of entanglement. First, a quantum circuit with a vanishingly small amount of entanglement that admits an apparent exponential speedup over the classical case. Then I will discuss the role of entanglement in quantum metrology. Specifically, I will present a new proof that entangling ancillas can make no difference to the accuracy of a quantum parameter estimation, regardless of the nature of the coupling Hamiltonian. Finally, I will conclude by discussing strategies for improving the scaling of quantum parameter estimation and experimental prospects for achieving these fundamental limits. 
November
17: CMP Seminar Zohar Nussinov, Washington University in St. Louis 12:00 pm, 107 Downs Title: Generalized symmetries and finite temperature topological orders Abstract: We prove sufficient conditions for topological order (TO) at finite temperatures. These conditions rely on the existence of "gauge like symmetries" (GLSs) which generally lie halfway between global and local symmetries. Such symmetries appear in numerous systems: the Kitaev model, orbitaldependent spin exchange Hamiltonians in 3d orbital systems, JahnTeller effects in transition metal compounds, liquid crystalline phases of Quantum Hall systems, p+ip superconducting arrays, Bose metals, some theories of glasses, sliding Luttinger liquids (stripes), and solvable frustrated spin systems with a deconfined quantum critical point. These GLSs (and perturbations about them) allow us to go beyond standard topological field theories to engineer new physical models with robust finite temperature TO. 
November
28: IQI Seminar Bryan Eastin, University of New Mexico 12:00 pm, 107 Downs Title: Ancillae with homogeneous errors Abstract: Ancillary state construction is a necessary component of quantum computing. Ancillae are required both for error correction and for performing universal computation in a faulttolerant way. Computation to an arbitrary accuracy, however, is effectively achieved by increasing the number of qubits in order to suppress the variance in the expected number of errors. Thus, it is important to be able to construct very large ancillary states. Concatenated quantum coding provides a means of constructing ancillae of any size, but, this fact aside, concatenation is not a particularly efficient form of coding. More efficient codes exist, but these codes lack the substructure of concatenated codes that enables faulttolerant preparation of large ancillae. In this talk I will discuss the advantages of coding in large blocks, both from the perspective of efficiency and analysis, and I will describe my progress in developing construction procedures for moderately large ancillae. 
December
5: IQI Seminar Nicolas Menicucci, Princeton 3:00 pm, 74 Jorgensen Title: The sound of inflation: phonon correlations in a chirped ion trap Abstract: Inflation has become a cornerstone of modern cosmology, including among its achievements the ability to explain the initial density fluctuations necessary for the formation of cosmic structures, like galaxies. It is argued that quantum fluctuations get "frozen out'' during inflation and become classical density fluctuations after reheating, and that these density fluctuations provide the initial conditions for all structure formation, including the detected anisotropy of the cosmic microwave background (CMB). This hypothesis is hard to test in a repeatable setting. Ion traps provide a manageable system with which we can study the acoustic analogues of inflationary processes, including the "freezing out'' of quantum fluctuations. Similar work has been done with BoseEinstein condensates, but ion traps have the added advantage of precision control and local phonon readout with individual ions. Using standard quantum mechanics, spatial correlations in the detected excitation of ions' electronic states can be shown to be a function of quantum correlations in the initial state of the phonon field. This is work in progress with Gerard Milburn. An introduction to inflationary cosmology and ion traps will be included. 
December
12: IQI Seminar Debbie Leung, University of Waterloo 3:00 pm, 74 Jorgensen Title: Quantum Network Coding  the butterfly and beyond Abstract: We study the communication of quantum information in networks of (directed) quantum channels. We consider the asymptotic rates of high fidelity quantum communication between specific senderreceiver pairs. In networks that are shallow, we find that rerouting of quantum information is optimal. Consequently, the achievable rate regions are given by counting edge avoiding paths, and precise achievable rate regions can be obtained. Slight twists to the above results are obtained when side classical channels are available. These complete solutions apply to many networks, including the butterfly network. Joint work
with Jonathan Oppenheim and Andreas Winter 