Seminar Abstracts

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

2000
2001
 Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
 Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
2002
2003
 Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
 Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov 2004

 2001 March Mar. 29: Special Seminar      Andris Ambainis, Berkeley      4:00 p.m., 102 Steele Title: Lower bounds on quantum computing Abstract: Quantum computation is an exciting new field which touches on the foundations of both computer science and quantum mechanics. It provides a new model of computation that is both physically reasonable and more powerful than conventional (classical) 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. Host: Leonard Schulman April Apr 27: IQI Seminar      Lorenza Viola, LANL      3:30 p.m., 102 Steele Title: Theory (and practice) of noiseless quantum subsystems Abstract: Noiseless subsystems provide a general tool for realizing the emergence of noise-protected degrees of freedom in open quantum systems. Starting from the simplest prototype example based on three symmetric spin 1/2 particles, I will show how noiseless subsystems can be defined for generic open-system evolutions and how they allow a unified understanding of existing noise control strategies. Special attention will be devoted to the connections between noiseless subsystems and quantum error-correcting codes. Finally, I will describe an experimental implementation via nuclear magnetic resonance of the above three spin noiseless subsystem to demonstrate the preservation of one qubit against collective noise. Host: John Preskill May May 4: IQI Seminar      Gerard Milburn, University of Queensland      3:30 p.m., 102 Steele Title: Quantum computation in linear bosonic and fermionic interferometers Abstract: Two qubit gates for photons are generally thought to require exotic materials with huge optical nonlinearity. I will describe a scheme that uses only linear optical interferometers to implementing reliable quantum algorithms. The scheme requires: two qubit gates that only work conditionally, near deterministic teleportation, single photon sources, and fast electro-optics feedforward. I will discuss one proposed single photon source based on the surface acoustic wave guiding of single electrons. The scheme can be extended to linear fermionic interferometers. Host: John Preskill May 11: IQI Seminar      Debbie Leung, IBM Watson Research Center      3:30 p.m., 102 Steele Title: Hiding classical data in quantum states Abstract: We consider methods to encode a classical secret as a quantum state shared by two parties, such that the secret is still hidden even if the two parties communicate classically but is opened if the two parties perform joint quantum operations. This exhibits a hiding capability stronger than is possible in any classical scheme. This capability originates from known rules of entanglement manipulations. General methods to derive upper and lower bounds of the information obtained by the two sharers will be described, and applied to prove the security of a proposed scheme. Other questions concerning the security and implementation, and extensions to this proposed scheme will be discussed. Host: John Preskill May 25: IQI Seminar      Alexei Kitaev, Microsoft Research      3:30 p.m., 102 Steele Title: Some results about parallel quantum computation Abstract: Parallelism of quantum computation can be quantified by circuit depth. I consider a model in which unitary operations are performed by braiding sufficiently nontrivial anyons; the reduction between this model and the standard circuit model is size- and depth-effective both ways. It is shown that computation with depth $O(\log n)$ is equivalent to measuring the anyonic charge in a (specially shaped) domain of polynomial size. Host: John Preskill June June 1: IQI Seminar      Michael Nielsen, University of Queensland      3:30 p.m., 102 Steele Title: Entanglement and universal quantum computation Abstract: What interactions are required to simulate arbitrary dynamics in a composite quantum system? I explain an efficient algorithm to simulate any desired Hamiltonian evolution using any single fixed entangling Hamiltonian and local unitary evolution. It follows that universal quantum computation can, in principle, be performed using any system with an entangling interaction and the ability to do local unitary operations. Host: John Preskill July August August 3: IQI Seminar      Yoshihisa Yamamoto, Edward L. Ginzton Laboratory, Stanford      3:30 p.m., 102 Steele Title: Generation and detection of triggered single photons Abstract: A source of single photons, each arriving within a known time interval, and high-efficiency/low-noise single photon counters, would be useful in the new fields of quantum key distribution and quantum computation with photonic qubits. In this talk, I will discuss our method or generating triggered single photons based on a single InAs quantum dot in a three-dimensional microcavity. The system is also expected to produce an entangled EPR-Bell photon pair. I will also describe efficient and low-noise detection of single photons with an As-doped Si avalanche detector. Host: Hideo Mabuchi August 24: IQI Seminar      Tommaso Calarco, University of Innsbruck      3:30 p.m., 102 Steele Title: Dynamical and holonomic quantum computation with quantum optical systems         T. Calarco, L.-M. Duan, D. Jaksch, A. Recati, I. Cirac and P. Zoller Abstract: We present and compare several schemes, among those recently developed by our group, for the scalable implementation of quantum computation by using atomic systems (either neutral or charged, i.e. ions) in microscopic potentials (optical lattices, magnetic and electromagnetic microtraps). First, we review schemes based on conditional dynamical phase shifts, obtained by means of different kinds of interactions (cold collisions, dipole-dipole interactions, electrostatic forces) either with single atoms/ions or with atomic ensembles. Then we discuss more recent proposals exploiting non-Abelian phases generated by quantum holonomies, either with trapped ions or neutral atoms. Host: Hideo Mabuchi September October 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 Novemeber November 1: Preskill group meeting      Lawrence Ip, Berkeley      5:30 p.m., 156 Jorgensen Title: Finding unknown shifts and hidden cosets: or how to fix a quantum hubble space         telescope Abstract: We present a class of shift problems with efficient quantum algorithms. This class of problems includes the Shifted Legendre Symbol Problem considered by van Dam and Hallgren. We show that shift problems, just like hidden subgroup problems, have direct links to well studied problems in signal processing. Host: Leonard Schulman November 7: IQI Seminar      Ronald de Wolf, UC Berkeley      3:00 p.m., 102 Steele Title: Quantum communication complexity: some recent results Abstract: In the setting of communication complexity, Alice receives an input x, Bob receives an input y, and together they want to compute some function f(x,y), while minimizing the amount of communication between them. In recent years, it has been found that quantum communication is much more efficient than classical communication for various functions. In this talk we will discuss three quantum communication complexity results that were obtained the past year: (1) quantum fingerprinting, which gives rise to an exponential quantum-classical improvement in a constrained communication model; (2) a precise algebraic characterization of a "non-deterministic" variant of quantum communication complexity; (3) slightly improved bounds for the bounded-error quantum communication complexity of the disjointness problem (whose complexity is one of the main open problems in qcc). This talk is based on 2 papers: H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, "Quantum Fingerprinting", Physical Review Letters, 87(16), September 2001, quant-ph/0102001 P. Hoyer and R. de Wolf, "Improved Quantum Communication Complexity Bounds for Disjointness and Equality", quant-ph/0109068 Host: John Preskill November 13: IQI Seminar      Wim van Dam, UC Berkeley      3:00 p.m., 74 Jorgensen **NOTE NEW LOCATION** Title: Playing games against theories: the statistical strength of arguments against locality Abstract: I will analyze the strength of a nonlocality argument in the setting of a game between an experimental physicist and an inventive believer in local theories. The experimentalist tries to collect evidence that the Bell inequality is indeed violated by Nature, whereas the local theorist tries to come up with local explanations of the observed phenomena. In a sense, this game can never be won completely by either party because there is always a local theory in combination with the argument that we just witnessed an unlikely, yet possible, series of outcomes. Clearly, the more experiments we do the more improbable such explanations become. It will be this 'increase of unlikeliness per experiment' that I will consider the strength of the nonlocality argument. To quantify this, I will look at the Kullback-Leibler distance between the probabilities that the theory of quantum mechanics predicts and the set of probability distributions stemming from the set of local theories. The local theory that comes closest to quantum mechanics is the strongest argument in favour of locality, whereas the experimental physicist tries to widen this gap. We thus reach a setting very familiar in the theory of zero-sum games where one party tries to minimize the quantity that the other party attempts to minimize. For a given nonlocality inequality, the 'strategy' of the physicist is determined by the probability distribution over the measurement settings that are involved. The optimal strategy is thus the one that establishes the largest possible Kullback-Leibler distance, which in turn defines the value of the nonlocality argument. Using this analysis I will consider a number of Bell inequalities and will present a tentative ranking of them. Host: John Preskill November 21: Mathematical Physics Seminar      Mary Beth Ruskai, University of Massachusetts Lowell      12:00 - 1:00 p.m., 351 Sloan (Lounge) Title: Capacity of noisy quantum channels Abstract: Quantum particles can be used to transmit classical information, typically encoding messages as strings of 0 and 1 represented by a pair of input states from a two level quantum system or "qubit". As with classical communication, channels may have noise, and the capacity is a measure of the maximum information per bit that can be transmitted. The Holevo capacity measures the information per bit that can be transmitted through a memoryless channel when product inputs are used, but entangled measurements are permitted to determine the output. It is known that this can be strictly greater than the capacity restricted to product measurements and that, in such cases, the optimal input states are generally not orthogonal. It is somewhat surprising that that there are situations for which the optimal inputs are not a pair of states, but a triplet of non-orthogonal states. This does NOT mean that a single photon or spin 1/2 particle can be used to send information distinguishing between 3 possible inputs, but that more information can be transmitted using long strings when the product inputs are chosen from among three states. 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 shrinks the sphere to an ellipsoid. This picture can be useful for understanding how the two competing quantities contributing to the capacity can be optimized, and can explain our construction of channels for which three inputs are needed. It also shows the fundamental difference between unital channels, which are essentially classical and non-unital channels which show a rich variety of quantum effects. 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. Host: Barry Simon November 27: IQI Seminar      Andris Ambainis, Berkeley      3:00 p.m., 74 Jorgensen Title: Generating quantum states and quantum communication complexity Abstract: Consider the following two communication problems. The first is to generate (or approximate) a bipartite quantum state. The second is computing a classical function (or sampling from a classical probability distribution) using quantum communication. In both cases, we try to minimize the amount of communication needed. 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. Ta-Shma, U. Vazirani, A. Wigderson. Quantum communication complexity of sampling. FOCS'98. The second result is new. Host: Leonard Schulman November 29: IQI Seminar      Scott Aaronson, Berkeley      2:00 p.m., 100 Powell-Booth Title: Quantum lower bound for the collision problem Abstract: The collision problem is to decide whether a function X:{1,..,n}-> {1,..,n} is one-to-one or two-to-one, given that one of these is the case. We show a lower bound of Theta(n^{1/5}) on the number of queries needed by a quantum computer to solve this problem with bounded error probability. The best known upper bound is O(n^{1/3}), but obtaining any lower bound better than Theta(1) was an open problem since 1997. Our proof uses the polynomial method augmented by some new ideas. We also give a lower bound of Theta(n^{1/7}) for the problem of deciding whether two sets are equal or disjoint on a constant fraction of elements. Finally we give implications of these results for quantum complexity theory. Host: John Preskill December December 18 : IQI Seminar      Andrei Soklakov, University of London      3:00 p.m., 74 Jorgensen Title: Variational principles of physics from the point of view of inductive inference Abstract: This talk is an overview of a recent proposal to establish a formal connection between the fundamental principles of physics and those of inductive inference. Given a physical system, we construct a hypothesis space as a collection of all possible laws that define system dynamics. Using the methods of algorithmic information theory we introduce the notion of complexity of a dynamical law. We show that the celebrated principle of least action can be viewed as a consequence of Occam's Razor principle. We speculate how the laws of quantum dynamics may arise in the context of Solomonoff's induction theory. We suggest that both physics and compute science may benefit from the proposed approach. The technical part of the talk is directly relevant to the general theory of induction by Occam's razor. Host: John Preskill 2002 January January 15: IQI Seminar      Andrew Doherty, Caltech       3:00 p.m., 74 Jorgensen Title: Distinguishing separable and entangled states Abstract: Although it is straightforward to define a separable quantum state as a mixture of product states, it is not known in general how to decide whether any given mixed state is in fact separable. I will discuss some new families of operational criteria that distinguish entangled from separable quantum states. The simplest of these tests is the well-known Peres-Horodecki or positive partial transpose criterion and the more complicated tests are strictly stronger. The new criteria are tractable due to powerful computational and theoretical methods for a class of convex optmization problems, termed semidefinite programs, that have found broad applicability in fields such as control theory. I will discuss theoretical background and perspectives on semidefinite programs that might have wider application in quantum information theory. Host: John Preskill January 22 : IQI Seminar      Antonio Acin, University of Geneva         3:00 p.m., 74 Jorgensen Title: Distillability and Bell inequalities in N qubit systems Abstract: We analyze the relation between distillability and Bell inequality violation. We consider quantum systems composed of N qubits, and the family of all Bell correlation inequalities for N qubits with two local measurements per site. If a N-qubit state violates any of these inequalities, then it is bipartite distillable. Host: John Preskill January 29 : IQI Seminar      Andreas Winter, University of Bristol         3:00 p.m., 74 Jorgensen Title: How much information is obtained by a quantum measurement? Abstract: We study the problem of separating the data produced by a given quantum measurement, described by a positive operator valued measure (POVM) acting on a state ensemble, into a "meaningful'' (intrinsic) and a "not meaningful'' (extrinsic) part. After reviewing the existing results on this problem, we propose a new notion of this separation, which appears to be the strongest possible, and which encompasses the previous notions: it is an asymptotic version of the convex decomposition of a POVM into extremal ones. The central results are: a data separation theorem, achieving the same rate of intrinsic data as the compression result of this paper's precursor [A. Winter and S. Massar, Phys. Rev. A, vol. 64, 012311, 2001], which is the Holevo mutual information of a particular ensemble associated to the measurement and the source average state, and the optimality of this result in the form of a strong converse. We apply this result to a similar decomposition of quantum instruments and quantum operations, in their Kraus form. This is used to give a refined notion of the entropy exchange of a quantum map. Other applications include a rederivation of the Holevo information bound and a first version of the Quantum Reverse Shannon Theorem. Host: John Preskill February February 5 : IQI Seminar      Alexei Kitaev, Caltech         3:00 p.m., 74 Jorgensen Title: Anyons for quantum computation Abstract: Anyons are special particles that occur in certain two-dimensional systems (e.g. in fractional quantum Hall systems). They feature unusual statistics and quantum numbers. I will describe a simple model with Abelian anyons, a mathematical version of which is known as the toric code. The existence of anyons is related to the ground state degeneracy on the torus. In general, this degeneracy is not exact, but the energy level splitting is exponentially small in the system size. With less trivial non-Abelian anyons, a degenerate state occurs when several particles are positioned on the plane far apart from each other. This provides an exciting possiblility of decoherence-protected quantum memory. Read-out 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 fault-tolerant 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: Consider a party at Caltech in which miraculously there happened to be exactly the same number of men and women. How can we generate a uniform superposition over all possible matchings of men with women for the swing couple dances that are being planned? Host: Leonard Schulman 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 all-powerful, 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 two-sided error (for prover's probability to win) is equivalent a game with one-sided 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 non-relativistic 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, non-abelean gauge theories and even field theories in curved space-times. 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 long-distance 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 single-photon 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 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 self-evident 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 non-local 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      Barbara Kraus, University of Queensland         3:00 p.m., 74 Jorgensen Title: Separable, distillable and activatable states Abstract: We introduce a formalism that connections entanglement witnesses and the distillation and activation properties of a state. We apply this formalism to two cases: First, we rederive the results presented in {\bf quant-ph/0104095} \cite{Eg01} by Eggeling et al., namely that one copy of any bipartite state with non--positive partial transpose (NPPT) is either distillable, or activable. Second, we show that there exist three--partite NPPT states, with the property that two copies can neither be distilled, nor activated. Host: John Preskill April 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 time-varying 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)$-unique-SVP 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 trade-off between information gain and state disturbance in quantum measurement. I'll end by describing a probability-free 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:math-ph/0202035 Host: John Preskill May 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). [2] G. Giedke and J.I. Cirac, submitted to Phys. Rev. A, quant-ph/0204085. Host: John Preskill June June 4: IQI Seminar      Jonathan Dowling, JPL      3:00 p.m., 74 Jorgensen Title: Projective Measurements and Linear Optics: For Fun and Profit Abstract: Heisenberg-limited measurement protocols can be used to gain an increase in measurement precision over classical protocols. Such measurements can be implemented using, e.g., optical Mach-Zehnder interferometers and Ramsey spectroscopes. We address the formal equivalence between the Mach-Zehnder interferometer, the Ramsey spectroscope, and the discrete Fourier transform. Based on this equivalence we introduce the quantum "Rosetta stone''. Large photon-number path entanglement is an important resource for Heisenberg-limited measurement protocols. We present a general constructive protocol to create any large photon number path-entangled 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_0|0> + c_1|1> + c_2|2>) without destroying it. This quantum nondemolition device can be used to create practical, efficient, quantum repeaters, employing double-photon guns, for long-distance optical quantum communication. The guns create polarization-entangled photon pairs on demand. One such source might be a semiconducter quantum dot, which has the distinct advantage over parametric down-conversion that the probability of creating a photon pair is close to one, while the probability of creating multiple pairs vanishes. The swapping and purifying components are implemented by polarizing beam splitters and probabilistic optical CNOT gates. 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 n-dimensional 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 problems on other spaces as well. 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 Einstein-Podolsky-Rosen 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 Hughston-Jozsa-Wootters). 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 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 known---if 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 read-only 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 and the required amount of entanglement in the teleportation can be easily derived from the above decomposition. 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 two-dimensional 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 two-dimensional systems it is a measure of entanglement. Host: John Preskill August September 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. Host: John Preskill September 27: IQI Special Seminar      *Friday*      Jose Latorre, University of Barcelona      2:00 p.m., location TBD Title: Majorization and quantum algorithms Abstract: Majorization theory establishes a far more refined relation of order between probability distributions than the concept of entropy. The solutions to quite a number of problems in quantum information have been proven to rely on majorization relations. We shall show that the known efficient quantum algorithms do carry a step-by-step majorization in their computational basis. Host: John Preskill October 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 Labs-Research      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      Yasser Omar, University of Oxford      3:00 p.m., 74 Jorgensen Title: Entanglement transfer and entanglement concentration using particle statistics Abstract: Using two pairs of entangled particles we show that particle indistinguishability can enforce a transfer of entanglement from the internal to the spatial degrees of freedom without any interaction between these degrees of freedom. Moreover, sub-ensembles selected by local measurements of the path will in general have different amounts of entanglement in the internal degrees of freedom depending on the statistics (either fermionic or bosonic) of the particles involved. 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      Andrew Childs, MIT      3:00 p.m., 74 Jorgensen Title: Exponential algorithmic speedup by quantum walk Abstract: We construct an oracular problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our oracular setting. We then show how this quantum walk can be used to solve our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve this problem with high probability in subexponential time. Host: John Preskill November 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 two-player cooperative games of incomplete information, which provide a framework in which various aspects of non-locality can be investigated. These games are also interesting since they arise in the study of multi-prover 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 multi-prover 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 two-player 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 well-studied 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 information-theoretic purposes, entanglement measures and ways of scaling systems to enable asymptotic developments. We propose ways in which these may be generalized to the Lie-algebraic setting, and to a lesser extent to the convex-cones setting. One of our original motivations for this program is to understand the role of entanglement-like concepts in condensed matter. We discuss how our work provides tools for analyzing the correlations involved in quantum phase transitions and other aspects of condensed-matter 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 cheat-sensitive 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 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, Ludwig-Maximilians University Munich      3:00 p.m., 74 Jorgensen Title: Computational model underlying the one-way quantum computer Abstract: We have demonstrated that a class of entangled multi-particle states, the cluster states, can serve as one-way quantum computers (QCc). The QCc is a scheme of universal quantum computation that consists only of one-qubit 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-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 so-called continuous variables offers a promising alternative to its finite-dimensional 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 continuous-variable 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: 2-D 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 Temperley-Lieb 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: Z2-gauge theory, Pfaffian phase, a universal system for quantum computation, ... . For more information see the posting: "A magnetic model with a possible Chern-Simons phase on quant-ph", 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 one-to-one correspondence between a subclass of remote state preparation protocols to private quantum channels (protocols that encrypt quantum messages using a classical secret key). 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 micro-coherences 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-2003 February 4: IQI Seminar      Dominic Mayers, University of Sherbrooke, Canada      3:00 p.m., 74 Jorgensen       Title: Composing quantum protocols Abstract: We provide a general technique to prove the security of quantum protocols that have subprotocols. For example, there are unconditionally secure classical protocols for a task called authentication, but these protocols require a short shared private key. To generate this private key, we can use quantum key distribution as a subprotocol. Are these authentication protocols still unconditionally secure if we replace the ideal private key by a call to quantum key distribution? This is only one example of a composability question. We will explain the general technique and use the above as an example. 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 phase-like transitions when correlations become classical. February 18: IQI Seminar      Michael Keyl, TU-Braunschweig      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, TU-Braunschweig      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-2003 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 many-particle entanglement in symmetric spin 1/2 systems paying particular attention to both the microscopic structure of the entanglement and its robustness to entanglement-damaging processes. In order to gain a better physical picture of many-particle 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 many-particle 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 spin-squeezed states). Finally, we connect our analysis to our ongoing experiments involving a symmetric ensemble of laser cooled Cs atoms. March 20-21: 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 super-positions, effectively performing actions on all instances of the problem at a time. An obstacle in the way of implementing quantum algorithms is de-coherence 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 two-state quantum system, or qubit. We discuss a model of multi-bit quantum systems and basic operations performed on them. The next part concerns de-coherence 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 error-correcting codes, the so-called stabilizer or symplectic codes. A stabilizer code Q is constructed from a pair of classical codes CGF(4) whose weight enumerators correspond to the weight enumerators of Q. We will compute the parameters of stabilizer codes, define their decoding, mention bounds on the size of stabilizer and other quantum codes, define quantum error detection, and show a way to use stabilizer codes to bound error exponents of an arbitrary quantum discrete memory-less channel. We will introduce most of the technical tools needed to derive the results. Some familiarity with linear algebra, coding and information theory, matrix groups as well as ignorance in quantum mechanics will help to easier understand the material. Bio: Alexander Barg (M'00-SM'01) received the M.Sc. degree in mathematics and the Ph.D. degree in information theory (the latter from the Institute for Information Transmission Problems (IPPI) Moscow, Russia) in 1987. He has been a Senior Researcher at IPPI since 1988. He spent years 1995-1996 at the Technical University of Eindhoven, Eindhoven, The Netherlands. From 1997 to 2003 he was with the Fundamental Mathematics Research Department of Bell Labs, Lucent Technologies, Murray Hill, NJ, on leave from the IPPI. He is currently with the Division of Applied Sciences at Harvard University. His research interests include coding and information theory and its links with mathematics. March 27: IQI Group Meeting      Oliver B. Downs (Olly), Princeton University & Analytical Insights, Inc.      10:00 a..m., 156 Jorgensen Title: The tunneling salesman - Novel ideas on global optimization I'd like to take this opportunity to talk about something somewhat off-the-wall, not directly about Machine Learning, or about conventional ideas in Optimization, but which I think embodies the principle of taking simple and elegant ideas and intuition, and applying them to a novel set of problems - with an interesting outcome. In this work I present a novel method for global optimization, exploiting the mathematics of quantum mechanics, and in particular the tunneling phenomenon. I use the fact that the ground state of a quantum system can be proven to localize to the global minimum of its potential, to determine the global minimum of any smooth (polynomial) cost function. Solution for this ground state requires the use of a basis function expansion, and it is the number of basis functions required which controls the complexity of the algorithm. Theoretically, this requirement has an exponential upper bound, but empirically the use of basis functions is significantly sparser. I show encodings of the integer bi-prime factoring and traveling salesman (and hence all NP-hard) problems in terms of finding the global minimum of a quartic polynomial cost function. The Tunneling Salesman algorithm is demonstrated on one- and two-dimensional toy problems (for visualization), and applied to factoring bi-primes with 10s of bits. A (somewhat out of date) technical report on this work can be downloaded from: http://www.research.microsoft.com/research/pubs/view.aspx?tr_id=620 This work is the basis of my PhD thesis dissertation. April-2003 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 pair-interaction Hamiltonians in n node quantum networks where the subsystems are qudits. We show that any pair-interaction 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 short-range interactions. We construct a nearest-neighbor Hamiltonian whose ground states encode the solutions to the NP-complete 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 non-trivial 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 half-vortices, 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 half-vortices 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 non-abelian 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 subexponential-time quantum algorithm for the dihedral hidden subgroup problem Abstract: I will discuss a quantum algorithm for the dihedral hidden subgroup problem with time and query complexity C^\sqrt{n}. By contrast the classical query complexity of DHSP is O(\sqrt{N}). The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins with the quantum character transform on the group, just as for other hidden subgroup problems. Then it tensors irreducible representations of D_N and extracts summands to obtain target representations. Finally, state tomography on the target representations reveals the hidden subgroup. April 10: Preskill Group Meeting      Greg Kuperberg, UC Davis      5:30 p.m., 156 Jorgensen Title: Hybrid quantum memory and its capacity Abstract: What is the most general possible kind of memory consistent with quantum mechanics? The only commonly considered kinds are qudits and classical digits, but a hybrid modelled by an arbitrary C^*-algebra is more generally possible. Modulo certain reasonable assumptions, this is as general as it gets. Assuming this model, when is one hybrid memory worth more than another? I will give a characterization of when many copies of a memory A embed (or blindly encode with perfect fidelity) into slightly more copies of another memory B. In particular, either there is such an embedding, or A admits a state that does not visibly encode into B with high fidelity. The second half of this alternative depends on a novel Holder inequality for hybrid memories that generalizes the classical pigeonhole principle. April 15: IQI Seminar      Robin Blume-Kohout, LANL      3:00 p.m., 74 Jorgensen Title: Decoherence from an unstable environment Abstract: Chaotic evolutions exhibit exponential sensitivity to initial conditions. This suggests that even very small perturbations resulting from weak coupling of a quantum chaotic environment to a system whose state is a superposition of eigenstates of the coupling Hamiltonian will lead to rapid decoherence. We analyze decoherence due to a "toy'' quantum environment that is analytically solvable, yet displays the crucial phenomenon of sensitivity to perturbation. We show that such an environment, with a single degree of freedom, can be far more effective at destroying quantum coherence than a heat bath with infinitely many degrees of freedom. 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 Abstract: A Gaussian version of the entanglement of formation adopted to bipartite Gaussian continuous variables systems is introduced by considering decompositions into pure Gaussians only. We show that this quantity is an entanglement monotone and provide a simplified computation for states of arbitrary many modes. For the case of one mode per site the remaining variational problem is solved analytically. If the considered state is in addition symmetric with respect to interchanging the two modes, we prove additivity of the considered entanglement measure and show that it is indeed equal to the true entanglement of formation. The latter is achieved by connecting EPR-like uncertainties to pure state entanglement for two-mode squeezed states. It is the first instance in which the entanglement of formation has been determined for genuine continuous variable systems. 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-2003 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      Ben Schumacher, Caltech      4:00 p.m., 201 E. Bridge Title: What is information? Abstract: Quantum information theory forces us to reconsider just what we mean by the term "information". Is there a more general physical idea of information that encompasses both quantum and classical concepts? This talk will try to present such a view. An information theory is a theory of the reversibility (or approximate reversibility) of state changes under a restricted set of feasible operations. Within quantum mechanics, there can be several distinct reasonable choices for the feasible set, and therefore several inequivalent concepts of "information". But these different types of information must share certain "categorical" features. We can also adapt this approach to ask, "What is computation?" From the standpoint of physics, computation must be based on the ability of one dynamical evolution to simulate another. A few observations on the general idea of simulation will be presented. 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-2003 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 operator-valued measures. There are no pure photon qubits, and no exactly orthogonal qubit states. Reduced density matrices for the spin of massive particles are well-defined, 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-2003 July 8: IQI Seminar      Michael Nielsen, University of Queensland      3:00 p.m., 74 Jorgensen Title: Entanglement and correlation in ground states of many-body systems Abstract: How can we characterize the entanglement and, more generally, the correlations in the ground state of a complex, many-body 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 non-degenerate quantum error-correcting 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 many-body quantum systems. July 15: IQI Seminar      Gerardo Ortiz, LANL      3:00 p.m., 74 Jorgensen Title: Entanglement as an observer-dependent 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 information-theoretic 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 distinguishable-subsystem framework, generalized entanglement also provides novel tools for probing quantum correlations in strongly interacting many-body 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: Non-gaussian quantum cloning of gaussian states Abstract: It has been known for some time that a phase-independent 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 *non-gaussian* cloning map gives rise to a 2.5 % improvement on this fidelity. The possible implications of this result on the non-gaussian attacks of continuous-variable 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 dipole-dipole 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 two-qubit 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 d-dimensional 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-2003 September 2: IQI Seminar      Michael Ben-Or, 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 one-way quantum communication complexity of 2-universal hash functions, and a Disturbance/Adversary-Information-Compression trade-off for this protocol. With these, we can show that with two-way 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 Hoi-Kwong 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 error-correction 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-2003 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 information-theoretic 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 non-contextual, 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 two-way and intrinsic three-way 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 Kochen-Specker 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 one-way 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 super-dense coding. Moreover, the parent protocols may be recovered from the children by "making them coherent". November-2003 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 time-dependent properties of the ground state and low energy excitations in generic one-dimensional quantum many-body systems. November 11: IQI Seminar      Daniel Gottesman, Perimeter Institute      3:00 p.m., 74 Jorgensen Title: The minimum distance problem for two-way entanglement purification Abstract: Entanglement purification protocols (EPPs) with one-way classical communications are equivalent to quantum error-correcting 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 two-way classical communications are known to be substantially more powerful than one-way 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 two-way 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 two-way EPPs can be better than any quantum error-correcting code in this scenario, and give examples of two-way EPPs that exceed both the quantum Hamming bound and the quantum Singleton bound. We also show that two-way 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 Gilbert-Varshamov bound, allowing only half the error rate for the same data rate. This is joint work with Andris Ambainis. November 12: Special IQI Seminar      Dominic Berry, Macquarie University, Australia      1:00 p.m., 114 E Bridge Title: Improving single photon sources via linear optics and photodetection Abstract: Many quantum information applications rely on the production of a single photon. In practice, single photons are generated with non-unit efficiency; that is, the actual state is a mixture of vacuum with a single photon. In order to obtain a high probability of a single photon, one may attempt to improve the source, or perform post-processing of the source to improve the efficiency. A promising method of performing post-processing is via linear optics and photodetection. I will present results showing that it is possible to improve the probability of a single photon using this method, and examine the limits to this method. November 13: Group Meeting      Lawrence Ip      5:30 p.m., 156 Jorgensen Title: Shor's Algorithm is Optimal Abstract: We show that the 'standard' quantum algorithm for the abelian hidden subgroup problem is not only efficient but is optimal in the information theoretic sense, in that it maximizes the probability of correctly identifying the hidden subgroup. The proof uses semidefinite programming to show that the standard algorithm implements the optimal set of measurements. 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      Alexander Klyachko, Bilkent University, Turkey      3:00 p.m., 74 Jorgensen Title: Dynamic symmetry approach to entanglement Abstract: We discuss new approach to entanglement, based on dynamic symmetry group, which treats it as a manifestation of quantum fluctuations. This puts entanglement into a broader context, eventually applicable to all quantum systems, sheds new light on known results providing for them a unified conceptual framework, opens a new prospect for further development of the subject, reveals its unexpected connections with other branches of physics and mathematics, and finally provides an insight on properties of environment in which entangled state can be stable. 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 Ta-Shma. January-2004 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 Gross-Pitaevskii 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 Gross-Pitaveskii result. In the second order the evolution will be still described by Gross-Pitavskii 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,T-invariant topological phases of correlated electrons Abstract: I will describe an approach to understanding the effective field theories associated with some P,T-invariant topological phases of correlated electrons, which have possible application to fault-tolerant 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 super-dense coding to prepare arbitrary quantum states instead of only classical messages. We also derive single-letter 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 Deutsch-Jozsa algorithm was implemented and the Cirac-Zoller 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-2004 March 2: IQI Seminar      Norbert Lütkenhaus, University of Erlangen-Nü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 co-enrichment 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      Hoi-Kwong 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, Ben-Or 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 Ben-Or's proof and extend it to a bit error rate of 11 percent for BB84 with only one-way classical communications. This error rate coincides with Shor-Preskill'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 Ben-Or.] March 16: IQI Seminar      Sergey Bravyi, Caltech      3:00 p.m., 74 Jorgensen Title: Entanglement theory for fermionic modes Abstract: We apply a subsystem-independent generalization of entanglement developed by Barnum, Knill, and Ortiz to a system of fermionic modes. In this approach unentangled states describe non-interacting 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 high-school 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 one-way communication complexity Abstract: We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem and prove that its quantum one-way communication complexity is $O(\log n)$, yet any randomized one-way protocol with bounded error must use $\Omega({\sqrt{n}})$ bits of communication. No asymptotic gap for one-way communication was previously known. The hidden matching problem also provides the first exponential separation between Simultaneous messages with public coins and quantum Simultaneous Messages. April-2004 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 long-standing 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 BCS-type superfluidity to Bose-Einstein 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 two-particle bound molecular state exists, thereby entering the BEC-BCS crossover regime. The experiments open the intriguing possibility to address questions of modern solid state physics with an atomic-physics 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 length-scale of the system. The role of these observable is also discussed in the context of NMR quantum information processing and bulk quantum state tomography. May-2004 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 steady-state 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 spin-cooling technique that employs data-compression 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 high-sensitivity 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 single-photon sources produce the vacuum state with non-negligible 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 Lieb-Thirring inequality, other less well-known 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 Glauber-Sudarshan P-function. We have succeeded in the teleportation of a squeezed state, which is a non-classical state. To make a quantum teleportation network among three parties, we have succeeded in preparing a fully inseparable tripartite continuous-variable 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. June-2004 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 (quant-ph/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: Large-scale 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. November-2004 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 real-space renormalization group approach. In my talk I'll introduce the real-space 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: Long-range 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 fault-tolerant 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 long-range localizable entanglement in a noisy three-dimensional cluster state. The partially decohered state is modeled by the thermal state of a suitable translation-invariant short-range 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 speed-up. 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. January-2005 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 h-cobordant 4-manifolds can not be distinguished by unitary TQFTs (obeying reasonable gluing axioms.) February-2005 February 1: IQI Seminar      Stefano Pironio, Caltech      3:00 p.m., 74 Jorgensen          Title: Bell inequalities and the communication cost of simulating non-locality Abstract: To reproduce non-local 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 non-local correlations violate Bell inequalities. Further, we demonstrate that to each set of non-local 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 multi-letter 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 single-letter characterization is also given. The second theorem is a multi-letter 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 quant-ph/0501045. I conclude by mentioning a full four-dimensional 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. March-2005 March 1: IQI Seminar      Hoi-Kwong Lo, University of Toronto      3:00 p.m., 74 Jorgensen Title: Practical decoy state quantum key distribution Abstract: We will present the general theory for decoy state quantum key distribution as well as a specific two-decoy-state protocol for practical quantum key distribution. There has been much interest in quantum key distribution. Experimentally, quantum key distribution over 150 km of commercial Telecom fibers has been successfully performed. The crucial issue in quantum key distribution is its security. Unfortunately, all recent experiments are, in principle, insecure due to real-life imperfections. Here, we propose a method that can for the first time make most of those experiments secure by using essentially the same hardware. Our method is to use decoy states to detect eavesdropping attacks. As a consequence, we have the best of both worlds---enjoying unconditional security guaranteed by the fundamental laws of physics and yet surpassing substantially even some of the best experimental performances reported in the literature. Finally, we present a specific two-decoy-state protocol and discuss the optimal choice of decoy states and the issue of statistical fluctuations. 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 many-body systems, such as the study of the ground-state correlations in the spin-1/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). [2] R. Somma, G. Ortiz, H. Barnum, E. Knill, L. Viola (2004), PRA v.70 p.1 (2004). 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 quant-ph/0501090. April-2005 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 (cond-mat/0309120, Phys. Rev. Lett. 94, 066401 (2005)). May-2005 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 single-photon sources, but present implementations primarily utilize weak coherent pulses, which can produce vulnerable multi-photon signals. The decoy state method, introduced by Hwang [PRL 91, 057901 (2003)] and made rigorous by Lo et al. [quant-ph/0411004], provides a way to characterize the quantum communication channel with current technology detectors by varying the signal intensities and thus identify how many single-photon 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 free-space 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 space-time is a construct, derived from the underlying quantum computation. Explicit mechanisms are provided for the back-reaction of the metric to computational 'matter,' black-hole 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 Superfluid-Mott 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 non-computable 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 un-founded 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 superfluid-Mott insulator quantum phase transition. June-2005 June 7: IQI Seminar      Cristopher Moore, University of New Mexico      4:30 p.m., 74 Jorgensen Title: Multiregister Fourier sampling and subexponential-time 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 worst-case to average-case 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 Sum-related approach to building subexponential-time 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 non-separable 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 post-quantum theory exploited by the eavesdropper must satisfy the no signalling principle. July-2005 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.8-dB 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 bottom-up nanofabrication has been to generate structures whose complexity matches that achieved by top-down 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. Self-assembled in a one-pot 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 5-pointed 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 bottom-up nanofabrication of complex nano-scale 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 "nano-laboratory" 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     Martin Roetteler NEC Laboratories      3:00, 74 Jorgensen Title: New Tales of the Mean King Abstract: The Mean King's problem asks to predict the outcome of a measurement which is randomly selected from a set of mutually complementary observables. The challenge is to make this prediction right away without actually knowing the observable, i.e., the information which observable was chosen is revealed only later in time. I will review this problem and offer a combinatorial solution which works whenever the system's dimension is a power of a prime number. More generally, I will show that whenever an affine resolvable design exists, then a state reconstruction problem similar to the Mean King's problem can be defined and solved. As an application of this general framework we consider a state reconstruction problem which can be solved using Hadamard designs. Using a different approach we show > that if the dimension of the system is large, the measurement result in the Mean King's problem as well as the secretly chosen measurement basis can be inferred with high probability. This can be achieved even when the mean-spirited King is unwilling to reveal the measurement basis at any point in time. August-2005 August 2: IQI Seminar     Tal Mor, Technion, Israel      3:00, 74 Jorgensen Title: From quantum computers to identification of molecules Abstract: In this talk I will suggest the first near-future application of quantum computing devices, "Algorithmic Cooling". I will explain how simple quantum algorithms, and novel entropy manipulations (that go far beyond Shannon's entropy bound), can be combined in order to improve identification of molecules. Molecules are built from atoms, and the nucleus inside each atom has a property called spin. The spin can be understood as the orientation of the nucleus, and when put in a magnetic field, certain spins are binary, either up (ZERO) or down (ONE). Several such bits (inside one molecule) represent a binary string -- a register. A macroscopic number of such registers/molecules are monitored in parallel, as done, for instance, in Magnetic Resonance Imaging (MRI). The device that monitors and manipulates these bits/spins is considered a simple "computing" device. 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 three-bit quantum computer beyond Shannon's entropy bound at the Technion NMR lab. September-2005 September 27: IQI Seminar      Daniel Lidar, USC      3:00, 74 Jorgensen Title: Are the assumptions of fault-tolerant quantum error correction internally consistent? Abstract: We critically examine the internal consistency of a set of minimal assumptions entering the theory of fault-tolerant quantum error correction for Markovian noise. We point out that these assumptions may not be mutually consistent in light of rigorous formulations of the Markovian approximation. Namely, Markovian dynamics requires either the singular coupling limit (high temperature), or the weak coupling limit (weak system-bath interaction). The former is incompatible with the assumption of a constant and fresh supply of cold ancillas, while the latter is inconsistent with fast gates. We discuss ways to resolve these inconsistencies. September 30: Special Condensed Matter Physics Seminar      Michael Freedman, Microsoft Research      4:00, 114 East Bridge Title: Some thoughts about 2 dimensional physics in general and the nu=5/2 fractional quantum Hall state in particular Abstract: I’ll begin with some abstractions about topological quantum field theory and explain what looks special about 2+1 dimensions. We’ll then look at this in the context of quantum computation. Finally, I’ll come to my ( current ) favorite system FQHE at nu=5/2. I’ll discuss how that system might function as a quantum computer and what some of the theoretical obstacles are (The experimental obstacles being, presumably, to numerous to mention!) October-2005 October 4: IQI Seminar      Ben Reichardt, Berkeley      3:00, 74 Jorgensen Title: Threshold for the distance three Steane quantum code Abstract: The error threshold is the model-dependent noise rate which we can tolerate and still compute to arbitrary accuracy. We prove the existence of a constant threshold for the seven qubit, distance three Steane quantum code. The proof first obtains a threshold for arbitrarily accurate stabilizer operations, then uses magic states distillation (distillation of certain noisy ancillas) to gain universality. The proof of a threshold for stabilizer operations proceeds similarly to the original threshold proof of Aharonov and Ben-Or (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      Lawrence Schulman, Clarkson University      3:00, 74 Jorgensen Title: Quantization of discrete breathers in doped alkali halides Abstract: Discrete breathers are localized excitations on lattices. Nonlinear interactions lead to oscillation frequencies outside the phonon bands. When these breathers occur in a quantum context the system may survive 10^9 times its natural time scale and may be a medium suitable for quantum information. To evaluate this possibility the level structure and quantum stability of the excitation must be studied. The physical system that I focus on is a doped alkali halide in which the breather is created when it acquires a Jahn-Teller-induced distortion. For the level structure, I use EBK quantization, a multi-dimensional generalization of WKB. The issue of stability has been the subject of controversy and I show the breather to be stable against all but tunneling, using both path integral and numerical diagonalization methods. October 18: IQI Seminar      Dorit Aharonov, Hebrew University      3:00, 74 Jorgensen Title: The quantum algorithm for approximating the Jones polynomial Abstract: Kitaev, Freedman, Larsen and Wang showed several years ago that topological quantum computation, based on anyons and topological quantum field theory (TQFT), is equivalent in computational power to the standard quantum computation model. TQFT is known to be strongly related to the Jones polynomial (defined for knots or braids) and so these results implicitly imply a quantum algorithm to approximate the Jones polynomial at the fifth root of unity. The exact specification of the quantum algorithm was not done, as far as we know. 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      Lucas Bouten, Caltech      3:00, 74 Jorgensen Title: A reference probability approach to quantum filtering Abstract: Introduction to quantum filtering theory where we focus on the derivation of the quantum filtering equation for a qubit in interaction with the electromagnetic field. Measurement of a field-quadrature via homodyne detection enables us to do inference on the qubit's observables. Using a non-commutative analogue of the Kallianpur-Striebel formula for conditional expectations we will derive the filtering equation for this setup. November-2005 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 n-vertex 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 single-register 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:quant-ph/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 Horodecki-Oppenheim-Winter 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 quantum-mechanical protocol and transforming it in a few simple ways we can accomplish most of the tasks of interest in two-party 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, 352-361, 1993), and for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also extend the result to show that one-way quantum computation of Raussendorf and Briegel (Physical Review Letters, 86:5188-5191, 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 small-treewidth 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: High-fidelity 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 non-detected error, when non-ideal detectors are considered, dependent only on the detector dark-count rate and independent of its efficiency. Since very low dark-count rate detectors are currently available, a high-fidelity 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. December-2005 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 black-box 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}) QLS(B^n) = Theta(2^{n/3} n^{1/6}) RLS([n]^d) = Theta(n^{d/2}) for d >= 4 QLS([n]^d) = Theta(n^{d/3}) for d >= 6 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]. Our new Local Search algorithms work well when the underlining graph expands slowly. As an application to the 2-dimensional grid [n]^2, a new quantum algorithm using O(sqrt(n) (log log n)^{1.5}) time and queries is given. This improves the previous best known upper bound of O(n^{2/3}) [Aaronson, STOC'04], and implies that Local Search on grids exhibits different properties at low dimensions. (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      Renato Renner, University of Cambridge      3:00 pm, 74 Jorgensen Title: A quantum de Finetti representation theorem and applications to QKD Abstract: The analysis of physical experiments is often based on the assumption that the same experiment can be repeated many times independently. In practical situations, however, the independence of the individual repetitions can usually not be guaranteed. The so-called 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 repetitions of the experiment is invariant under reordering. 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. January-2006 January 10: IQI Seminar      Matthew Hastings, Los Alamos National Laboratory      3:00 pm, 74 Jorgensen Title: Lieb-Schultz-Mattis in higher dimensions Abstract: In 1961, Lieb, Schultz, and Mattis showed the absence of a gap in a class of one-dimensional spin chains: chains with half-integer spin per unit cell and SU(2)-invariant short-range 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 half-integer spins. Since then, there has been much work searching for higher dimensional extensions of this result, in particular due to possible connections to high-temperature 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 long-range 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 Perez-Garcia, 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 NP-hardness appear even in the simplest cases. This non-trivial 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 Blume-Kohout, 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 Maximum-Likelihood 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 few-quanta 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 two-state atoms interacting collectively with a single quantized mode of the electromagnetic field (without the standard rotating- wave approximation) exhibits a zero-temperature quantum phase transition to a super-radiant state at a critical atom-cavity coupling strength; characteristic order parameters are the mean photon number and atomic inversion. Here I put forward a proposal based on multilevel atoms and cavity-mediated 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 few-atom and many-atom 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 interacting-spin systems which also exhibit quantum phase transitions and critical behavior of entanglement. February-2006 February 7: IQI Seminar      Andrew Cross, MIT      3:00 p.m., 74 Jorgensen Title: A bound on the accuracy threshold for trapped-ion 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 trapped-ion 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. Fault-tolerant 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 error-correction 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 trapped-ion quantum computing Abstract: We consider a model of quantum computation in which the set of operations is limited to nearest-neighbor interactions on a 2D lattice. For this model we design a fault-tolerant coding scheme using the concatenated $[[7,1,3]]$ Steane code. Our architecture is potentially applicable to ion-trap and solid-state quantum technologies. We calculate a lower bound on the fault-tolerance 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 one-tenth 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. March-2006 March 3: IQI Special Seminar      Luming Duan, University of Michigan      4:00 p.m., 74 Jorgensen Title: Quantum simulation of many-body physics with ultracold atoms Abstract: Coherent control of ultracold atoms provides a powerful platform for quantum simulation of strongly correlated many-body 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 time-of-flight 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 Arthur-Merlin games Abstract: Evaluation of the ground state energy of quantum many-body 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 non-positive 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 translation-invariant Hamiltonians within the specified class obey the area law for entanglement entropy. Our proof is based on the Kirkwood-Thomas 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: One-and-a-half 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 near-optimal 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 Finetti-style theorem (our 'half' theorem); the de Finetti-approximation 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 quant-ph/0602130. April 11: IQI Seminar      Cindy Regal, JILA, University of Colorado      3:00 p.m., 74 Jorgensen Title: Studying the BCX-BEC 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 s-wave 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 Bose-Einstein 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 BCS-BEC crossover. April 13: IQI Special Seminar      Martin Zwierlein, MIT      1:30 p.m., 308 Firestone Title: Observation of high-temperature 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 quark-gluon 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 Bose-Einstein condensate of molecules to a Bardeen-Cooper-Schrieffer 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      Yi-Kai Liu, UCSD      3:00 p.m., 74 Jorgensen Title: Two Results on the Consistency of Local Density Matrices Abstract: Suppose we have an n-qubit 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 maximum-entropy principle; here we give a somewhat different proof, using properties of the partition function. Second, we show that the consistency problem is QMA-hard; in particular, we give a randomized poly-time 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: Bose-Einstein Condensates in Optical Lattices and Superlattices Abstract: Bose-Einstein 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, experimentally-controllable 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 (space-dependent) 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 Deutsch-Jozsa and Bernstein-Vazirani 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 two-level systems (bits). In the generic case, the extractable work can be maximized only by Boolean functions that correspond to proper multi-bit 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 two-level systems with different energy gaps solves the NP complete problem KNAPSACK. The results indicate that there is a trade-off 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 well-known example is the density-matrix renormalisation group (DMRG). Unfortunately, however, little is known about the correctness and worst-case 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 Lieb-Robinson bound and quasi-adiabatic continuation that show that one can provably obtain a representation of the ground state of a class of low-dimensional 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, 1762-65 (2005). [2] D. Pekker, A. Bezryadin, D.S. Hopkins and P.M. Goldbart. Operation of a superconducting nanowire quantum interference device with mesoscopic leads, Physical Review B 72, 104517 (2005). [3] D.S. Hopkins, D. Pekker, T.-C. Wei, P.M. Goldbart and A. Bezryadin, manuscript in preparation (2006). 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 on-chip, 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 spin-echo pulse sequence based on the exchange interaction we extend the spin coherence time, T2 beyond 1.2 microseconds. Current efforts to implement a two-qubit gate and to control the coupling between the electron and nuclear spin systems will be presented. Oct 31: IQI Seminar      Iordanis Kerenidis, CNRS-University of Paris      3:00 pm, 74 Jorgensen Title: Quantum vs. classical one-way communication complexity Abstract: The first exponential separation between quantum and randomized one-way communication complexity was proved by Bar-Yossef, Jayram, Kerenidis [BJK04] for the Relational Hidden Matching Problem. They proved that the quantum one-way communication complexity of this relation is O(log n), yet any randomized one-way 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 one-way communication complexity. Since there is a quantum one-way protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88]. 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 long-range interactions. Finally, implications for the realization of fault-tolerant 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 Gottesman-Knill 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 speed-up 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 half-way between global and local symmetries. Such symmetries appear in numerous systems: the Kitaev model, orbital-dependent spin exchange Hamiltonians in 3d orbital systems, Jahn-Teller 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 fault-tolerant 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 fault-tolerant 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 Bose-Einstein 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 sender-receiver 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