| |
|
| | |
|
![[photo of a speaker] (c) D.Nagaj](img/photos/speaker.jpg)
other seminars:
|
:: Fri 11/30/18, 1:30pm in 6C-442 Shruti Puri (Yale) Many physical systems exhibit error channels that are strongly biased, that is, one type of error dominates the channel. Naively, in this case error correction becomes much easier and more hardware efficient. However, maintaining the bias while performing gates which do not commute with the dominant error is not possible with two-dimensional systems. In this talk, I will demonstrate a way to circumvent this using the non-trivial topology of a continuous family of Schrödinger cat-state qubits. These bosonic qubits can be experimentally realized in a driven non-linear (Kerr) oscillator and exhibit a phase-flip rate that is exponentially suppressed relative to the bit-flip rate. The phase of the drive provides a continuous parameter that permits topologically-protected realization of CNOT gates in a bias-preserving manner. I will present all the bias-preserving operations possible with these cat qubits and discuss how these can lead to efficient quantum error correction codes. :: Fri 11/2/18, 1:30pm in 6C-442 Ken Brown (Duke) The compass model of condensed-matter physics directly inspired the Bacon-Shor subsystem code, but both the Shor code and the rotated surface code can be considered as alternate choices for fixing gauge operators. I will discuss our work exploring the space of compass codes on LxL lattices and potential advantages over the surface codes for errors that are anisotropic or inhomogeneous in space. I will then focus on distance 3 versions of the compass code and describe their possible implementation with trapped atomic ions. This will include a discussion of stabilizer slicing for correcting systematic errors during syndrome extraction. :: Fri 5/11/18, 1:30pm in 6C-442 David Gosset (IBM) Stabilizer states are a rich class of quantum states which can be efficiently classically represented and manipulated. In this talk I will describe classical simulation algorithms for quantum circuits which are based on expressing a quantum state as a superposition of (as few as possible) stabilizer states. The runtime of these algorithms is polynomial in both the number of qubits and the number of Clifford gates but exponential in the number of non-Clifford gates. Based on arXiv:1601.07601 (with Sergey Bravyi) and work in progress with Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell and Mark Howard. :: Fri 4/20/18, 1:30pm in 6C-442 Urmila Mahadev (Berkeley) We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which enables a classical verifier to ensure that the quantum prover holds an n qubit quantum state, and correctly reports the results of measuring it in a basis of the verifier's choice. This is enforced based on the assumption that the learning with errors problem is computationally intractable for efficient quantum machines. :: Fri 10/7/16, 1:30pm in 6C-442 Matthias Christandl (U Copenhagen) We prove upper bounds on the tensor rank of networks of entangled pairs. Any graph defines such a network by associating an entangled pair to each edge of the graph. We present two methods. First, we introduce a surgery-like procedure to transform a good decomposition of a well-chosen tensor into a good decomposition of a tensor of interest. We illustrate the method with surgery on the cycle graph, which corresponds to the iterated matrix multiplication tensor and obtain the first nontrivial rank results for large odd cycles and optimal asymptotic rank results for all cycles. Second, we generalize Strassen’s laser method to higher- order tensors in order to show a nontrivial upper bound on the asymptotic rank for the complete graph. ""Per edge"" this improves on the best upper bound on the matrix multiplication exponent [LG14], for four or more vertices. In entanglement theory, our results amount to protocols for creating a network of entangled pairs from GHZ states by SLOCC. In communication complexity theory, our results imply new bounds on the nondeterministic quantum communication of equality games. Our work is inspired and tightly connected with the vast body of research on matrix multiplication. Based on joint work with Peter Vrana and Jeroen Zuiddam :: Fri 2/5/16, 1:30pm in 6C-442 Marissa Giustina (University of Vienna) Local realism is the worldview in which physical properties of objects exist independently of measurement and where physical influences cannot travel faster than the speed of light. Bell’s theorem states that this worldview is incompatible with the predictions of quantum mechanics, as is expressed in Bell’s inequalities. Previous experiments convincingly supported the quantum predictions. Yet, every experiment requires assumptions that provide loopholes for a local realist explanation. Here, we report a Bell test that closes the most significant of these loopholes simultaneously. Using a well-optimized source of entangled photons, rapid setting generation, and highly efficient superconducting detectors, we observe a violation of a Bell inequality with high statistical significance. :: Thu 1/7/16, 1:30pm in 6C-442 Philipp Kammerlander (ETH Zurich) As technology miniaturizes we find that some approaches of traditional thermodynamics are inadequate to study heat and work in the regime of the very small. There are several aspects to this change, such as finite-size effects, the emergence of quantum effects, the growing importance of correlations between small systems, and the subjectivity of information. In this talk I focus on the last point in this list and argue that objectivity / subjectivity is already an issue when dealing with the traditional theory of phenomenological thermodynamics. I will explore the connection of information theory and thermodynamics and, building on this, present a new formulation of traditional thermodynamics that makes the subjective nature of thermodynamic quantities explicit. :: Tue 1/5/16, 1:30pm in 6C-442 David Sutter (ETH Zurich) The Shannon and von Neumann entropies quantify the uncertainty in a system. They are operationally motivated by natural information processing tasks such as compression, channel coding or randomness extraction. A mathematical consequence of the postulates of quantum physics are several entropy inequalities such as the strong subadditivity of quantum entropy and the monotonicity of quantum relative entropy under physical processes. A series of recent works showed that these inequalities can be strengthened in the context of recoverability, i.e., by considering the question of how well a physical process can be reversed. This also provides an operational definition of approximate quantum Markov chains. In this talk, I will give an overview about the recent works on recoverability, present some new results, and discuss open problems. Based on joint work with Omar Fawzi, Aram Harrow, Marius Junge, Renato Renner, Marco Tomamichel, Mark M. Wilde, and Andreas Winter (arXiv:1504.07251, arXiv:1507.00303, and arXiv:1509.07127). :: Fri 12/11/15, 1:30pm in 2-105 Dave Touchette (Caltech) In the basic communication complexity setup, Alice and Bob are given classical inputs x and y, respectively, and they want to compute a bipartite function f(x, y) while minimizing the amount of communication they must exchange. In the closely related information complexity setting, we are instead interested in the least amount of information that Alice and Bob must leak to each other about their respective inputs in order to compute the function f(x, y). This information complexity paradigm has proven to be a powerful tool for obtaining communication complexity lower bounds in both the classical and quantum settings. In quantum protocols, it is possible for Alice and Bob to forget information they have learned about each other’s classical input. In this talk, we explore the many consequences of this ability of quantum protocols to forget information for defining a quantum notion of information cost. :: Fri 12/4/15, 1:30 in 6C-442 John Wright (CMU) Suppose you have access to iid samples from an unknown probability distribution p = (p_1, …, p_d) on [d], and you want to learn or test something about it. For example, if one wants to estimate p itself, then the empirical distribution will suffice when the number of samples, n, is O(d/epsilon^2). In general, you can ask many more specific questions about p – Is it close to some known distribution q? Does it have high entropy? etc. etc. – and for many of these questions the optimal sample complexity has only been determined over the last 10 years in the computer science literature. The natural quantum version of these problems involves being given samples of an unknown d-dimensional quantum mixed state \rho, which is a d \times d PSD matrix with trace 1. Many questions from learning and testing probability carry over naturally to this setting. In this talk, we will focus on the most basic of these questions: how many samples of \rho are necessary to produce a good approximation of it? Our main result is an algorithm for learning \rho with optimal sample complexity. Furthermore, in the case when \rho is almost low-rank, we show how to perform PCA on it with optimal sample complexity. Surprisingly, we are able to reduce the analysis of our algorithm to questions dealing with the combinatorics of longest increasing subsequences (LISes) in random words. In particular, the main technical question we have to solve is this: given a random word w \in [d]^n, where each letter w\_i is drawn iid from some distribution p, what do we expect \mathrm{LIS}(w) to be? Answering this question requires diversions into the RSK algorithm, representation theory of the symmetric group, the theory of symmetric polynomials, and many other interesting areas. This is joint work with Ryan O'Donnell. :: Fri 11/20/15, 1:30pm in 6C-442 David Gosset (Caltech) Frustration-free local Hamiltonians are a commonly studied subclass of (general) local Hamiltonians. A frustration-free local Hamiltonian H can be written as a sum of terms, such that any ground state of H also has minimal energy for each term. In this talk I will describe some fundamental consequences of frustration-freeness. Firstly I will consider the scaling of the correlation length with spectral gap. Hastings proved that a ground state of a local Hamiltonian with spectral gap g has correlation length upper bounded as O(1/g). This bound cannot be improved in general. However, frustration-free systems satisfy a stronger O(1/sqrt(g)) upper bound on correlation length. Secondly I will consider the scaling of the spectral gap with system size. For 1D translation-invariant frustration-free systems which are gapless in the thermodynamic limit, the spectral gap of an open boundary chain of size n is upper bounded inverse quadratically with n. In contrast if we remove the frustration-freeness restriction then the gap can scale inverse linearly with system size. Finally, I will briefly discuss an open question concerning the scaling of entanglement entropy with spectral gap in frustration-free systems. This talk is based on a joint work with Yichen Huang (arxiv:1509.06360) and a joint work with Evgeny Mozgunov (to appear on arxiv soon). :: Fri 11/13/15, 1:30pm in 6C-442 Ke Li (IBM/MIT) Suppose we are given n copies of one of the quantum states {rho_1,..., rho_r}, with an arbitrary prior distribution that is independent of n. The multiple hypothesis testing problem concerns the minimal average error probability P_e in detecting the true state. It is known that P_e~exp(-En) decays exponentially to zero. However, this error exponent E is generally unknown, except for the case r=2. In this talk, I will give a solution to the problem of identifying the above error exponent, by proving Nussbaum and Szkola's conjecture that E=min_{i\neq j} C(rho_i, rho_j). The right-hand side of this equality is called the multiple quantum Chernoff distance, and C(rho_i, rho_j):=max_{0 \leq s \leq 1} {-log Tr rho_i^s rho_j^(1-s)} has been previously identified as the optimal error exponent for testing two hypotheses, rho_i versus rho_j. The main ingredient of our proof is a new upper bound for the average error probability, for testing an ensemble of finite-dimensional, but otherwise general, quantum states. This upper bound, up to a states-dependent factor, matches the multiple-state generalization of Nussbaum and Szkola's lower bound. Specialized to the case r=2, we give an alternative proof to the achievability of the binary-hypothesis Chernoff distance, which was originally proved by Audenaert et al. :: Fri 11/6/15, 1:30pm in 6C-442 Beni Yoshida (Caltech) In this talk, I will establish the connection among classifications of gapped boundaries in topological phases of matter, bosonic symmetry-protected topological (SPT) phases and fault-tolerantly implementable logical gates in quantum error-correcting codes. We begin by presenting constructions of gapped boundaries for the d-dimensional quantum double model by using d-cocycles functions (d geq 2). We point out that the system supports m-dimensional excitations (m < d), which we shall call fluctuating charges, that are superpositions of point-like electric charges characterized by m-dimensional bosonic SPT wavefunctions. There exist gapped boundaries where electric charges or magnetic fluxes may not condense by themselves, but may condense only when accompanied by fluctuating charges. Magnetic fluxes and codimension-2 fluctuating charges exhibit non-trivial multi-excitation braiding statistics, involving more than two excitations. The statistical angle can be computed by taking slant products of underlying cocycle functions sequentially. We find that excitations that may condense into a gapped boundary can be characterized by trivial multi-excitation braiding statistics, generalizing the notion of the Lagrangian subgroup. As an application, we construct fault-tolerantly implementable logical gates for the d-dimensional quantum double model by using d-cocycle functions. Namely, corresponding logical gates belong to the dth level of the Clifford hierarchy, but are outside of the (d-1)th level, if cocycle functions have non-trivial sequences of slant products. :: Fri 10/30/15, 1:30pm in 6C-442 Ashley Montanaro (U. Bristol) In this talk I will discuss a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T vertices, each vertex corresponding to a test of a partial solution. I will present a bounded-error quantum algorithm which completes the same task using O(sqrt(T) n^(3/2) log n) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree. I will also discuss how, for certain distributions on the inputs, the algorithm can lead to an average-case exponential speedup. :: Fri 10/23/15, 1:30pm in 6C-442 Michael Walter (Stanford) TBA :: Fri 10/9/15, 1:30 in 6C-442 Barry Sanders (University of Calgary) Quantum information processing is possible via multi-channel linear (passive) interferometry with photon number states as some or all of the inputs and photon-coincidence detection at the output ports. The Knill-Laflamme-Milburn nonlinear sign gate on dual-rail photonic qubits and the Aaronson-Arkhipov BosonSampling scheme are salient examples of linear photonic quantum information processing. Implementations of quantum walks also make use of linear photon interferometry. The famous Hong-Ou-Mandel dip presents the heart of what makes linear photon interferometry quantum and furthermore serves as an indispensable characterization tool for sources and interferometers. Our aim is to advance linear photonic quantum interferometry to serve as a precise and accurate tool for optical quantum information processing. To this end we develop and experimentally test a theory for accurate and precise characterization of the Hong-Ou-Mandel dip setup, extend this theory for accurate and precise characterization of multi-channel interferometry based on photon coincidences, extend the Hong-Ou-Mandel dip concept beyond two-channel to multi-channel interferometry, develop theory and (classical) algorithms for computing irreducible representations of SU(m) whose elements represent all m-channel interferometers, and determine the effects of extraneous multi-photon contributions to the desired outputs. Our approach allows for non-simultaneous photon arrival times, which removes the typical symmetrization assumption in photon interferometry and leads to photon coincidence rates depending on immanants of SU(m) matrices or submatrices; immanants generalize the concepts of permanents and determinants to allow for partial symmetries. For linear photon interferometry to move beyond the proof-of-principle stage to solving computational problems, they need to be reliable, accurate and precise within known error. Furthermore their performance needs to be benchmarked against the best classical simulation algorithms. Our results are enabling the field to advance in this direction. :: Fri 10/2/15, 2:10pm in MSR, Horace Mann Conference Room, One Memorial Drive (note different place and time) Ryan O'Donnell (CMU) In quantum mechanics, the state rho of a d-dimensional particle is given by a d x d PSD matrix of trace 1. The "quantum tomography problem" is to estimate rho accurately using as few "copies" of the state as possible. The special case of "quantum spectrum estimation" involves just estimating the eigenvalues alpha_1, ..., alpha_d of rho, which form a probability distribution. By virtue of some representation theory, understanding these problems mostly boils down to understanding certain statistics of random words with i.i.d. letters drawn from the alpha_i distribution. These statistics involve longest increasing subsequences, and more generally, the shape of Young tableaus produced by the Robinson-Schensted-Knuth algorithm. In this talk we will discuss new probabilistic, combinatorial, and representation-theoretic tools for these problems, and the consequent new upper and lower bounds for quantum tomography. This is joint work with John Wright :: Fri 9/18/15, 1:30pm in 6C-442 Or Sattath (MIT) Frustration free Hamiltonians play an important role in many aspects of quantum information theory and condensed matter. Determining whether a given Hamiltonian is frustration free is, however, a complexity theoretically intractable problem. Here, we prove a general criterion under which a local Hamiltonian must be frustration free. Surprisingly, this quantum property is diagnosed by a combinatorial property: analyzing the roots of the matching polynomial of the interaction graph, or in condensed matter terminology, analyzing the partition function of a classical hard-core lattice gas at negative fugacity living on the same interaction graph. We apply this to analyze when local Hamiltonians on various regular lattices and random graphs must be frustration free :: Fri 9/11/15, 1:30pm in 6C-442 Chris Monroe and Jungsang Kim (University of Maryland; Duke) :: Fri 6/26/15, 1:30 in 6C-442 Marco Tomamichel (The University of Sydney) TBA :: Tue 6/23/15, 1:30 in 6C-442 Rotem Arnon Friedman (ETH Zurich) TBA :: Fri 6/12/15, 1:30 in 6C-442 Edward Fredkin (Carnegie Mellon University) TBA :: Mon 5/18/15, 1:30 in 6C-442 Lidia del Rio (University of Bristol) Inspired by quantum information approaches to thermodynamics, we introduce a general framework for resource theories, from the perspective of subjective agents. First we formalize a way to think of subjective knowledge through what we call specification spaces, where states of knowledge (or specifications) are represented by sets whose elements are the possible states of reality admitted by an observer. We explore how to conciliate different views of reality via embeddings between specification spaces. Then we introduce resource theories on specification spaces, which are constructed from a set of allowed operations, imposing a pre-order structure in the specification space. We see how to relate, combine and create different resource theories. The local structure of a specification space (which in quantum theory is given by tensoring different Hilbert spaces) is not assumed a priori. Instead, we derive it operationally from commutativity relations in the set of transformations. Further applications are discussed. :: Fri 5/15/15, 1:30 in 6C-442 Sergey Bravyi (IBM) The energy gap of quantum spin chains is an important parameter that controls the decay of ground state correlation functions, entanglement scaling, and complexity of many simulation tasks. Deciding whether a quantum spin chain is gapped or gapless in the thermodynamic limit is therefore a fundamental problem. I will describe a complete solution of this problem in the special case of quantum 2-SAT Hamiltonians. Specifically, we consider a system of n qubits on a line and a translation-invariant Hamiltonian composed of rank-1 projectors acting on nearest-neighbor qubits. It is shown that the energy gap of this system is controlled by eigenvalues of a certain 2x2 transfer matrix T which has been previously used to compute the ground space degeneracy of a quantum 2-SAT. Namely, the energy gap decays as 1/n if the eigenvalues of T have equal non-zero magnitude. Otherwise the energy gap is lower bounded by a positive constant independent of n. A key ingredient in the proof is a new operator inequality for the ground space projector which expresses a monotonicity under the partial trace. Based on a joint work with David Gosset arXiv:1503.04035. Beni Yoshida (Caltech) We propose a family of exactly solvable toy models for the AdS/CFT correspondence based on a novel construction of quantum error-correcting codes with a tensor network structure. Our building block is a special type of tensor with maximal entanglement along any bipartition, which gives rise to an exact isometry from bulk operators to boundary operators. The entire tensor network is a quantum error-correcting code, where the bulk and boundary degrees of freedom may be identified as logical and physical degrees of freedom respectively. These models capture key features of entanglement in the AdS/CFT correspondence; in particular, the Ryu-Takayanagi formula and the negativity of tripartite information are obeyed exactly in many cases. That bulk logical operators can be represented on multiple boundary regions mimics the Rindler-wedge reconstruction of boundary operators from bulk operators, realizing explicitly the quantum error-correcting features of AdS/CFT. This is a joint work with Daniel Harlow, Fernando Pastawski and John Preskill William Wooters (Williams College) Two orthogonal bases for a Hilbert space are called mutually unbiased if each vector in one basis is an equal-magnitude superposition of all the vectors in the other basis. The maximum number of mutually unbiased bases in a space of dimension d is d+1; so a set of d+1 such bases is called complete. Complete sets of mutually unbiased bases play significant roles in quantum cryptography and quantum tomography. For certain values of d, it is possible to find a single unitary transformation that, by repeated application, generates a complete set of mutually unbiased bases starting with the standard basis. This talk reviews our current understanding of such cycling unitaries and related transformations, and shows how their effects can be pictured in a discrete phase space. :: Fri 4/17/15, 1:30 in 6C-442 Lior Eldar (MIT) Quantum entanglement is considered to be a very delicate phenomenon that is hard to maintain in the presence of noise, or non-zero temperatures. In recent years however, and motivated by a quest for a quantum analog of the PCP theorem, researches have tried to establish whether or not we can preserve quantum entanglement at constant temperature that is independent of system size. This would imply that any quantum state with energy at most, say 0.05 of the total available energy of the Hamiltonian, would be highly-entangled. However to this date, no such systems were found. Moreover, it became evident that even embedding local Hamiltonians on robust, albeit "non-physical" topologies, namely expanders, does not guarantee entanglement robustness. In this talk, I'll provide indication that such robustness may be possible after all, by showing a local Hamiltonian with the following property of inapproximability: any quantum state that violates a fraction at most 0.05 of all local terms cannot be even approximately simulated by classical circuits whose depth is sub-logarithmic in the number of qubits. In a sense, this implies that even providing a "witness" to the fact that the local Hamiltonian can be "almost" satisfied, requires long-range entanglement. :: Fri 3/20/15, 1:30 in 6C-442 Richard Cleve (IQC, University of Waterloo) We present exact unitary 2-designs on n qubits that can be implemented with ?(n) elementary gates from the Clifford group. This is essentially a quadratic improvement over all previous constructions that are exact or approximate (for sufficiently strong approximations). This is joint work with Debbie Leung, Li Liu, and Chunhao Wang. :: Fri 2/27/15, 1:30 in 6C-442 Ramis Movassagh (MIT) Entanglement is a quantum correlation which does not appear classically, and it serves as a resource for quantum technologies such as quantum computing. The area law says that the amount of entanglement between a subsystem and the rest of the system is proportional to the area of the boundary of the subsystem and not its volume. A system that obeys an area law can be simulated more efficiently than an arbitrary quantum system, and an area law provides useful information about the low-energy physics of the system. It was widely believed that the area law could not be violated by more than a logarithmic factor (e.g. based on critical systems and ideas from conformal field theory) in the system?s size. We introduce a class of exactly solvable one-dimensional models which we can prove have exponentially more entanglement than previously expected, and violate the area law by a square root factor. We also prove that the gap closes as n^{-c}, where c ge 2, which rules out conformal field theories as the continuum limit of these models. In addition to using recent advances in quantum information theory, we have drawn upon various branches of mathematics and computer science in our work and hope that the tools we have developed may be useful for other problems as well. (Joint work with Peter Shor) Brian Swingle (Stanford University) I will propose a mechanism whereby a dynamical geometry obeying Einstein's equations emerges holographically from entanglement in certain quantum many-body systems. As part of this broader story I will discuss in particular two crucial results: one establishing a geometric representation of entanglement in the vacuum state of a wide class of (lattice regulated) quantum field theories and one showing how the equivalence principle of gravity is encoded in the universality of entanglement. I will also briefly indicate how the first result opens the door to solving previously intractable strongly interacting models of relevance for experiments in the solid state and elsewhere. Thus I will argue that the fundamental physics of entanglement provides a window into non-perturbative quantum field theory and quantum gravity. :: Fri 12/5/14, 1:30 in 6C-442 Jess Riedel (Perimeter Institute) TBA :: Fri 11/21/14, 1:30 in 6C-442 John Preskill (California Institute of Technology) TBA :: Fri 11/14/14, 1:30 in 6C-442 Lorenza Viola (Dartmouth College) Hamiltonian engineering via unitary open-loop quantum control provides a versatile and experimentally validated framework for precisely manipulating a broad class of non-Markovian dynamical evolutions of interest, with applications ranging from dynamical decoupling and dynamically corrected quantum gates to noise spectroscopy and quantum simulation. In this context, transfer-function techniques directly motivated by control engineering have proved invaluable for obtaining a transparent picture of the controlled dynamics in the frequency domain and for quantitatively analyzing control performance. In this talk, I will show how to construct a general filter-function approach, which overcomes the limitations of the existing formalism. The key insight is to identify a set of "fundamental filter functions", whose knowledge suffices to construct arbitrary filter functions in principle and to determine the minimum "filtering order" that a given control protocol can guarantee. Implications for dynamical control in multi-qubit systems and/or in the presence of non-Gaussian noise will be discussed. :: Fri 11/7/14, 1:30 in 6C-442 Alan Aspuru-Guzik (Harvard University) Density functional theory (DFT) and it's time-dependent counterpart (TDDFT) have been cornerstones in the field of numerical simulations, e.g. in computational materials science, ad computational physics and chemistry. The DFT theorems demonstrate that the exact energy of the ground state of a quantum system is a functional of the density of the system. The time-dependent counterpart (TDDFT) demonstrates that a time-evolving density is enough, in theory, to obtain all observables of a quantum system. In this talk, I will discuss our group's work on the connections of time-dependent density functional theory (TDDFT) and quantum information. In particular, we have proved the TDDFT theorems for the case of open quantum systems. I will discuss the implications of this to problems such as decoherence and the emergence of density functionals for dissipation and relaxation. We also recently showed that TDDFT theorems also exist for the case of distinguishable spin 1/2 systems (e.g. qubits) that are able to perform universal quantum computation. I will discuss the theorems and some potential applications to quantum simulation and also to the possibility of approximating the results of quantum information processing tasks. Recently, we have worked on the complexity of TDDFT as a procedure and show that, within certain physical and computational considerations, it belongs to the bounded quantum polynomial complexity class. This is joint work with Joel Yuen-Zhou, currently a Silbey postdoctoral fellow at MIT, David Tempel, currently a postdoctoral researcher in my group, as well as James Whitfield, former PhD. student currently in Vienna, Sergio Boixo, now at Google and Man-Hong Yung now Assistant Professor at Tsinghua University. :: Fri 10/24/14, 1:30 in 6C-442 Chetan Nayak (Microsoft Research, Station Q and UC Santa Barbara) :: Fri 5/23/14, 1:30 PM in 6C-442 Robin Blume-Kohout (Sandia National Labs) A gauge symmetry appears when we can transform the parameters of a theory, yet leave every observable property invariant. This means that the theory contains redundant parameters. The theory of quantum information processing (QIP) -- in which elementary operations are completely positive maps, and any viable algorithm is described by a quantum circuit that specifies a sequence of those operations -- has a gauge. For "forward" QIP this is no big deal; it just provides multiple equivalent ways to describe the same physical device. But for "inverse" QIP -- i.e., tomography and characterization -- this is surprisingly inconvenient! I will discuss our recent progress on device characterization via gate-set tomography, chronicle our ongoing struggles with the gauge, and plead for your assistance in taming it. Nicole Yunger Halpern (Caltech) How can thermodynamics, which involves vast numbers of particles, describe cutting-edge technology, which involves tiny scales? Heat exchanges have been modeled with the resource-theory framework famous for elucidating entanglement. ?Helmholtz? resource theories have shown that the work cost W_cost of creating one copy of a state can differ from the work W_dist distillable from the state. This ?one-shot? result contrasts with the thermodynamic limit, in which W_cost = W_dist. I will generalize the resource-theory framework from heat exchanges to more-arbitrary thermodynamic interactions. I will introduce resource theories of non-equilibrium, a family of models that includes the Helmholtz theories. In addition to shedding new light on Helmholtz theories, the non-equilibrium framework expands the resource theories? potential to describe experiments and quantum phenomena. I will quantify the distinction between W_cost and W_dist in terms of the hypothesis-testing entropy D_H. This research is motivated by the interplay between information and energy on small scales exemplified by single-molecule experiments, nanoscale engines, and molecular motors. This work was conducted partially (arXiv:1309.6586) at the Perimeter Institute for Theoretical physics with Markus M?ller and Rob Spekkens, as well as with Gilad Gour and Varun Narasimhachar. Part of this work is being conducted with Joe Renes. :: Tue 5/20/14, 12 PM in 4-331 Claudio Chamon (Boston University) The well-known heuristic DMRG (Density Matrix Renormalization Group) has been the method of choice for the practical solution of 1D systems since its introduction two decades ago by Steve White. However, the reasons for DMRG's success are not theoretically well understood and it is known to fail in certain cases. In this talk, I will describe the first polynomial time classical algorithm for finding ground states of 1D quantum systems described by gapped local Hamiltonians. The algorithm is based on a framework that combines recently discovered structural features of gapped 1D systems, convex programming, and a new and efficient construction of a class of operators called approximate ground state projections (AGSP). An AGSP-centric approach may help guide the search for algorithms for more general quantum systems, including for the central challenge of 2D systems, where even heuristic methods have had very limited success. Joint work with Zeph Landau and Thomas Vidick :: Fri 5/16/14, 1:30 PM in 6C-442 Robin Kothari (University of Waterloo) We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error. This is joint work with Dominic W. Berry, Andrew M. Childs, Richard Cleve, and Rolando D. Somma. Available at http://arxiv.org/abs/1312.1414 :: Thu 5/15/14, 11 AM in 6C-442 Umesh Vazirani (UC Berkeley) The well-known heuristic DMRG (Density Matrix Renormalization Group) has been the method of choice for the practical solution of 1D systems since its introduction two decades ago by Steve White. However, the reasons for DMRG's success are not theoretically well understood and it is known to fail in certain cases. In this talk, I will describe the first polynomial time classical algorithm for finding ground states of 1D quantum systems described by gapped local Hamiltonians. The algorithm is based on a framework that combines recently discovered structural features of gapped 1D systems, convex programming, and a new and efficient construction of a class of operators called approximate ground state projections (AGSP). An AGSP-centric approach may help guide the search for algorithms for more general quantum systems, including for the central challenge of 2D systems, where even heuristic methods have had very limited success. Joint work with Zeph Landau and Thomas Vidick :: Fri 5/9/14, 1:30 PM in 6C-442 Andris Ambainis (University of Latvia) The complexity class QMA (quantum counterpart of NP) allows to understand the complexity of many computational problems in quantum physics but some natural problems appear to be slightly harder than QMA. We introduce new complexity classes consisting of problems that are solvable with a small number of queries to a QMA oracle and use these complexity classes to quantify the complexity of several natural computational problems (for example, the complexity of estimating the spectral gap of a Hamiltonian). Sergei Bravyi (IBM) Quantum codes with low-weight stabilizers known as LDPC codes have been actively studied recently due to their potential applications in fault-tolerant quantum computing. However, all families of quantum LDPC codes known to this date suffer from a poor distance scaling limited by the square-root of the code length. This is in a sharp contrast with the classical case where good families of LDPC codes are known that combine constant encoding rate and linear distance. In this talk I will describe the first family of good quantum codes with low-weight stabilizers. The new codes have a constant encoding rate, linear distance, and stabilizers acting on at most square root of n qubits, where n is the code length. For comparison, all previously known families of good quantum codes have stabilizers of linear weight. The proof combines two techniques: randomized constructions of good quantum codes and the homological product operation from algebraic topology. We conjecture that similar methods can produce good stabilizer codes with stabilizer weight n^a for any a>0. Finally, we apply the homological product to construct new small codes with low-weight stabilizers. This is a joint work with Matthew Hastings Preprint: arXiv:1311.0885 :: Fri 4/25/14, 1:30 in 6C-442 Isaac Kim (Perimeter Institute) For a general multipartite quantum state, we formulate a locally checkable condition, under which the expectation values of certain nonlocal observables are completely determined by the expectation values of some local observables. The condition is satisfied by ground states of gapped quantum many-body systems in one and two spatial dimensions, assuming a widely conjectured form of area law is correct. Its implications on quantum state tomography, quantum state verification, and quantum error correcting code is discussed. :: Fri 4/18/14, 1:30 PM in 6C-442 Stephanie Wehner (National University of Singapore) The second law of thermodynamics tells us which state transformations are so statistically unlikely that they are effectively forbidden. Its original formulation, due to Clausius, states that "Heat can never pass from a colder to a warmer body without some other change, connected therewith, occurring at the same time." The second law applies to systems composed of many particles, however, we are seeing that one can make sense of thermodynamics in the regime where we only have a small number of particles interacting with a heat bath, or when we have highly correlated systems and wish to make non-statistical statements about them. Is there a second law of thermodynamics in this regime? Here, we find that for processes which are cyclic or very close to cyclic, thesecond law for microscopic or highly correlated systems takes on a very different form than it does at the macroscopic scale, imposing not just one constraint on what state transformations are possible, but an entire family of constraints. In particular, we find that the quantum Renyi relative entropy distances to the equilibrium state can never increase. We further find that there are three regimes which govern which family of second laws govern state transitions, depending on how cyclic the process is. In one regime one can cause an apparent violation of the usual second law, through a process of embezzling work from a large system which remains arbitrarily close to its original state. :: Fri 4/11/14, 1:30 PM in 6C-442 Keith Lee (Perimeter Institute) Quantum field theory provides the framework for the Standard Model of particle physics and plays a key role in physics. However, calculations are generally computationally complex and limited to weak interaction strengths. After an introduction to quantum field theory, I'll describe polynomial-time quantum algorithms for computing relativistic scattering amplitudes in both scalar and fermionic quantum field theories. The algorithms achieve exponential speedup over known classical methods. One of the motivations for this work comes from computational complexity theory. Ultimately, we wish to know what is the computational power of our universe. Studying such quantum algorithms probes whether a universal quantum computer is powerful enough to represent quantum field theory; in other words, is quantum field theory in BQP? Conversely, one can ask whether quantum field theory can represent a universal quantum computer; is quantum field theory BQP-hard? I'll describe our approach to addressing the question of BQP-hardness. :: Wed 4/2/14, 4:30 PM in 6C-442 Renato Renner (ETH) Quantum state tomography is the task of estimating the state of a quantum system using measurements. Typically, one is interested in the (unknown) state generated during an experiment which can be repeated arbitrarily often in principle. However, the number of actual runs of the experiment, from which data is collected, is always finite (and often small). As pointed out recently, this may lead to unjustified (or even wrong) claims when employing standard statistical tools without care. In this talk, I will present a method for obtaining reliable estimates from finite tomographic data. Specifically, the method allows the derivation of confidence regions, i.e., subsets of the state space in which the unknown state is contained with probability almost one. :: Wed 3/26/14, 4 PM in 32-G575 Alexander Belov (MIT) In this talk, I describe some recent quantum algorithms for the problem of learning and testing juntas. For the main part of the talk, I study the following variant of the junta learning problem. We are given an oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined symmetric function h. The task is to identify the variables the function depends on. This is a generalization of the Bernstein-Vazirani problem (when h is the XOR function) and the (combinatorial) group testing problem (when h is the OR function). I describe an optimal quantum algorithm for the case when h is the OR or the EXACT-HALF function. For the case of the MAJORITY function, I obtain an upper bound of O(k1/4). Additionally, I describe an application of these techniques for the problem of testing juntas, that is a joint work with Andris Ambainis, Oded Regev, and Ronald de Wolf. :: Fri 10/18/13, 1:30 PM in 6C-442 Sean Hallgren (Penn State (visiting MIT)) Computing the unit group of a number field is one of the main problems in computational algebraic number theory. Polynomial time algorithms for problems for arbitrary degree number fields should be polynomial time in both the degree and log of the discriminant. The best classical algorithms for computing the unit group takes time exponential in both parameters. There is a quantum algorithm that runs in time polynomial in log the discriminant but exponential in the degree. We give a quantum algorithm that is polynomial in both parameters of the number field. The proof works via a reduction to a continuous Hidden Subgroup Problem. :: Thu 10/17/13, 3:00 PM in E17-133 Juerg Froehlich (ETH Zurich) After a brief general introduction to the subject of quantum probability theory, quantum dynamical systems are introduced and some of their probabilistic features are described. On the basis of a few general principles - "duality between observables and indeterminates", "loss of information" and "entanglement generation" - a quantum theory of experiments and measurements is developed, and the "theory of von Neumann measurements" is outlined. Finally, a theory of non-demolition measurements is sketched, and, as an application of the Martingale Convergence Theorem, it is shown how facts emerge in non-demolition measurements. :: Thu 10/17/13, 4:00 PM in 10-250 Matthias Troyer (ETH Zurich) About a century after the development of quantum mechanics we have now reached an exciting time where non-trivial devices that make use of quantum effects can be built. While a universal quantum computer of non-trivial size is still out of reach there are a number commercial and experimental devices: quantum random number generators, quantum encryption systems, and analog quantum simulators. In this colloquium I will present some of these devices and validation tests we performed on them. Quantum random number generators use the inherent randomness in quantum measurements to produce true random numbers, unlike classical pseudorandom number generators which are inherently deterministic. Optical lattice emulators use ultracold atomic gases in optical lattices to mimic typical models of condensed matter physics. Finally, I will discuss the devices built by Canadian company D-Wave systems, which are special purpose quantum simulators for solving hard classical optimization problems. :: Fri 9/27/13, 1:30 PM in 6C-442 Joseph Traub (Columbia University (on sabbatical at Harvard)) We introduce the notion of strong quantum speedup. To compute this speedup one must know the classical computational complexity. What is it about the problems of quantum physics and quantum chemistry that enable us to get lower bounds on the classical complexity? :: Fri 5/10/13, 2:00 PM in 6C-442 Thomas Vidick (MIT) The laws of quantum mechanics allow unconditionally secure key distribution protocols. Nevertheless, security proofs of traditional quantum key distribution (QKD) protocols rely on a crucial assumption, the trustworthiness of the quantum devices used in the protocol. In device-independent QKD, even this last assumption is relaxed: the devices used in the protocol may have been adversarially prepared, and there is no a priori guarantee that they perform according to specification. Proving security in this setting had been a central open problem in quantum cryptography. :: Wed 5/8/13, 4:30 PM in 6C-442 Matthias Troyer (ETH Zurich, Institute for Theoretical Physics) :: Fri 4/26/13, 2:00 PM in 6C-442 Toby Cubitt (University of Cambridge) The spectral gap of a quantum many-body Hamiltonian -- the difference between the ground state energy (lowest eigenvalue) and lowest excited state (next-lowest eigenvalue, ignoring degeneracies) in the thermodynamic limit (limit of arbitrarily large system size) -- plays an important role in determining the physical properties of a many-body system. In particular, it determines the phase diagram of the system, with quantum phase transitions occurring at critical points where the spectral gap vanishes. :: Fri 2/22/13, 2:00 PM in 6C-442 Gil Kalai (Hebrew University of Jerusalem and Yale University) Quantum computers are hypothetical devices based on quantum physics that can out-perform classical computers. A famous algorithm by Peter Shor shows that quantum computers can factor an integer n in C(log n)^3 steps. The question if quantum computer are realistic is one of the most fascinating and clear-cut scientific problems of our time, and my work is geared toward a negative answer. The main concern from the start was that quantum systems are inherently noisy; we cannot accurately control them, and we cannot accurately describe them. To overcome this difficulty, a fascinating notion of quantum error-correction and a remarkable theory of quantum fault-tolerance were developed. :: Fri 12/7/12, 2:00 PM in 6C-442 Keye Martin (Naval Research Laboratory) :: Fri 11/30/12, 2:00 PM in 6C-442 Richard Cleve (Waterloo) I define a class of non-local games (in other words, Bell inequality frameworks) that naturally generalizes Mermin's so-called "magic square" game, and then consider the problem of determining the entangled value of such a game. :: Fri 11/16/12, 2:00 PM in 6C-442 Graeme Smith (IBM Research) :: Fri 11/9/12, 2:00 PM in 6C-442 Mario Szegedy (Rutgers) The Garden Hose complexity is a new communication complexity introduced by H. Buhrman, S. Fehr, C. Schaffner and F. Speelman to analyze position-based cryptography protocols in the quantum setting. We focus on the garden hose complexity of the equality function, and improve on the bounds of Buhrman at all. With the help of of a new approach and of our handmade simulated annealing based solver, we have out-performed the commercial set solvers used by Buhrman at all. We have also found beautiful symmetries of the solutions that have lead us to develop the notion of "garden hose permutation groups." Then, exploiting this new concept, we get even farther, although several interesting open problems remain. In our talk we explain the background, our algorithmic efforts, and give a pictorial presentation of the symmetries. :: Fri 10/26/12, 2:00 PM in 6C-442 Daniel Gottesman (Perimeter) Vladan Vuletic (MIT) :: Fri 2/17/12, 10:00 AM in 2-132 Fernando Brandao Quantum mechanics predicts the existence of correlations among two or more quantum systems that cannot be described merely by shared randomness. Such correlations, termed entanglement, have been analyzed from a foundation perspective since the beginning of quantum theory and, more recently, as a resource for quantum information-theoretic tasks. A fundamental problem in entanglement theory is the following: given the description of a quantum system of two or more parties as a density matrix (a positive semidefinite matrix of unit trace), how can we decide if the state is entangled? In this talk I will discuss the fastest known algorithm for solving this question, based on a natural Lasserre hierarchy relaxation of the problem introduced by Doherty, Parrilo, and Spedalieri in 2001, and show how it converges in quasi-polynomial time to the true solution. :: Wed 2/15/12, 2:00 in 6c-442 (QIP seminar) Stephen Jordan (NIST) The study of quantum computation began with Feynman's observation that certain quantum systems require exponential time to simulate on conventional computers. This suggested that quantum mechanical systems are exponentially more computationally powerful than classical systems. This suggestion has been borne out by the subsequent discovery of exponential quantum speedups for several computational problems, most famously factoring. In this talk, I will address a natural follow-up question to Feynman's original observation: can quantum computers efficiently simulate quantum field theories? Specifically, I will present my recent joint work with Keith Lee and John Preskill showing that quantum computers can, in polynomial time, approximate scattering probabilities in phi-fourth theory. In the regimes of strong coupling or high precision, this constitutes an exponential speedup over classical algorithms. In addition, I will discuss our ongoing efforts to extend our simulation methods to the full Standard Model in order to show that, neglecting gravity, the computational power of our universe is equivalent to that of a quantum Turing machine. Prior knowledge of quantum algorithms will not be assumed. :: Fri 2/3/12, 2:30 in 6C-442 (QIP seminar) Aram Harrow (University of Washington) Random unitary matrices are an important tool in quantum information theory and can help us understand physical processes such as thermalization. However, generating even approximately uniformly random unitaries requires time exponential in the size of the system, so is not likely to be possible in practice. In this talk, I will discuss two types of pseudo-random unitaries: t-designs and t-tensor product expanders. Both are distributions that approximately match the first t moments of the uniform distribution. I'll explain how to construct them, either using explicit quantum circuits, or as a result of natural processes. Finally, I'll describe several applications of pseudo-random unitaries to quantum computing and physics. :: Mon 11/21/11, 4:00 in 6C-442 (QIP seminar) Sergey Bravyi (IBM Research) A big open question in the quantum information theory concerns feasibility of a self-correcting quantum memory. A user of such memory would need quantum computing capability only to write and read information. The storage itself requires no action from the user, as long as the memory is put in contact with a cold enough thermal bath. In this talk I will prove that the 3D Cubic Code model discovered recently by Haah is a marginally self-correcting memory. For a fixed temperature T and sufficiently small lattices the memory time of the encoded qubit grows polynomially with the lattice size L. The degree of the polynomial is proportional to 1/T. The polynomial growth of the memory time holds only up to a certain critical value of L which is exponential in 1/T. The maximum memory time that can be achieved at a given temperature T is thus exponential in 1/T^2. The main feature of the 3D Cubic Code Hamiltonian responsible for the self-correction is the energy landscape penalizing any sequence of local errors resulting in a logical error. The energy barrier that must be overcome to implement a bit-flip or phase-flip on the encoded qubit grows as log(L). This is a joint work with Jeongwan Haah (Caltech) Paper: PRL107, 150504 (2011) :: Mon 11/14/11, 4:00 in 6C-442 (QIP seminar) Greg Kuperberg (UC Davis) Every Bell-type protocol separates quantum probability from classical probability, but at what rate of persuasion? A simple calculation shows that the rate of persuasion of the CHSH protocol, which is an optimization of the original Bell protocol, has a persuasion rate (or Kullback-Leibler divergence) of less than 1/20 of the entanglement entropy. Under various rules for the allowed protocol, we can establish up to 13.4% efficiency using larger qudits, and we can prove an upper bound of 100% for any protocol. The natural upper bound is reachable for multipartite cat states, but the bipartite case is open. We also look at ultra-Bell separation between quantum entanglement and general non-signaling boxes, which is a case where we can prove maximal statistical divergence. :: Mon 10/31/11, 4:00 in 6C-442 (QIP seminar) Pawel Wocjan (University of Central Florida) We present an efficient quantum algorithm for computing the period lattice of infrastructures of fixed dimension. The algorithm applies to infrastructures that satisfy certain conditions. The latter are always fulfilled for infrastructures obtained from global fields, i.e., algebraic number fields and function fields with finite constant fields. The first of our main contributions is a rigorous and complete proof that the running time of the algorithm is polynomial in the logarithm of the determinant of the period lattice and exponential in the dimension n. The second main contribution is the determination of an explicit lower bound on the success probability of our algorithm which improves on the bounds given in the works of Hallgren and Schmidt and Vollmer. The exponential scaling seems inevitable because the best currently known methods for carrying out fundamental arithmetic operations in infrastructures obtained from algebraic number fields take exponential time. In contrast, the problem of computing the period lattice of infrastructures arising from function fields can be solved without the exponential dependence on the dimension n since this problem reduces efficiently to the abelian hidden subgroup problem. This is also true for other important computational problems in algebraic geometry. The running time of the best classical algorithms for infrastructures arising from global fields increases subexponentially with the determinant of the period lattice. The talk is based on two articles: one with Felix Fontein and one with Pradeep Sarvepalli. :: Tue 10/4/11, 4:15 in 32-124 (TOC Colloquium) Scott Aaronson (MIT) In recent work with Alex Arkhipov, we proposed a rudimentary form of quantum computing, based entirely on linear optics with nonadaptive measurements; and used a connection between linear optics and the permanent function to show that even this limited model could solve sampling and search problems that are intractable for classical computers under plausible complexity assumptions. In this talk, I'll discuss this work in a self-contained way accessible to classical TCS folks, and mention some of its implications for quantum computing experiments in the very near future. I'll also discuss some more general results that emerged from our work. These include: a new equivalence between sampling problems and search problems based on Kolmogorov complexity; a new, linear-optics-based proof of Valiant's famous theorem that the permanent is #P-complete; and a new classical approximation algorithm for the permanent. Papers: http://arxiv.org/abs/1011.3245 http://arxiv.org/abs/1009.5104 http://www.scottaaronson.com/papers/sharp.pdf :: Mon 10/3/11, 4:00 in 6C-442 (Note new location!) (QIP seminar) Antonello Scardicchio (ICTP) TBA :: Mon 5/16/11, 4:00 in 36-428 (QIP seminar) Martin Roetteler (NEC Laboratories America) We introduce a new quantum adversary method to prove lower bounds on the query complexity of quantum state generation problems. This encompasses both, the computation of partial or total functions and the preparation of target quantum states. There had been hope for quite some time that quantum state generation might be a route to tackle the Graph Isomorphism problem. We show that for the related Index Erasure problem our method leads to tight lower bound on the query complexity, showing that a simple reduction to quantum search is optimal. This closes an open problem first raised by Shi [FOCS'02]. Our approach is based on (i) a generalization of the additive and multiplicative adversary methods and (ii) a representation-theoretic way to exploit symmetries of the underlying problem. We construct adversary matrices from the Bose-Mesner algebra of an association scheme that is defined implicitly by the Index Erasure problem. On the algorithmic side, we present a new technique to tackle quantum state generation which can be thought of as a quantum analog of the classical rejection sampling method (von Neumann, 1951). We analyze the running time of our algorithm using semidefinite programming. As an application, we derive a new quantum algorithm for the hidden shift problem for an arbitrary Boolean function whose running time is obtained by "water-filling" its Fourier spectrum. Joint work with Andris Ambainis, Loick Magnin, Maris Ozols, and Jeremie Roland and based on arXiv:1103.3017 and arXiv:1103.2774. :: Mon 5/9/11, 4:00 in 36-428 (QIP seminar) Steve Flammia (California Institute of Technology) Recent years have witnessed tremendous progress in laboratory experiments which prepare highly entangled states of quantum many-body systems. As the complexity of these states increases, however, so too does the difficultly in verifying the quality of the experiment by some objective measure, and in characterizing any undesired noise processes therein. In this talk I will discuss several new methods which address both tasks -- verification and characterization -- using far fewer resources than traditional methods. I will show how ideas from compressed sensing can be adapted to learn a nearly pure quantum state or nearly unitary quantum process using quadratically fewer measurement settings than traditional methods, an improvement which is provably optimal. Next, I will show how ideas from quantum information theory and condensed matter physics allow us to efficiently learn the ground states of local Hamiltonians of gapped one-dimensional interacting quantum systems in polynomial time in the number of systems. Finally, I will show how to directly verify the quality of an experiment (as quantified by the fidelity or process fidelity with respect to some ideal process) using only a constant number of measurement settings, independent of the size of the system. :: Mon 4/25/11, 4:00 in 36-428 (QIP seminar) Chris King (Northeastern University) The concentration of measure phenomenon has been used to analyze typical behavior of high-dimensional random channels, leading to the proof of existence of counterexamples to the additivity conjectures. In this talk another application will be described, concerning the behavior of typical output states from multiple products of a fixed channel, when the number of factors in the product increases. Concentration of measure implies that the output entropy per channel use for typical states will converge to the average output entropy per channel use. Explicit calculations are shown for some classes of examples, and the relation to entanglement of typical output states is also discussed. :: Mon 4/11/11, 4:00 in 36-462 (QIP seminar) Robert Raussendorf (University of British Columbia) We demonstrate that the two-dimensional AKLT state on a honeycomb lattice is a universal resource for measurement-based quantum computation [1]. This opens up an appealing possibility of creating a universal resource state by cooling into the ground state of a rather simple Hamiltonian. Our argument proceeds by reduction of the AKLT state to a 2D cluster state, which is already known to be universal, and consists of two steps. First, we devise a local POVM by which the AKLT state is mapped to a random planar graph state. Second, we show numerically that the connectivity properties of these random graphs are governed by percolation, and that typical graphs are in the connected phase. The corresponding graph states can then be transformed to 2D cluster states by standard techniques. Joint work with Tzu-Chieh Wei and Ian Affleck. An analogous result has been obtained by A. Miyake in [2]. [1] TC. Wei, I. Affleck and R.Raussendorf, PRL 106 (2011), [2] A. Miyake, arXiv:1009.3491 :: Mon 4/4/11, 4:30 in 2-105 (QIP seminar) Zhenghan Wang (Microsoft Research) Topological phases of matter are exotic quantum states of matter that possess an elusive order, dubbed topological order by X.-G. Wen. Elementary excitations in topological phases of matter are quasi-particles, named anyons by F. Wilczek, which obey neither bosonic nor fermionic statistics. Modeling of two dimensional topological phases of matter utilizes a diverse variety of mathematics: (2+1)-topological quantum field theory as effective theory, conformal field theory as edge theory, and modular tensor category as an algebraic theory of anyons. A topological phase of matter that harbors non-abelian anyons is essentially a topological quantum computer immune to local errors and thus provides a realization of fault-tolerant quantum computation. In this survey talk, we will start with the only currently known examples of topological phases of matter---fractional quantum Hall liquids--and explain their theoretical models. The effective theories of fractional quantum Hall liquids are the quantum Witten-Chern-Simons theories, and the major components of the modeling ground state wave functions of quantum Hall liquids are translation-invariant symmetric polynomials with an arbitrary number of variables (most such polynomials occur as conformal blocks of the conformal field theories which describe the edges). Next, we will discuss how quantum computing is carried out by braiding non-abelian anyons. We will address when braiding alone can lead to universal quantum gates and hence Shor?s factoring algorithm can be implemented by a topological quantum computer. Finally, we conjecture that the failure of the universality of braiding gates is related to a form of explicit locality in topological quantum field theory involving the Yang-Baxter equation. :: Mon 3/14/11, 4:00 in 36-428 (QIP seminar) Andrew Childs (University of Waterloo) We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether a graph is planar, is a forest, or does not contain a path of a given length. We show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minor-closed properties (and more generally, sparse graph properties) that can be characterized by finitely many forbidden subgraphs can be solved strictly faster, in o(n^{3/2}) queries. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems. This is joint work with Robin Kothari. :: Mon 3/7/11, 4:00 in 36-428 (QIP seminar) Patrick Hayden (McGill University) Where should one look to find bases satisfying strong uncertainty relations? Position and momentum lead the way: it's hard to do better than any orthonormal basis and its Fourier transform. The natural generalization to so-called mutually unbiased bases, however, leaves a bit to be desired when it comes to uncertainty relations. Reframing the search in terms of low-distortion embeddings instead leads to bases satisfying much stronger uncertainty relations than had previously been known, plus a wealth of applications. I'll explain, for example, how to encrypt an n-bit message using a constant-sized secret key and how to perform equality testing of n-qubit quantum states using a a constant amount of quantum communication. Based on joint work with Omar Fawzi and Pranab Sen. arXiv:1010.3007. :: Thu 2/24/11, 11:00 in 6-310 (QIP seminar) Sanders,Barry (University of Calgary) Since 1982, when Feynman first proposed efficiently simulating Hamiltonian dynamics on a quantum computer as a way around classical- computer intractability, great advances have been achieved in developing general-purpose quantum-simulation algorithms for bounded- error solutions that fully account for all consumed computational resources. The primary focus has been on time-independent Hamiltonian evolution, but time-dependent Hamiltonian evolution is also important as it is central to quantum control and adiabatic processes. I report our efficient quantum algorithm for simulating time-dependent Hamiltonian evolution of general input states on a quantum computer provided that the Hamiltonian is sufficiently smooth. The time cost of our algorithm is close to linear in the evolution time, hence comparable to algorithms for simulating time-independent Hamiltonian evolution. Our algorithm is based on queries to an oracle holding the Hamiltonian, and we assign unit cost per bit or qubit for oracle calls in contrast to previous work wherein an oracle query yields an arbitrary number of bits or qubits at constant cost. Our per-bit or per-qubit costing of oracle calls reveals hitherto unnoticed simulation costs even for the case of simulating time-independent Hamiltonian evolution. We also account for discretization errors in the time and the representation of the Hamiltonian. Consequently our algorithm not only enables simulation of time-dependent quantum dynamics on a quantum computer but also reduces to the time- independent evolution case and with a fair assessment of oracle-query cost. :: Mon 12/6/10, 4:00 in 36-428 (QIP seminar) Rafail Ostrovsky (UCLA) In this talk, I'll describe position-based cryptography in the classical and in the quantum world. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that there are very strong impossibility results in both worlds, with interesting consequences for one-round distributed quantum computation. On the positive side, we show that if adversaries do not share entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. In models where secure positioning is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any pre-shared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement. The talk will be self-contained and accessible to the general audience. The talk is based on two papers: http://arxiv.org/abs/1009.2490 http://www.cs.ucla.edu/~rafail/PUBLIC/102.pdf :: Mon 11/1/10, 4:00 in 36-428 (QIP seminar) Francesco Zamponi (Ecole Normale Superieure) I will discuss the quantum version of a simplified model of optimization problems, where quantum fluctuations are introduced by a transverse field acting on the qubits. The Hamiltonian of the model displays a complex low-energy spectrum, characterized by an abrupt condensation transition and a continuum of level crossings as a function of the transverse field. This complex structure might have deep consequences on the behavior of quantum algorithms attempting to find solutions to these problems, which I will discuss. Based on joint work with Laura Foini and Guilhem Semerjian, Phys. Rev. Lett. 105, 167204 (2010) :: Mon 10/18/10, 4:00 in 36-462 (QIP seminar) Peter Young (University of California, Santa Cruz) I will describe results of quantum Monte Carlo simulations for quite large problem sizes which aim to determine how efficiently the quantum adiabatic algorithm could solve hard optimization problems on a quantum computer. A comparison will be made with a classical, heuristic, algorithm WALKSAT. Some recent results on XORSAT, a problem which is very hard for local search algorithms even though it is in the P complexity class, will also be presented. :: Tue 10/5/10, 4:00 in 34-401A (Special Seminar) Marco Bellini (Istituto Nazionale di Ottica, INO-CNR, Firenze, Italy) I will illustrate some of the recent activities carried out in our laboratory to investigate and control the quantum nature of light. The experimental implementation of some of the most basic quantum operations, like single-photon creation [1,2] and annihilation [3], has allowed us to generate and manipulate light at the most accurate levels. This, together with advanced techniques for the complete characterization of the generated light states, has allowed us to probe fundamental rules of quantum physics (like the commutation relations [4-6]), and develop novel tools (like noiseless linear amplification [7]) for quantum information processing and future quantum technologies. References: [1] A. Zavatta, S. Viciani, and M. Bellini, Science 306, 660 (2004). [2] A. Zavatta, V. Parigi, and M. Bellini, Phys. Rev. A 75, 052106 (2007) [3] A. Zavatta, V. Parigi, M. S. Kim, and M. Bellini, New J. Phys., 10, 123006 (2008) [4] V. Parigi, A. Zavatta, M.S. Kim, and M. Bellini, Science, 317, 1890-1893 (2007) [5] M. S. Kim, H. Jeong, A. Zavatta, V. Parigi, and M. Bellini, Phys. Rev. Lett., 101, 260401 (2008) [6] A. Zavatta, V. Parigi, M.S. Kim, H. Jeong, and M. Bellini, Phys. Rev. Lett., 103, 140406 (2009) [7] A. Zavatta, J. Fiurasek, and M. Bellini, arXiv:1004.3399v1 :: Mon 10/4/10, 4:00 in 36-428 (QIP seminar) Bartlett,Stephen (University of Sydney) A recent breakthrough in quantum computing has been the realization that quantum computation can proceed solely through single-spin measurements on an appropriate quantum state. One exciting prospect is that the ground or low-temperature thermal state of an interacting quantum many-body system can serve as such a resource state for quantum computation. The system would simply need to be cooled sufficiently and then subjected to measurements. It would be unfortunate, however, if the usefulness of a ground or low-temperature thermal state for quantum computation was critically dependent on the details of the system's Hamiltonian; if so, engineering such systems would be difficult or even impossible. A much more powerful result would be the existence of a robust ordered phase which is characterized by the ability to perform measurement-based quantum computation. I'll discuss some recent results on the existence of such a quantum computational phase of matter. I'll first outline some positive results on a phase of a toy model that allows for quantum computation. Then, in a realistic model of a coupled spin-1 chain, I'll demonstrate the existence of a computational phase. This result is obtained by using a measurement sequence to "renormalize" the state to a computationally-universal fixed point - the so-called AKLT state in the Haldane phase. Together, these results reveal that the characterization of computational phases of matter has a rich, complex structure -- one which is still poorly understood. Joint work with Gavin Brennen, Akimasa Miyake, and Joseph Renes. :: Mon 5/17/10, 4:30 in 36-462 (QIP seminar) Zeng,Bei (University of Waterloo) Quantum 2-SAT is a problem of asking whether there exists a state of n qubits such that its 2-qubit reduced density matrices have support on prescribed subspaces. Here, we show that every positive instance of Quantum 2-SAT always has a solution that is a product of single- or two-qubit states. This gives a no-go theorem for one-way quantum computing, which says that in order to do one-way quantum computing with a natural ground state of a two-body frustration-free Hamiltonian, one has to go to higher dimensional particle systems other than qubit systems. Furthermore, we give a characterization of the whole solution space of the Quantum 2-SAT problem in terms of span of product states. This characterization implies that the counting version of Quantum 2-SAT is in #P, and therefore #P-Complete. Our results indicate that entanglement plays almost no role in the Quantum 2-SAT problem. Joint work with Jianxin Chen, Xie Chen, Runyao Duan, Zhengfeng Ji and Zhaohui Wei. :: Mon 5/10/10, 4:30 in 36-462 (QIP seminar) Temme,Kristan (University of Vienna) Quantum computers have emerged as the natural architecture to study the physics of strongly correlated many-body quantum systems, thus providing a major new impetus to the field of many-body quantum physics. While the method of choice for simulating classical many-body systems has long since been the ubiquitous Monte Carlo method, the formulation of a generalization of this method to the quantum regime has been impeded by the fundamental peculiarities of quantum mechanics, including, interference effects and the no-cloning theorem. We overcome those difficulties by constructing a quantum algorithm to sample from the Gibbs distribution of a quantum Hamiltonian at arbitrary temperatures, both for bosonic and fermionic systems. This is a further step in validating the quantum computer as a full quantum simulator, with a wealth of possible applications to quantum chemistry, condensed matter physics and high energy physics. :: Mon 5/3/10, 4:30 in 36-462 (QIP seminar) Ji,Zhengfeng (University of Waterloo) We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE, the class of problems that can be solved in polynomial space. This containment is proved by applying a parallelized form of the matrix multiplicative weights update method to a class of semi-definite programs that captures the computational power of quantum interactive proofs. As the containment of PSPACE in QIP follows immediately from the well-known equality IP = PSPACE, the equality QIP = PSPACE follows. Joint work with Rahul Jain, Sarvagya Upadhyay, and John Watrous. :: Mon 4/26/10, 4:30 in 36-428 (QIP seminar) Aaronson,Scott (M.I.T) We propose a linear-optics experiment that might be feasible with current technology, and argue that, if the experiment succeeded, it would provide evidence that at least some nontrivial quantum computation is possible in nature. The experiment involves generating reliable single-photon states, sending the photons through a random linear-optical network, and then reliably measuring the photon number in each mode. The resources that we consider are not known or believed to be universal for quantum computation; nevertheless, we show that they would allow the solution of certain sampling and relational problems that appear to be intractable for classical computers. Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as our optical experiment, then P^P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, the above result assumes an extremely reliable experiment. While that could in principle be arranged using quantum error correction, the question arises of whether a noisy experiment would already have interesting complexity consequences. To address this question, we formulate a so-called "Permanent-of-Gaussians Conjecture" (PGC), which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; as well as a "Permanent Concentration Conjecture" (PCC), which says that |Per(A)|>=sqrt(n!)/poly(n) with high probability over A. We then show that, assuming both the PGC and the PCC, polynomial-time classical simulation even of noisy linear-optics experiments would imply a collapse of the polynomial hierarchy. Joint work with Alex Arkhipov. :: Mon 4/12/10, 4:30 in 36-428 (QIP seminar) Harrow,Aram (University of Bristol) Given two copies of a n-system pure state psi, there a natural (even canonical) test that can estimate whether psi is product across all n systems or far from product. Our main technical result is an improved analysis of this test that achieves performance independent of the number of subsystems or their dimension. I'll describe applications to information theory and quantum proof systems (aka QMA(2)). These latter results will imply new hardness results for several problems, including finding the ground-state energy in the mean-field approximation and (as promised in the title) identifying the set of separable states up to constant accuracy. Based on 1001.0017, which is joint work with Ashley Montanaro. :: Mon 4/5/10, 4:30 in 36-462 (QIP seminar) Irani,Sandy (University of California, Irvine) DMRG has been an extremely successful method in practice for computing ground energies in 1D quantum systems. In recent years, DMRG has been recast as a method which heuristically minimizes energy over the set of states which can be represented as Matrix Product States. This suggests that there is a correspondence between efficiently computable ground states and Matrix Product States - but is there a provable connection? In this talk, we describe an algorithm which finds an approximation of the lowest energy MPS for a 1D quantum system. The algorithm runs in time that is polynomial in the number of particles and the approximation error, but exponential in D, the bond dimension of the Matrix Product State. It implies a pseudo-polynomial algorithm for systems whose ground state can be approximated by an MPS with logarithmic bond dimension. The algorithm uses dynamic programming to find a state with low energy, similar to the way that dynamic programming is used to solve a classical constraint satisfaction problem on a line. This dynamic programming approach can also be used to find ground states for 1D commuting Hamiltonians. :: Tue 3/23/10, 4:00 in 36-428 (QIP seminar) Elham Kashefi (University of Edinburgh) We present the semantics of quantum circuits with time-like loops in terms of projection-based quantum computing and characterise the class of time-like loop with unitary or completely-positive semantic that can be deterministically simulated in the one-way model. We also present the re-write rules for opening the loops to transform an imaginary circuit to a normal circuit and discuss the connection between time-like loops and depth complexity. :: Mon 3/15/10, 4:30 in 36-462 (QIP seminar) Matthew Hastings (Microsoft Research) Hamiltonians such as the toric code and Levin-Wen models have many nice features: the ground state can be written down exactly, the system is gapped, and, perhaps most importantly, the low-lying states have topological properties useful for computation. However, what happens if we consider weak perturbations of these Hamiltonians? I will discuss recent work proving stability of topological quantum order in such Hamiltonians against weak perturbations. This will be a blackboard talk, aimed at motivating the problem, explaining the technical statement of what we proved, and giving some idea of the techniques involved. :: Mon 3/8/10, 4:30 in 36-462 (QIP seminar) Krovi,Hari (University of Connecticut) Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it could solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. These hard instances usually lie far from the satisfiability threshold of random instances of NP-complete problems and this is regime where classical solvers are inefficient. Thus, it is important to understand whether adiabatic quantum optimization is efficient in this regime. Here, we will show that because of a phenomenon similar to Anderson localization, an exponentially small eigenvalue gap appears in the spectrum of the adiabatic Hamiltonian for large random instances, very close to the end of the algorithm. This implies, unfortunately, that adiabatic quantum optimization fails for these instances by getting stuck in a local minimum, unless the computation is exponentially long. (Joint work with Boris Altshuler and J?r?mie Roland) :: Mon 2/22/10, 4:30 in 36-428 (QIP seminar) Denchev,Vasil (Purdue/Google) We report on work aiming to apply adiabatic quantum computing (AQC) to machine learning. Machine learning is of rapidly growing importance to many engineering disciplines. At their core, most machine learning problems map to formally NP-hard optimization. This motivates the use of AQC as it promises to deliver solutions of higher quality than classical heuristic solvers. Specifically, we study the problem of training a binary classifier. The classifier is constructed as a thresholded linear superposition of a set of weak classifiers with weights that are optimized in a learning process striving to minimize the training error as well as the number of weak classifiers used. We show that the necessary bit precision of the weights grows only logarithmically with the ratio of the number of training examples to the number of weak classifiers and formulate the training as quadratic unconstrained binary optimization to conform to the format required by D-Wave's implementation of AQC. Next, we generalize this baseline method to large-scale classifier training, where either the cardinality of the dictionary of weak classifiers or the number of weak classifiers used in the final strong classifier exceed the number of variables that can be handled in a single global optimization. For such situations we propose an iterative and piecewise approach in which a subset of weak classifiers is selected in each iteration via global optimization. The strong classifier is then constructed by concatenating the subsets of weak classifiers. We find that on our benchmark problems the proposed method outperforms the state-of-the-art algorithm AdaBoost, even when we use a classical heuristic as a stand-in for the quantum hardware. We also provide theoretical arguments as to why the proposed optimization method, which does not only minimize the training error but also adds L0-norm regularization, is superior to versions of boosting that only minimize the training error. By conducting a quantum Monte Carlo simulation, we gather initial evidence that AQC may be able to handle a generic training problem efficiently. Finally, we describe our first attempt to use D-Wave's current hardware to train a large-scale detector. :: Mon 2/8/10, 4:30 in 36-462 (QIP seminar) Gurvits,Leonid (LANL) After making some historical remarks, I will first focus on classical randomized algorithm(s) for the additive approximation of the permanent, which came after the corresponding quantum linear optical algorithms. In the second part of the talk, I will discuss the relative approximation of the permanent of PSD matrices. Quantum linear optical as well classical approaches will be presented. Rigorous results will be clearly separated from some speculations. :: Mon 12/7/09, 4:00 in 36-428 (QIP seminar) K.Birgitta Whaley (UC Berkeley) The initial light-harvesting step of photosynthesis is known to be exceptionally efficient, transporting absorbed light energy as electronic excitation to the reaction center with near unity efficiency within a few picoseconds. It was recently shown that this process is accompanied by surprisingly long-lived electronic coherences, which prompted speculation that light harvesting complexes might be robust, evolved quantum processors that operate effectively in a highly decohering environment. I shall present theoretical studies (quant-ph/0905.3787,quant-ph/0910.1847 ) of the quantum dynamics of a prototypical photosynthetic light harvesting complex, the Fenna-Matthews-Olson (FMO) complex that address the nature and extent of two characteristic features of quantum processors, quantum speedup and quantum entanglement, in these biological systems with the help of both generic model and realistic simulations. :: Mon 11/30/09, 4:00 in 36-428 (QIP seminar) Pirandola,Stefano (MIT/University of York) The optimal discrimination of quantum states is a central problem in quantum information theory. A problem of equal importance, but more difficult to solve, is the optimal discrimination between different quantum channels. In this seminar we analyze these general problems and we specialize them to the scenario of bosonic systems. First we consider the optimal discrimination between two arbitrary Gaussian states, showing how we can estimate the corresponding error probability via the quantum Chernoff bound. Then, we consider the case of two Gaussian channels. Here we provide a lowerbound for the minimum error probability which affects the "classical discrimination" of these channels, i.e., their optimal discrimination assuming "classical states" as input (defined as states with positive P-representation). Exploiting this bound, we can find channel discrimination problems where the use of a "non-classical" input state (e.g., an entangled state) outperforms the use of any "classical" input state. This enhancement is shown in two paradigmic tasks: the sensing of low-reflectivity targets in bright thermal-noise baths (quantum illumination), and the readout of classical digital memories (quantum reading). :: Mon 11/23/09, 4:00 in 36-428 (QIP seminar) Aram Harrow (University of Bristol) Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector b, find a vector x such that Ax=b. We consider the case where one doesn't need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm. This talk is based on arXiv:0811.3171v3, which is joint work with Avinatan Hassidim and Seth Lloyd. Andy Lutomirski (M.I.T) Public-key quantum money is a cryptographic protocol in which a bank can create quantum states which anyone can verify but no one except possibly the bank can clone or forge. There are no secure public-key quantum money schemes in the literature; as we show in this paper, the only previously published scheme (Aaronson 2009) is insecure. We introduce a category of quantum money protocols which we call collision-free. For these protocols, even the bank cannot prepare multiple identical-looking pieces of quantum money. We present a blueprint for how such a protocol might work as well as a concrete example which we believe may be insecure. :: Mon 11/9/09, 4:00 in 36-428 (qip-sem) Ben Reichardt (University of Waterloo) The general adversary bound is a lower bound on the number of input queries required for a quantum algorithm to evaluate a boolean function. We show that this lower bound is in fact tight, up to a logarithmic factor. The proof is based on span programs. It implies that span programs are an (almost) equivalent computational model to quantum query algorithms. One of the consequences is that almost-optimal quantum algorithms can always be designed based on span programs. This is worthwhile because span programs have useful properties, such as composing easily. We apply this to the formula-evaluation problem. For example, evaluating an AND-OR formula is similar to the question of whether white or black has a winning strategy in chess. We give an optimal quantum algorithm for evaluating almost-balanced formulas over any finite boolean gate set. For example, the formula's gate set may be taken to be all functions {0,1}^k --> {0,1} with k <= 1000. Another consequence is a simpler semi-definite program for quantum query complexity. :: Mon 11/2/09, 4:00 in 36-428 (qip-sem) Daniel Nagaj (RCQI, IoP SAS, Bratislava) Given a verifier circuit for a problem in QMA, we show how to exponentially amplify the gap between its acceptance probabilities in the `yes' and `no' cases, with a method that is quadratically faster than the procedure given by Marriott and Watrous. Our construction is natively quantum, based on the analogy of a product of two reflections and a quantum walk. Second, in some special cases we show how to amplify the acceptance probability for good witnesses to 1, inquiring whether QMA with one-sided error (QMA_1) is equal to QMA and as a side result, show that QCMA_1 is equal to QCMA. Finally, we simplify the filter-state method to search for QMA witnesses by Poulin and Wocjan. [This is joint work with Pawel Wocjan, Yong Zhang and Stephen Jordan] :: Mon 10/26/09, 4:00 in 36-428 (qip-sem) Kaiser,David (MIT) In recent years, the field of quantum information science-an amalgam of topics ranging from quantum encryption, to quantum computing, quantum teleportation, and more-has catapulted to the cutting edge of physics, sporting a multi-billion-dollar research program, tens of thousands of published research articles, and a variety of device prototypes. This tremendous excitement marks the tail end of a long-simmering Cinderella story. Long before the big budgets and dedicated teams, the field smoldered on the scientific sidelines. In fact, the field's recent breakthroughs derive, in part, from the hazy, bong-filled excesses of the 1970s New Age movement. Many of the ideas that now occupy the core of quantum information science once found their home amid an anything-goes counterculture frenzy, a mishmash of spoon-bending psychics, Eastern mysticism, LSD trips, CIA spooks chasing mind-reading dreams, and comparable "Age of Aquarius" enthusiasms. For the better part of two decades, the concepts that would,in time, blossom into developments like quantum encryption were bandied about in late-night bull sessions and hawked by proponents of a burgeoning self-help movement-more snake oil than stock option. This talk describes the field's bumpy transition from New Age to cutting edge. :: Mon 10/19/09, 4:00 in 36-428 (qip-sem) Andrew Childs (University of Waterloo) Standard methods for performing an arbitrary N-dimensional unitary operation use a number of elementary operations proportional to N^2. We consider a related problem, the implementation of a unitary operation using a black-box description of its matrix elements. In this model, we show that any unitary can be performed using approximately N^{2/3} queries. Indeed, many unitary transformations can be performed in only about sqrt(N) queries, which cannot be improved in general. Our implementation of black-box unitaries makes use of general methods for black-box Hamiltonian simulation (based on discrete-time quantum walk) and black-box quantum state preparation.This is joint work with Dominic Berry (IQC). :: Tue 10/13/09, 3:00 in 36-428 (qip-sem) Nayak,Ashwin (U. Waterloo and Perimeter) The two-party communication complexity model formalizes the study of costs involved in distributed computation. Here, two processors aim to jointly solve a task by communicating over a connecting link. In a realistic setting, this link may be subject to noise and we may wonder how reliably we can compute over this link, and what the associated overhead is. An application of the Shannon noisy coding theorem results in a simulation of protocols that is robust against noise, but comes with a logarithmic factor overhead in communication cost. In the 90's, Schulman gave an elegant simulation of interactive protocols that incurs only constant factor overhead, in spite of the fact that we do not have the advantage of long block size for such coding. We consider the problem of coding for interactive protocols with quantum communication. In this setting, the Schulman scheme breaks down for a number of reasons. First, we do not know of a quantum analogue of the "tree codes'' used in the scheme. Second, the scheme relies on re-computation of messages that are corrupted beyond repair, which is not possible for quantum states due to impossibility of cloning. We describe a simulation of quantum communication protocols which overcomes these hurdles while introducing only a constant factor slowdown. (Joint work with Falk Unger, UC Berkeley) :: Fri 10/9/09, 11:00 in 36-462 Barry Sanders (University of Calgary) :: Mon 10/5/09, 4:00 in 36-428 (QIP seminar) Jacobs,Kurt (University of Massachusetts Boston) I will describe a method to obtain effective non-linearities in quantum resonators by coupling them perturbatively to low-dimensional systems (one or two qubits). The method involves determining sufficiently simple Hamiltonians for the qubits that will generate perturbation expansions with desired properties. A potentially wide range of nonlinearities can be obtained in this way, and results indicate that they are relatively robust against decoherence in the auxiliary system. :: Wed 7/1/09, 2:00 in 6-310 (QIP seminar) Berkley,Andrew (D-Wave) The state of the art in superconducting quantum electronics has reached the point where it appears feasible to build an adiabatic quantum optimization processor based on them. D-Wave is currently building such a device. In this talk I will discuss: the high-level architecture; the design of the qubits and supporting devices; measurements of qubit performance and noise characterization; and measurements on a scalable 8-qubit unit cell where optimization problems are downloaded to the chip by a handful of digital lines leading to on-chip control circuitry (SFQ) which configure the qubits and couplers. :: Mon 5/18/09, 4:15 in 36-428 (QIP seminar) Navascues,Miguel (Imperial College London) In this talk, I will analyze the speed of convergence of algorithms for entanglement detection based on PPT (Positive Partial Transpose) symmetric extensions, as conceived by Doherty et al. [1]. I will show that the states defined in [1] can be made separable just by partially depolarizing one of the parts. While the amount of necessary noise to induce separability on states that admit a plain N-symmetric extension decreases as O(1/N), the corresponding perturbation for states arising from PPT N-symmetric extensions decreases at least as O(1/N^2). I will use these results to estimate and compare the time and space complexity of both algorithms. Finally, I will consider the power of the PPT criterion alone: I will show how to derive upper bounds on the maximum possible distance between a PPT entangled state and the set of separable states by means of a simple construction. [1] A. C. Doherty, P. A. Parrilo and F. M. Spedalieri, Phys. Rev. A 69, 022308 (2004). :: Mon 5/11/09, 4:15 in 36-428 (QIP seminar) Jordan,Stephen (Caltech) In topological quantum computation the geometric details of a particle trajectory are irrelevant; only the topology matters. This is one reason for the inherent fault tolerance of topological quantum computation. I will describe a model in which this idea is taken one step further. Even the topology is irrelevant. The computation is determined solely by the permutation of the particles. Unlike topological quantum computation, which requires anyons, permutational quantum computations can in principle be performed by permuting ordinary spin-1/2 particles. It seems possible that permutational quantum computation is less powerful than standard quantum computation (BQP). Nevertheless I will present algorithms for this model which provide apparent exponential speedup over classical algorithms. Girvin,Steven (Yale) The 'circuit QED' architecture consists of Josephson junction qubits placed inside a coplanar waveguide microwave resonator. This talk will present an introduction to the quantum optics of these novel electrical circuits and describe recent experiments in the Schoelkopf lab at Yale. With the help of a controlled phase gate based on precision control and shaping of microwave pulses, it is now possible to achieve two-qubit entanglement on demand with concurrence up to 94% and to run the Grover search and Deutsch-Josza quantum algorithms with fidelities exceeding 80%. This success is based on a qubit design with long coherence times and the ability to simultaneously readout the state of two qubits (so far still with low fidelity). :: Mon 5/4/09, 4:15 in 36-428 (QIP seminar) Broadbent,Anne (IQC) We present a protocol which allows a client to have a server carry out a quantum computation for her such that the client's inputs, outputs and computation remain perfectly private, and where she does not require any quantum computational power or memory. The client only needs to be able to prepare single qubits randomly chosen from a finite set and send them to the server, who has the balance of the required quantum computational resources. Our protocol is interactive: after the initial preparation of quantum states, the client and server use two-way classical communication which enables the client to drive the computation, giving single- qubit measurement instructions to the server, depending on previous measurement outcomes. Our protocol works for inputs and outputs that are either classical or quantum. We give an authentication protocol that allows the client to detect an interfering server; our scheme can also be made fault-tolerant. :: Mon 4/27/09, 4:15 in 34-401B (QIP seminar) Smith,Graeme (IBM) Besides transmitting ordinary classical information, some quantum channels can faithfully transmit intact quantum states. A channel's capacity for such coherent transmission, its quantum capacity, is of central importance in quantum information theory as it measures the optimum performance of quantum error-correcting codes. I will show that two quantum channels, each of zero quantum capacity, can nevertheless achieve a positive quantum capacity when used together. This result contrasts sharply with the classical setting, where the capacity of a channel is independent of what other channels are available. This uniquely quantum effect unveils a rich structure in the theory of quantum communications and shows that there are several kinds of quantum information, the ability to transmit each of which is necessary but not sufficient for faithful quantum communication. :: Mon 4/13/09, 4:15 in 36-428 (QIP seminar) Debbie Leung (University of Waterloo) Many capacities of a quantum channel are given by expressions that involve asymptotically large number of uses of the channel, thus, there is no a priori reason for the capacities to be continuous. In this talk, we prove that the ability to transmit classical data, private classical data, quantum data are all continuous. :: Mon 3/30/09, 4:15 in 36-428 (QIP seminar) Frederick Strauch (Williams College) Superconducting quantum bits are artificial atoms that can be wired up into complex structures. I will present a theoretical proposal to implement perfect quantum state transfer between any two nodes of a hypercube network. This example of novel quantum transport in an artificial solid has many applications for quantum computing. It would also provide an experimental simulation of a continuous-time quantum walk with exponential speedup over the corresponding classical walk. This speedup is found to be remarkably robust to both decoherence and diagonal disorder, but only for certain (inefficient) representations of the hypercube. :: Mon 3/16/09, 4:15 in 36-428 (QIP seminar) Aaronson,Scott (MIT) I'll describe a powerful new result about quantum advice: namely, given any state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that *any* ground state of H can be used to simulate rho on all circuits of a fixed polynomial size. In terms of complexity classes, this implies that BQP/qpoly is contained in QMA/poly, superseding the previous result that BQP/qpoly is contained in PP/poly. Indeed, we can exactly characterize the /qpoly operator, as equivalent in power to *untrusted* quantum advice combined with trusted *classical* advice. The proof of this theorem relies on my previous result about the learnability of quantum states, as well as a new combinatorial result called the "majority-certificates lemma" that might be of independent interest. Joint work with Andrew Drucker. :: Tue 2/17/09, 4:15 in 36-428 (QIP seminar) Roland,Jeremie (NEC Laboratories America) We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input x, Bob gets an input y, and their goal is to each produce an output a,b distributed according to some pre-specified joint distribution p(a,b|x,y). Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa, therefore our techniques apply to any communication problem that can be reduced to a non-signaling distribution, including quantum distributions, Boolean and non-Boolean functions, most relations, partial (promise) problems, in the two-player and multipartite settings. We give elementary proofs and very intuitive interpretations of the recent lower bounds of Linial and Shraibman, which we generalize to the problem of simulating any non-signaling distribution. The lower bounds we obtain are also expressed as linear programs (or SDPs for quantum communication). We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequalities, which was previously known only for the case of Boolean outcomes with uniform marginals. Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence of this is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication. Joint work with:Julien Degorre, Marc Kaplan and Sophie Laplante :: Mon 2/9/09, 4:30 in 4-237 (QIP seminar) Matthew Hastings (Los Alamos National Laboratory) Suppose Alice is using a noisy quantum channel to send classical information to Bob. For example, she might send single photons over a fiber optic line. How should she do this? In particular, should she use entanglement or should she send unentangled input states? The additivity conjecture in quantum information theory states that it is never useful for her to use entanglement. In fact, there are several related additivity conjectures, depending on the use of entanglement for different tasks. I will present a counter-example to one of these conjectures, the minimum output entropy conjecture, implying that all of these conjectures are false, and that in some circumstances Alice can increase the communication capacity by using entangled states. Guifre Vidal (University of Queensland) Entanglement Renormalization (ER) has been proposed as a real space renormalization group transformation for quantum lattice systems in D spatial dimensions [Phys. Rev. Lett. 99, 220405 (2007)]. Its main novelty is the use of disentanglers, namely unitary transformations that act accross a spin block boundary, to remove short-range entanglement from the system's ground state. In this talk I will first review the basic concepts underlying ER and then present a summary of the most recent results. Specifically, I intend to describe the simulation of lattice systems at a quantum critical point by exploiting scale invariance; and the simulation of two dimensional lattice systems that are beyond the reach of Monte Carlo sampling techniques, including spin models of frustrated antiferromagnets. :: Tue 1/20/09, 4:15 in 36-428 (QIP seminar) Sattath,Or (Hebrew University) In 1985, Valiant-Vazirani showed [VV85] that solving NP with the promise that "yes" instances have only one witness, is powerful enough to solve the entire NP class (under randomized reductions).We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur (MA) and Quantum- Classical-Merlin-Arthur (QCMA) [AN02].Our results have implications on the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation, within polynomial accuracy, of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard, under randomized reductions. This is in strong contrast to the case of constant gapped 1-D Hamiltonians, which is in NP [Has07]. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian which allows the efficient calculation of expectation values.Finally, we conjecture that an analogous result to the class Quantum Merlin-Arthur(QMA) is impossible. This is formulated by separating between the two relavant classes, QMA and its "unique" version UQMA, using the definition by Aaronson and Kuperberg [AK06] of quantum oracles. :: Thu 1/8/09, 4:15 in 36-428 (QIP seminar) Eban,Elad (Hebrew University) The widely held belief that BQP strictly contains BPP raises fundamental questions: Upcoming generations of quantum computers might already be too large to be simulated classically. Is it possible to experimentally test that these systems perform as they should, if we cannot efficiently compute predictions for their behavior? Vazirani has asked [Vaz07]: If computing predictions for Quantum Mechanics requires exponential resources, is Quantum Mechanics a falsifiable theory? In cryptographic settings, an untrusted future company wants to sell a quantum computer or perform a delegated quantum computation. Can the customer be convinced of correctness without the ability to compare results to predictions? To provide answers to these questions, we define Quantum Prover Interactive Proofs (QPIP).Whereas in standard Interactive Proofs [GMR85] the prover is computationally unbounded, here our prover is in BQP, representing a quantum computer. The verifier models our current computational capabilities: it is a BPP machine, with access to few qubits. Our main theorem can be roughly stated as: "Any language in BQP has a QPIP, and moreover, a fault tolerant one". We provide two proofs. The simpler one uses a new (possibly of independent interest) quantum authentication scheme (QAS) based on random Clifford elements. This QPIP however, is not fault tolerant. Our second protocol uses polynomial codes QAS due to Ben-Or, Cr?epeau, Gottesman, Hassidim, and Smith [BOCG+06],combined with quantum fault tolerance and secure multiparty quantum computation techniques. A slight modification of our constructions makes the protocol "blind": the quantum computation and input remain unknown to the prover. After we have derived the results, we have learnt that Broadbent, Fitzsimons, and Kashefi [BFK08] have independently derived "universal blind quantum computation" using completely different methods (measurement based quantum computation). Their construction implicitly implies similar implications. :: Mon 12/8/08, 4:15 in 36-428 (QIP seminar) Zeng,Bei (MIT) ``Quantum Error Correction via Codes Over GF(4)" is one of the seminal papers in quantum coding theory. This 1996 work transforms the problem of finding binary quantum-error-correcting codes into the problem of finding additive codes over the field GF(4) which are self-orthogonal with respect to a certain trace inner product. Ever since then, these codes, called additive codes or stabilizer codes, have dominated the research on quantum coding theory. There is now a rich theory of stabilizer codes, and a thorough understanding of their properties. Nevertheless, there are a few known examples of nonadditive codes which outperform any possible stabilzer code. In previous work, my colleagues and I introduced the codeword stabilized quantum codes framework for understanding additive and nonadditive codes. This has allowed us to find, using exhaustive or random search, good new nonadditive codes. However, these new codes have no obvious structure to generalize to other cases. A systematical understanding of constructing nonadditive quantum codes is still lacking. In this talk, we introduce the idea of constructing binary quantum- error-correcting codes via classical codes over the field GF(3). Quantum codes directly constructed this way are nonadditive codes adapted to the amplitude damping channel. These codes have higher performance than all the previous codes for the amplitude damping channel. We then further generalize this GF(3) idea to the case of constructing 'usual' binary quantum codes for the depolarizing channel, which leads to a systematical way of constructing good nonadditive codes that outperform best additive codes. Using this method, many good new codes are found. Particularly, we construct families of good nonadditive codes which not only ourperform any additive codes, but also asymptotically achieve the quantum Hamming bound. Generalization to nonbinary case is straightforward and families of good nonadditive nonbinary quantum codes are found. What is more, our new method can also be used to construct additive codes, and additive codes with better parameters than previous known are found. Based on joint work with Markus Grassl, Peter Shor, Graeme Smith, and John Smolin. :: Mon 12/1/08, 4:15 in 36-428 (QIP seminar) Wootters,William (Williams College) For a joint measurement on a pair of spatially separated quantum objects, one can ask how much entanglement is needed to carry out the measurement using only local operations and classical communication. In this talk I focus on a particular orthogonal measurement on two qubits with partially entangled eigenstates, for which we can find upper and lower bounds on the entanglement cost. The lower bound implies that the entanglement required to perform the measurement is strictly greater than the average entanglement of the eigenstates. I also consider other examples, including a simple two-qubit product- state measurement that cannot be performed locally. :: Mon 11/24/08, 4:15 in 36-428 (QIP seminar) Verstraete,Frank The theory of entanglement and of quantum computational complexity is providing valuable new insights into the problem of simulating strongly correlated quantum many-body systems. We will discuss recent progress in that field. :: Mon 11/17/08, 4:15 in 36-428 (QIP seminar) Aliferis,Panos (IBM) Experimentalists in quantum computing observe that in many of their systems noise is biased---i.e., loss of phase coherence in the computational basis occurs faster than relaxation to the lowest energy eigenstate or leakage outside the computational subspace. I will discuss a scheme for fault-tolerant quantum computation that is especially designed to protect against biased noise. The scheme is particularly effective when the noise bias is very high, with dephasing dominating other types of noise by three orders of magnitude or more. To illustrate how this scheme could be relevant for future experiments, I will discuss the design of a universal set of biased-noise operations for the superconducting flux qubit investigated at the IBM labs. :: Wed 10/22/08, 3:00 in 36-428 (special seminar) William Oliver (MIT Lincoln Laboratory) In this talk, we will present an overview of our superconductive quantum computing effort. In collaboration with Lincoln?s Solid State Division (Division 8) and the MIT campus, we have fabricated superconductive artificial atoms, actively cooled them to near absolute zero, and demonstrated new broadband spectroscopy techniques along with the more conventional Rabi, Ramsey, and spin-echo metrics to characterize their coherence. These artificial atoms form the fundamental building blocks, ?qubits,? of a quantum information processor. We have developed and simulated a universal set of gate operations capable of low error rates to control these qubits. Today, we are working to improve single-qubit coherence while coupling these qubits into more complicated circuit elements. The talk will present a review of our progress and future work. :: Mon 10/20/08, 4:15 in 36-428 (QIP seminar) Kenneth Brown (Georgia Institute of Technology) A quantum simulation is a map of the dynamics of a target quantum system onto a control quantum system. A quantum computer is a control quantum system that can simulate any target quantum system. In this talk, we describe two cases of quantum simulations in the presence of errors. In the first case, we examine a control quantum system that simulates the target system in an interaction picture. Although the control system simulates the dynamics, it does not simulate the thermodynamics of the target system. This is an important distinction when the target system represents a Hamiltonian with proposed error-correcting properties. In the second case, we use a model of a fault-tolerant quantum architecture to evaluate the resource cost of evaluating the ground state energy of the target quantum system. The resources are compared to performing Shor's algorithm on the same model. Simulations of modest accuracy on 10's of qubits are found to have comparable cost, in the product of computational time and space (KQ), to the factoring of 1024 bit numbers. :: Mon 10/6/08, 4:15 pm in 36-428 (QIP seminar) Hassidim,Avinatan (MIT) Quantum Multi Prover Interactive Proofs (QMIP) can provide us with important insights to the capabilities of entanglement. The talk will present some known models and insights they give. We introduce a variant of the model, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap. The main idea is not to bound the information the provers exchange with each other, as in the classical case, but rather to prove that any ``cheating'' strategy employed by the provers has constant probability to diminish the entanglement between the verifier and the provers by a constant amount. Detecting such reduction gives us the soundness proof. Similar ideas and techniques may help help with other models of Quantum MIP, including the dual question, of non communicating provers with unlimited entanglement. :: Mon 9/8/08, 4:15 pm in 36-428 (QIP seminar) Sergey Bravyi (IBM) We study properties of additive quantum error-correcting codes (QECC) that permit a local description on a regular D-dimensional lattice. Specifically, we assume that the stabilizer group of a code has a set of local generators such that support of any generator can be bounded by a rectangular box of size $r=O(1)$. Our first result concerns the optimal scaling of the distance $d$ with the linear size of the lattice $L$. We establish an upper bound $dle r L^{D-1}$ which is tight for $D=1,2$. We also prove a bound $d=O(1)$ for one-dimensional subsystem codes assuming that the gauge group of a code has a set of local generators. Secondly we analyze suitability of various QECCs for building a self-correcting quantum memory. Any additive QECC with geometrically local generators can be naturally converted to a local Hamiltonian that penalizes states violating the stabilizer conditions. A degenerate ground state of this Hamiltonian corresponds to the logical subspace of a code. We prove that for $D=1,2$ the height of an energy barrier separating different logical states is upper bounded by a constant independent of the lattice size $L$. This result demonstrates that a self-correcting quantum memory cannot be build using additive QECC in dimensions $D=1,2$. :: Thu 9/4/08, 3:00 pm in 24-307 (special seminar) Paola Cappellaro (Harvard) The development of new technologies at scales approaching the quantum regime is driving new theoretical and experimental research on control in quantum systems. The implementation of quantum control would have an enormous impact on a wide range of fields, in particular in quantum information processing and precision metrology. In this talk Dr. Cappellaro will present the application of coherent control techniques to the electronic and nuclear spins associated with Nitrogen-Vacancy (NV) centers in diamond. These systems have emerged as excellent candidates for quantum information processing, since they can be optically polarized and detected, and present good coherence properties even at room temperature. She will first show how this solid state system can be used as the building block of a scalable architecture for quantum computation or communication,then present a novel approach to magnetometry, based on NV centers, that takes advantage of coherent control techniques and the confinement of the sensing spins into a sample of nanometer dimensions. The resulting magnetic sensor is projected to yield an unprecedented combination of ultra-high sensitivity and spatial resolution, with the potential of exciting applications in bioscience, materials science, and single electronic and nuclear spin detection. :: Wed 9/3/08, 3:00 pm in Mallinckrodt M213 (12 Oxford st, across from science center) (special seminar) Alexandra Olaya-Castro Photosynthetic structures are finely tuned to capture solar light efficiently and transfer it to molecular reaction centres for conversion into chemical energy with 950r more efficiency. How photosynthetic structures achieve such a high-efficiency is still a long-standing question in science. Fundamental breakthroughs towards answering this question have recently been achieved. In particular, direct evidence of long-lasting electronic coherence during excitation transfer in photosynthetic complexes has been obtained. In this talk I will discuss our recent work on the energy transfer efficiency in a photosynthetic core where a light harvesting antenna is connected to a reaction centre as in purple bacteria. By using a quantum jump approach, we demonstrate that in the presence of quantum coherent energy transfer and energetic disorder, the transfer efficiency from the antenna to the reaction centre depends intimately on the quantum superposition properties of the initial state. This indicates that initial state properties could be used as an efficiency control parameter. Our results open up experimental possibilities to investigate and exploit such coherent phenomena in artificial and natural systems capable of harvesting light. :: Mon 6/9/08, 3:00pm in 6C-442 (QIP seminar) Peter Young (UCSC) We study the minimum gap in the quantum version of the Exact Cover problem using Quantum Monte Carlo simulations, with a view to understanding the complexity of the quantum adiabatic algorithm for much large sizes than was possible before. For a range of sizes, N <= 128, where the classical Davis-Putnam algorithm shows exponential complexity, the quantum adiabatic algorithm shows polynomial complexity. The bottleneck of the algorithm is an isolated avoided crossing point of a Landau-Zener type (collision between the two lowest energy levels only). (from arXiv:0803.3971) :: Mon 5/12/08, 4:15pm in 36-428 (QIP seminar) Carlos Mochon (Perimeter Institute) Coin flipping by telephone (Blum '81) is one of the most basic cryptographic tasks of two-party secure computation. In a quantum setting, it is possible to realize (weak) coin flipping with information theoretic security. :: Mon 5/5/08, 4:15pm in 36-428 (QIP seminar) Barbara Terhal (IBM) We show how to map a given n-qubit target Hamiltonian with bounded-strength k-body interactions onto a simulator Hamiltonian with two-body interactions, such that the ground-state energy of the target and the simulator Hamiltonians are the same up to an extensive error O(epsilon n) for arbitrary small epsilon. The strength of interactions in the simulator Hamiltonian depends on epsilon and k but does not depend on n. We accomplish this reduction using a new way of deriving an effective low-energy Hamiltonian which relies on the Schrieffer-Wolff transformation of many-body physics. :: Mon 4/14/08, 4:15pm in 36-428 (QIP seminar) Michel Devoret (Yale) Can the collective variables that describe the state of a radio-frequency circuit, in other words currents and voltages, behave quantum-mechanically? Is it possible to have in a wire a quantum superposition of currents flowing simultaneously in two opposite directions? Integrated superconducting circuits employing Josephson junctions as purely dispersive non-linear elements are sufficiently non-dissipative at low temperatures that coherent effects of this kind can not only manifest themselves, but dominate the dynamics of the circuit. Josephson junctions, together with transmission lines and capacitors, form a basic "Lego set" for the implementation of an arbitrary quantum Hamiltonian. In particular, the quantization of energy levels of the circuit, together with interference phenomena displayed by coherent population of these levels, can radically differ from the usual manifestations of microscopic superconductivity and emulate many situations encountered in quantum optics and NMR. We will give a short review of latest experiments in this field, which saw recently the development of entangled solid-state qubits and the observation of single photons in a microwave resonator. Finally, we will discuss the prospects of these circuits for implementing a complete set of primitives for a quantum information processor. :: Mon 4/7/08, 4:15pm in 36-428 (QIP seminar) John Watrous (Waterloo) Little is known about the expressive power of multi-prover quantum interactive proof systems. At one extreme it is not known if multiple provers give more computational power than just a single prover, and at the other extreme it is not even known if every problem having a multi-prover quantum interactive proof is computable. The difficulty in both cases centers on shared entanglement, and in understanding the strategies that it allows multiple provers to implement. :: Mon 3/31/08, 4:15pm in 36-428 (QIP seminar) Alain Tapp (Montreal) I will present the first protocol for the anonymous transmission of a quantum state that is information-theoretically secure against an active adversary, without any assumption on the number of corrupt participants. The anonymity of the sender and receiver is perfectly preserved, and the privacy of the quantum state is protected except with exponentially small probability. Even though a single corrupt participant can cause the protocol to abort, the quantum state can only be destroyed with exponentially small probability: if the protocol succeeds, the state is transferred to the receiver and otherwise it remains in the hands of the sender (provided the receiver is honest). :: Mon 3/17/08, 4:15pm in 36-428 (QIP seminar) Markus Grassl (Innsbruck) Most of the quantum error-correcting codes (QECCs) are based on the stabilizer formalism which relates quantum codes to certain additive codes over GF(4). However, it is known that non-additive QECCs can have a higher dimension compared to additive QECCs with the same length and minimum distance. The most prominent example is the code ((5,6,2)) of Rains et al. More recently, some improved one-error-correcting codes of length 9 and 10 have been found. So far, all these non-additive QECCs are obtained as the complex span of some stabilizer or graph states. :: Mon 3/10/08, 4:30pm in 2-105 (applied math) Alexei Ashikmin (Lucent-Alcatel) A complex Grassmannian packing is a collection of m-dimensional subspaces in a complex space of dimension n, m :: Mon 3/3/08, 4:15pm in 36-428 (QIP seminar) Runyao Duan (Tsinghua) In 1956 Shannon introduced the notion of zero-error capacity to characterize the ability of noisy channels to transmit classical information with zero probability of error. The study of this notion and the related topics has since then grown into a vast field called zero-error information theory. In this talk we will study the quantum counterpart of this notion within the following communication framework: m senders want to transmit classical information to n receivers with zero probability of error using a noisy communication channel. The senders are allowed to exchange classical, but not quantum, messages among themselves, and the same holds for the receivers. It is well known that if the channel is classical, a single use can transmit information perfectly if and only if multiple uses can. In sharp contrast, we exhibit, for each m and n with m>1 or n>1, a quantum channel of which a single use is not able to transmit information yet two uses can. This latter property requires and is enabled by quantum entanglement. For the case of m=1 and n=1, we propose a weaker notion of error-free classical capacity to describe the ability of a quantum channel to transmit classical information unambiguously. Then we construct explicitly a quantum channel that has positive error-free classical capacity but only when entangled input states are allowed. We further examine the effect of additional resources such as shared entanglement between the sender and the receiver, classical feedback, and quantum feedback. We find these resources are extremely useful as they not only can dramatically increase both the zero-error and error-free capacities, but also can greatly simplify the calculation of these capacities in many cases. This talk is based on joint works with Yaoyun Shi (University of Michigan). :: Mon 2/11/08, 4:15pm in 36-428 (QIP seminar) John Smolin (IBM) I will describe an approach to quantum error correcting code design that encompasses additive (stabilizer) codes, as well as all known examples of nonadditive codes with good parameters. Our quantum codes are described by a single graph state, together with a classical binary code. The graph state may be thought of as mapping quantum errors to an exotic classical error model, which we must then arrange to correct with our classical code. Stabilizer codes arise naturally as those quantum codes with a linear classical code. I will show how to use this framework to generate new codes with superior parameters to any previously known, as well as construct encoding circuits for all codes within this family. :: Mon 1/14/08, 3pm in 6-310 (QIP seminar) Avinatan Hassidim (Hebrew University, Jerusalem) We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: :: Mon 12/10/07, 4pm in 36-428 (QIP seminar) Giacomo Mauro D'Ariano (Pavia) A method method for optimizing quantum circuits architecture is presented. The method is based on the notion of "quantum comb", which describes a circuit board in which one can insert variable subcircuits, and mathematically corresponds to a generalization of the notions of quantum operation and POVM. The method allows to address novel kinds of quantum processing tasks, such as optimal storing-retrieving and cloning of channels, and optimal quantum circuit board testers. :: Mon 12/3/07, 4pm in 36-428 (QIP seminar) Saikat Guha (MIT RLE) Determining the ultimate classical information carrying capacity of electromagnetic waves requires quantum-mechanical analysis to properly account for the bosonic nature of these waves. Our previous work has established capacity theorems for the bosonic single-user channel with additive thermal noise, under the presumption of a minimum output entropy conjecture. More recent work has established capacity theorems for the bosonic broadcast, and wiretap channels under the presumption of a second minimum output entropy conjecture, which is in some sense the dual of the first conjecture. Now, with Graeme Smith's recent results on the equivalence of privacy capacity and the quantum capacity of degradable quantum channels, proving the second minimum output entropy conjecture would also establish the quantum capacity of the single-user lossy bosonic channel. Despite considerable accumulated evidence that supports the validity of these conjectures, they have yet to be proven. Both conjectures have been proven if the input states are restricted to be Gaussian, and we have shown that they are equivalent under this input-state restriction. The Entropy Power Inequality (EPI) from classical information theory is widely used in coding theorem converse proofs for Gaussian channels. By analogy with the EPI, we conjecture its quantum version, viz., the Entropy Photon-number Inequality (EPnI). In this talk we show that the preceding two minimum output entropy conjectures are simple corollaries of the EPnI. Hence, proving the EPnI would immediately establish key results for the capacities of bosonic communication channels. :: Mon 11/19/07, 4pm in 36-428 (QIP seminar) Mohammad Amin (D-Wave) Adiabatic quantum computation (AQC) is an attractive model of quantum computation as it may naturally possess some degree of fault tolerance. Nonetheless, any practical quantum circuit is noisy and one must answer important questions regarding what level of noise can be tolerated. Gate model quantum computation relies on three important quantum resources: superposition, entanglement, and phase coherence. In this presentation, I will discuss the role of these three resources and the effect of environment upon them with respect to AQC. I will also show a close relation between open AQC and incoherent tunneling processes as in a double-well potential. At a more microscopic level, I will present a non-Markovian theory for macroscopic resonant tunneling, together with recent experimental results on superconducting flux qubits which demonstrate excellent agreement with the theory and may shed light on the microscopic origin of flux noise in these devices. Finally, I will discuss the effect of low and high frequency noise on practical AQC processors and compare AQC with thermal annealing. :: Wed 11/7/07, 11am in 36-428 (rle) Richard Hughes (LANL) ... :: Mon 11/5/07, 4pm in 36-428 (QIP seminar) Pawel Wocjan (UCF) We construct a translation invariant finite-range interaction on a one-dimensional qudit chain and prove that a single-shot measurement of the energy of an appropriate computational basis state with respect to this Hamiltonian provides the output of any quantum circuit. The required measurement accuracy scales inverse polynomially with the size of the simulated quantum circuit, showing that the implementation of energy measurements on generic qudit chains is as hard as the realization of universal quantum computation. Here a measurement is any procedure that samples from the spectral measure induced by the observable and the state under consideration. :: Thu 11/1/07, 3pm in 6C-442 (ctp) Sahel Ashhab (RIKEN) I will talk about two applications of the Landau-Zener problem in quantum computing systems. In the first part of the talk, I will discuss the effect of noise on adiabatic quantum computing (AQC). The main message of this part is that noise effects should be treated more seriously in the study of AQC than has been done in the past. In the second part of the talk, I will present a geometric picture for understanding recent experiments on strongly driven two-level systems. In such a system, one can understand the dynamics as being constructed from a sequence of simple, finite rotations. In addition to its conceptual simplicity, this approach allows the derivation of quantitative results where other theoretical methods fail. :: Mon 10/29/07, 4pm in 36-428 (QIP seminar) Umesh Vazirani (UC Berkeley) Are there natural computation problems with exponential quantum speedups beyond the abelian hidden subgroup problems. The recent sequence of negative results about the non-abelian hidden subgroup problem rules out a promising direction. In this talk I will outline a proposal where rather than increasing complexity by moving to non-abelian groups, the challenge is to find hidden non-linear structures in an abelian setting. We show that for certain hidden quadratic structures, quantum algorithms provably give an exponential speedup over classical algorithms in a black-box setting. :: Mon 10/22/07, 4pm in 36-428 (QIP seminar) Cris Moore (UNM) It is known that any quantum algorithm for Graph Isomorphism that works within the framework of the hidden subgroup problem must perform highly entangled measurements across many coset states. One of the only known models for how such a measurement could be carried out efficiently is Kuperberg's "quantum sieve" for the dihedral group. However, I will discuss joint work with Alex Russell and Piotr Sniady in which we show that no such approach, no matter what rule we use to combine coset states in the sieve, can produce an improvement over known classical algorithms for Graph Isomorphism. :: Mon 10/15/07, 4pm in 36-428 (QIP seminar) Yaoyun Shi (Michigan) A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical protocols on total Boolean functions in the standard two-party interactive model. The answer appears to be "No''. In 2002, Razborov proved this conjecture for so far the most general class of functions :: Wed 10/10/07, 3pm in 26-214 (QIP seminar) Graeme Smith (IBM) In classical information theory there is a neat formula for the private capacity of a channel. This problem has two quantum analogs, the private classical capacity of a quantum channel, and the quantum capacity (necessarily private) of a quantum channel, neither of which is as nice. Indeed, these capacities are unknown for all but a handful of channels. I discuss these capacities in a scenario supplemented by a symmetric side channel, which by itself has no quantum or secret capacity. Including this extra resource results in a dramatic simplification?the capacities are additive, convex, and single letter?and gives strong upper bounds on the unassisted capacities of several channels of interest. :: Mon 10/1/07, 4pm in 36-428 (QIP seminar) Seth Lloyd (MIT) The Supreme Court has decided that the Constitution does not guarantee a right to privacy. Luckily, the laws of physics do. Suppose that Larry has a database containing valuable information. You want to ask that database a question, and are willing to pay good money for the answer. Larry wants to give you the answer and take your money. But you want a guarantee that, when you receive your answer, Larry no longer knows your question. Quantum mechanics supplies such a guarantee. This talk describes the protocol for conducting such Quantum Private Queries. Quantum Private Queries are exponentially more efficient than classical techniques for Private Information Retrieval, and supply unique guarantees for the privacy of the questioner and for the owner of the database. :: Mon 9/24/07, 4pm in 36-428 (QIP seminar) Iordanis Kerenidis (Universite Paris-Sud) Statistical Zero-Knowledge (SZK) is a very important notion in cryptography and complexity Theory. In this model, a Prover possesses a secret and he interacts with a Verifier, so that the Verifier is convinced that the Prover knows the secret, however learns nothing about the secret itself. Unfortunately, we do not know how to achieve classical SZK proofs for the class NP, even if we restrict ourselves to the case of Honest Verifiers. Here, we show that by slightly modifying the definition of quantum Zero-Knowledge given by Watrous, we can achieve quantum honest verifier SZK proofs for all Interactive Proofs, i.e. for the class IP=PSPACE. :: Mon 9/17/07, 4pm in 36-428 (QIP seminar) Patrick Hayden (McGill) The maximal p-norm multiplicativity conjecture is a natural strengthening of the additivity conjecture of quantum information theory. The additivity conjecture implies, among other things, that using entangled codewords can't improve the classical information-carrying capcity of a quantum channel. A proof of the multiplicativity conjecture for p in a neighborhood (1,1+x) would have implied the more important additivity conjecture. The multiplicativity conjecture, however, is false. In this talk I'll present counterexamples for all p>1. I'll then discuss the curious obstinacy of the additivity conjecture and why it seems to be unscathed by these examples. :: Mon 9/17/07, 12noon in 4-331 (CMT Chez Pierre) Masud Haque (MPI Dresden) I will first give an overview of recent uses of entanglement concepts from quantum information to probe quantum many-particle physics. I particular, I will focus on the entropy of entanglement between regions of a topologically ordered state. :: Thu 9/13/07, 4pm in 36-428 (RLE) Masahide Sasaki and Masahiro Takeoka (NGNRC, National Institute of Information and Communications Technology) We first review the outline of quantum info-communications research in NICT, by introducing the activities on quantum cryptography and quantum information processing. We then focus on some detail of quantum information processing. After explaining our original motivation to use it for quantum channel coding, we present our recent results on the non-Gaussian control of continuous variables. They include experimental generation of Schroedinger kittens with even and odd parities with negative Wigner functions. Finally we present our theoretical study on quantum receiver, which is a typical application of such non-Gaussian operations. :: Mon 9/10/07, 2pm in 6-310 (QIP seminar) Aram Harrow (Bristol) The additivity conjecture in quantum information theory states that entangled inputs cannot improve the rate at which classical messages can be sent over quantum channels, or equivalently that the minimum output entropy of two copies of a channel is achieved by unentangled inputs. This conjecture can be generalized by replacing von Neumann entropy with p-Renyi entropy, since the p=1 Renyi entropy is the same as the von Neumann entropy. Recently, counterexamples to this generalized additivity conjecture have been found by Dupuis, Hayden, Leung and Winter for all p>1. In this talk, I will describe counterexamples to additivity for p=0 and for a small range of p near 0. Like the p>1 counterexamples, these are also based on a randomized construction. However, we also have an explicit channel from 4 to 3 dimensions whose minimum output Renyi entropy is non-additive for all p<0.01. :: Mon 5/21/07, 4pm in 26-214 (QIP seminar) Peter Love (Haverford) Quantum simulation provides an interesting application of quantum computing, based on the idea that one quantum system can emulate another. On the other hand, most quantum algorithms which provide speedups over known classical algorithms rely on group- and representation-theoretic constructions such as the generic fourier transform. How are these two branches of quantum computing related? In this talk I will describe a class of quantum cellular automata based on finite groups, describe some of their properties, and discuss their relevance to the quantum computational complexity of quantum dynamics. :: Wed 5/16/07, 4pm in 26-214 (special seminar) Lorenza Viola (Dartmouth) Generalized entanglement has recently emerged as a unifying framework capable of overcoming the limitations of standard subsystem-based entanglement and of bridging to various physical and information-theoretic aspects of "complexity". After reviewing the essential background underlying the generalized entanglement notion, I will focus on highlighting applications where the latter genuinely expands conventional entanglement settings -- including indecomposable quantum systems, indistinguishable fermions, and chaotic quantum systems. I will then turn the attention to address "classicality" properties of generalized un-entangled states -- by showing how, under appropriate assumptions, they both minimize uncertainty as quantified by the quantum Fisher information and emerge as "pointer states" under decoherence. :: Mon 5/14/07, 4pm in 26-214 (QIP seminar) Itai Arad (Hebrew U, Jerusalem) I will present an efficient quantum algorithm for an additive approximation of the famous Tutte polynomial of any planar graph at any point. The Tutte polynomial captures an extremely wide range of interesting combinatorial properties of graphs, including the partition function of the q-state Potts model. This provides a new class of quantum complete problems. :: Mon 5/7/07, 4pm in 26-214 (QIP seminar) Dave Bacon (U. of Washington) In nearly every quantum algorithm which exponentially outperfroms the best classical algorithm the quantum Fourier transform plays a central role. Recently, however, cracks in the quantum Fourier transform paradigm have begun to emerge. In this talk I will discuss one such development which arises in a new efficient quantum algorithm for the Heisenberg hidden subgroup problem. In particular I will show how considerations of symmetry for this hidden subgroup problem lead naturally to a different transform than the quantum Fourier transform, the Clebsch-Gordan transform over the Heisenberg group. Clebsch-Gordan transforms over finite groups thus appear to be an important new tool for those attempting to find new quantum algorithms. [Part of this work was done in collaboration with Andrew Childs (Caltech) and Wim van Dam (UCSB)] :: Mon 4/30/07, 4pm in 26-214 (QIP seminar) Navin Khaneja (Harvard) In this talk, we motivate the study of certain coset spaces that arise naturally in problems of time optimal control of coupled quantum dynamics. We show that problem of efficient synthesis of quantum circuits can be approached by study of geodesics on these spaces. Specifically, the role of certain symmetric spaces and Kostant's convexity in problems of optimal control of coupled nuclear spin dynamics and electron-nuclear spin dynamics will be discussed. I will discuss the role of Lie algebras in understanding robust manipulation of quantum dynamics that can compensate for various errors and dispersions. Finally, we introduce a class of control systems that help to compute the reachable sets to quantum dynamics in the presence of decoherence. We use these ideas to compute the maximum coherence or polarization that can be transferred between coupled spins in presence of relaxation. Application of these methods to design of multidimensioal experiments in Protein NMR spectroscopy will be discussed. :: Mon 4/23/07, 4pm in 26-214 (QIP seminar) Ivan Deutsch (UNM) Spins in cold atomic gases are a clean platform for exploring quantum control and information processing, given their long coherence times and our ability to manipulate them with a variety of electromagnetic fields ranging from quasi-static magnetic to optical. In this seminar I will present a variety of QIP protocols including quantum-state preparation through optimal control, nondestructive quantum-state reconstruction through continuous measurement, and collective spin control for studies of nonlinear dynamics, quantum chaos, and quantum phase transitions. The interplay of theory and experiment has played an important role in the development of these protocols. Experimental results from the laboratory of my collaborator, Prof. Poul Jessen, University of Arizona, will also be presented. :: Mon 4/2/07, 4pm in 26-214 (QIP seminar) Seth Lloyd (MIT) TBA :: Mon 3/19/07, 4pm in 26-214 (QIP seminar) Jacob Taylor (MIT) Creating and controlling small quantum systems (with only a few qubits) has been the focus of most experiments in quantum information over the past decade. In contrast, proposals for quantum information processing largely rely upon a robust collection of thousands or millions of qubits in a single, deterministic system with small error rates. In this talk I will discuss some approaches to using modest, non-deterministic resources (such as probabilistic entanglement generation) and small quantum registers for robust quantum communication and information processing. Both physical implementation ideas and error correction procedures will be considered. :: Mon 3/12/07, 3pm in 34-401A (EECS) Scott Aaronson (Waterloo) In the popular imagination, quantum computers would be almost magical devices, able to "solve impossible problems in an instant" by trying exponentially many solutions in parallel. In this talk, I'll describe four results in quantum computing theory that directly challenge this view. :: Mon 2/26/07, 4pm in 26-214 (QIP seminar) Guifre Vidal (University of Queensland) I will describe a renormalization group transformation for strongly correlated quantum systems in D spatial dimensions based on ideas from quantum computation and quantum information (quantum circuits, entanglement, ...). Entanglement renormalization can be used to study extended quantum systems in a symmetry breaking phase, as well as quantum phase transitions between two such phases [cond-mat/0512165, quant-ph/0610099]. Recently it has been realized that it also offers a natural framework to describe systems with topological order. I will attempt to present an overview of these results directed to a mixed audience of researchers in theoretical quantum computation/information and condensed matter. :: Mon 12/11/06, 4pm in 26-214 (QIP seminar) Richard Cleve (Waterloo) The Bell Inequalities and their violation by entangled systems are among the most intriguing observable consequences of quantum mechanics. What happens if multiple tests of such inequalities are performed in parallel? Barrett et al have shown that, for the CHSH inequality, there exists a classical strategy that passes two tests with probability greater than the product of the individual optimal success probabilities. We show that, in contrast to this, quantum strategies for a wide class of tests (called XOR games) are multiplicative. More precisely, for this class of tests, the optimal quantum success probability for passing multiple tests is exactly the product of the individual optimal success probabilities. This can be interpreted in the language of computer science as a perfect parallel repetition theorem for a class of multiprover interactive proof systems. (This is joint work with William Slofstra, Falk Unger, and Sargavya Upadhyay. A preliminary version of the paper is available at quant-ph/0608146.) :: Mon 12/4/06, 4pm in 26-214 (QIP seminar) Hideo Mabuchi (Caltech) Laser cooling and precision spectroscopy provide powerful tools for exploring quantum measurement and metrology using atoms as sensors. In this talk I will discuss our ongoing work to bring together abstract ideas of quantum parameter estimation and detailed physical modeling of atomic-photon interactions in the specific context of magnetometry. I will also present some new ideas on how laser probing of cold atoms could provide a basis for developing entanglement-enhanced spin gyroscopes. :: Mon 11/27/06, 4pm in 26-214 (QIP seminar) Alan Aspuru-Guzik (Harvard) The calculation time for the energy of atoms and molecules scales exponentially with system size on a classical computer, but polynomially using quantum algorithms. We demonstrate that such algorithms can be applied to problems of chemical interest using modest numbers of quantum bits. Calculations of the H2O and LiH molecular ground-state energies have been carried out on a quantum computer simulator using a recursive phase estimation algorithm. The recursive algorithm reduces the number of quantum bits required for the read-out register from approximately twenty to four. Mappings of the molecular wave function to the quantum bits are described. An adiabatic method for the preparation of a good approximate ground-state wave function is described and demonstrated for stretched H2. The number of quantum bits required scales linearly with the number of basis functions used and the number of gates required grows polynomially with the number of quantum bits. Our current work on methods for obtaining excited states of molecular systems is summarized. :: Mon 11/20/06, 4:30pm in 2-105 (applied math colloquium) Rob Calderbank (Princeton) We describe a mathematical framework for detection and estimation that applies to domains as different as remote sensing and quantum information theory. :: Thu 11/16/06, 12pm in Lyman 425 @ Harvard (Harvard Condensed Matter Theory Seminar) Lev Ioffe (Rutgers) ... :: Mon 11/13/06, 4pm in 26-214 (QIP seminar) Elham Kashefi (Oxford) Despite the extensive research on measurement-based quantum computing it remains an open question however, whether this model may suggest new techniques for designing quantum algorithms. We address this question positively by introducing a novel methodology for direct decomposition of a given unitary map into a measurement pattern. The core observation is that measurement patterns implicitly define a particular decomposition of unitary maps into a preparation map enlarging the input space, a diagonal map with unit coefficients, and a restriction map contracting back the space to the output space, called a phase map decomposition. This constitutes a heuristic method for the implementation of unitary maps in the measurement model which bypasses completely the circuit picture, and may produce more efficient implementations in particular instances. (joint work with N. de Beaudrap and V. Danos) :: Mon 11/6/06, 4pm in 26-214 (QIP seminar) Ben Reichardt (Berkeley) The fragile nature of quantum superpositions makes it particularly important to design robust schemes for fault-tolerant quantum computation. Over the last couple of years, new schemes for achieving fault tolerance based on error detection, rather than error correction, appear to tolerate as much as 3-6% noise per gate -- an order of magnitude better than previous schemes, although with higher overhead. But proof techniques could not show that these promising fault-tolerance schemes tolerated any noise at all. :: Mon 10/30/06, 4pm in 26-214 (QIP seminar) Rolando Somma (LANL) If a large quantum computer (QC) existed today, what type of physical problems could we efficiently simulate on it that we could not simulate on a conventional computer? In this talk, I argue that a QC could solve some relevant physical "questions" more efficiently. First, I will focus on the quantum simulation of quantum systems satisfying different particle statistics (e.g., anyons), using a QC made of two-level physical systems or qubits. The existence of one-to-one mappings between different algebras of observables or between different Hilbert spaces allow us to represent and imitate any physical system by any other one (e.g., a bosonic system by a spin-1/2 system). We explain how these mappings can be performed showing quantum networks useful for the efficient evaluation of some physical properties, such as correlation functions and energy spectra. :: Fri 10/27/06, 4pm in 32-123 (RLE) David DiVincenzo (IBM) The idea of quantum computing looks natural and inevitable today, but at its emergence less than twenty-five years ago, it looked inspired and incredible. Please join us as Dr. David P. DiVincenzo, Research Staff Member in the Physical Sciences Department at the IBM T. J. Watson Research Center in Yorktown Heights, NY., traces at least three independent threads of thought that launched the field, one of which is tied up with the origins of RLE. Dr. DiVincenzo will argue that once we had quantum circuit rules, a notion of secure quantum-bit transmission, and above all, Shor's factoring algorithm, there was no turning back. Dr. DiVincenzo will survey the plethora of activities that are now underway to build a quantum computer, with particular examples from IBM's current work to create a quantum-mechanical world in low-temperature electric circuits. :: Mon 10/23/06, 4pm in 26-214 (QIP seminar) Martin Roetteler (NEC labs) Quantum convolutional codes can be used to protect a stream of quantum bits against errors when sending them along a quantum channel. We review the code conditions for quantum convolutional codes, give some basic code constructions, and motivate the notion of catastrophic errors. We present an algorithm to compute a constant depth quantum circuit which can be used to perform non-catastrophic encoding and inverse encoding. We also show that the encoders and their inverses constructed by our method naturally can be applied online, i.e., qubits can be sent and received with constant delay. :: Mon 10/16/06, 4pm in 26-214 (QIP seminar) Zeph Landau (CCNY) It has been known for some time that quantum computation is equivalent to approximating the Jones polynomial at certain roots of unity. This result, due to Friedman, Kitaev, Larsen, Wang, was presented in the language of topological quantum field theories and was not widely understood by the quantum computing community. :: Mon 9/18/06, 4pm in 26-214 (QIP seminar) Sergey Bravyi (IBM) Ground state problems for interacting quantum spins are analyzed using techniques from complexity theory. I focus on the problem of evaluating the smallest eigenvalue of a spin Hamiltonian with non-positive matrix elements. This problem is shown to be contained in the complexity class AM and be hard for the class MA (probabilistic analogues of NP with one (MA) and two (AM) rounds of communication between the prover and the verifier). I also consider the smallest eigenvalue problem for frustration free Hamiltonians (quantum analogue of k-SAT) and prove that it is MA-complete. If no restrictions on the matrix elements are imposed, both problems are complete for QMA --- quantum analogue of NP. These results can be viewed as a strict version of folklore knowledge: Hamiltonians avoiding the "sign problem" are easy to simulate. :: Fri 9/8/06, 2:30pm in 3-370 (MechE seminar) Navin Khaneja (Harvard) In this talk I will describe applications of control theory to problems that arise in manipulation of coupled spin dynamics in nuclear magnetic resonance (NMR) spectroscopy using radio frequency pulses. In control and manipulation of quantum systems, the system of interest is rarely isolated but interacts with its environment. This leads to relaxation which in practice results in signal loss and limits the range of applications. I will present our work on optimal design of rf pulse sequences for minimizing relaxation losses and improving the sensitivity of experiments. I will motivate the study of class of optimal control problems ranging from time optimal control of dynamical systems evolving on compact Lie Groups to computing the reachable sets of dissipative control systems. Applications of these optimal control methods to NMR spectroscopy of very large proteins in solution will be discussed. These experiments involve steering an ensemble of quantum systems, which show dispersion in the parameters that govern their dynamics. This gives rise to interesting control problems of steering a continuum of dynamical systems with different dynamics using the same control signal that can compensate for the various dispersions. I will discuss our work on controllability of quantum ensembles. :: Mon 5/15/06, 4pm in 26-214 (QIP seminar) Scott Aaronson (Waterloo) Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, I'll show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n, and polynomially with certain error parameters. I'll then give two applications of this learning theorem to quantum computing: first, the use of trusted classical advice to verify untrusted quantum advice, and second, a new simulation of quantum one-way protocols. :: Mon 5/8/06, 2pm in NE25, 4th floor seminar room (CTP) (ctp) Alexei Kitaev (Caltech) Quantum computers may provide efficient solution to some computational problems that otherwise appear intractable, such as factoring of large integers. Unfortunately, the physical realization of this possibilityhas proved extremely difficult. Any reasonable implementation of a quantum computer must store qubits (i.e., quantum bits) in an encoded form so that to protect them from decoherence and other ``errors''; a computer built of bare qubits will not scale. On the other hand, logical qubits may be encoded directly into a system of many spins or electrons. In particular, three is a class of two-dimensional systems that carry anyons - quasiparticles with unusual statistics. Some more exotic variety on anyons are called ``non-Abelian''. With two non-Abelian anyons trapped in potential wells far apart from each other, one obtains a system with several quantum states. There is virtually no way to change one state to another or to tell them apart until the anyons are brought together and fuse. Thus the states are protected from decoherence. I will discuss general properties of anyons as well as their potential use in quantum computation. :: Mon 4/24/06, 4pm in 26-214 (QIP seminar) Cristopher Moore (Santa Fe Institute) Like factoring, Graph Isomorphism is not known to be in P, but it is probably not NP-complete either. This makes it an attractive target for quantum computing. Shor's algorithm solves the factoring problem by reducing it to the Hidden Subgroup Problem (HSP) in cyclic groups, and much of the community's hopes for Graph Isomorphism have hinged on an analogous approach: namely, we could solve Graph Isomorphism if we could solve the HSP in the symmetric groups Sn. :: Thu 4/13/06, 2pm in 36-462 (dne) Christophe Couteau (Waterloo) Since the Knill, Laflamme and Milburn proposal in 2001 to build a computer that would work with linear optics only, a search for a good source of indistinguishable photons has increased. Semiconductor quantum dots are thought to be potentially well-adapted for this type of activity and experimental research in this area is constantly growing. We will first introduce the physics of quantum dots, their main properties and what it is makes them attractive. Then we will define what a source of single photons is and how to characterise it. We will show typical experiments in quantum optics that one can do with such systems. We will show in particular the effect of photon antibunching which was historically the first proof of the existence of photons. :: Mon 4/3/06, 4pm in 26-214 (QIP seminar) Israel Klich (Caltech) Entanglement entropy emerged as a joint interest in several areas in physics such as condansed matter, field theory and quantum information in the last years. One of the most interesting properties is the scaling behavior of the entanglement entropy, especialy close to phase transitions. It was believed that at dimensions higher then 1 the entropy scales like surface area of the subsystem. However, I will describe a result for free fermions, where the entropy in fact scales faster. This will be related to a conjectured formula by H. Widom. I will also discuss ways to measure Entagnlement Entropy in various systems. :: Sat 3/25/06, 9am-5pm in 9th floor colloquium room, BU Photonics Center, 8 St. Mary's st. Boston Colloquium for Philosophy of Science (saturday session) MORNING SESSION: 9 A.M. - 12 P.M. :: Fri 3/24/06, 9am-5pm in 9th floor colloquium room, BU Photonics Center, 8 St. Mary's st. Boston Colloquium for Philosophy of Science (friday session) MORNING SESSION: 9 A.M. - 12:30 P.M. :: Fri 3/17/06, 12pm in 34-401A (Applied Probability Seminar) Marc Mezard (CNRS & Ecole Polytechnique) A new field of research is rapidly expanding at the crossroad between statistical physics, information theory and combinatorial optimization. It studies large networks of discrete variables, interacting through many local constraints. Examples range from error correcting codes using parity checks to graph coloring or satisfiability. All these problems become particularly hard when the density of constraints reaches a threshold where a spin glass phase appears. Spin glasses have been studied in statistical physics for more than 30 years. This talk will present some of their basic properties, and the reason for their ubiquity. Taking as a guide the satisfiability of random Boolean formulas, it will show how the concepts and methods developed in spin glass theory provide new analytical results on the phase transition and offer a powerful algorithmic framework. :: Thu 3/9/06, 3pm in Jefferson 250 @ Harvard (Loeb Lecture) John Preskill (Caltech) TBA :: Thu 3/9/06, 3pm in 34-401A (EECS) Andrew Childs (Caltech) Quantum mechanical computers can solve certain problems significantly faster than classical computers can, but the extent of this advantage is not well understood. The central problem of quantum computation is to better ascertain what kinds of problems are amenable to quantum speedup, and in particular, to develop algorithmic tools for designing fast quantum computations. In this talk, I will describe an approach to quantum algorithms based on implementing optimal measurements for distinguishing quantum states. This approach has led to new quantum algorithms with exponential speedup for certain instances of the hidden subgroup problem and other related problems. :: Tue 3/7/06, 3pm in Jefferson 250 @ Harvard (Loeb Lecture) John Preskill (Caltech) TBA :: Mon 3/6/06, 4.15pm in Jefferson 250 @ Harvard (Loeb Colloquium) John Preskill (Caltech) TBA :: Thu 3/2/06, 12:00am in 12-132 (Chez Pierre (CMT) Seminar) Frank Verstraete (Caltech) The concept of entanglement plays a central role in the field of strongly correlated quantum systems: it gives rise to fascinating phenomena such as quantum phase transitions and topological quantum order, but also represents a main obstacle to our ability to simulate such systems. We will discuss some new developments in which ideas, originating from the field of quantum information theory, led to valuable insights into the structure of entanglement in quantum spin systems and to novel powerful simulation methods. :: Wed 3/1/06, 4:30pm in Jefferson 356 (Harvard) (Harvard atomic physics) Gerard Milburn (U. of Queensland) TBA :: Mon 2/6/06, 4.15pm in Jefferson 250 @ Harvard (Harvard Colloquium) Chetan Nayak (Microsoft) TBA :: Mon 12/12/05, 4.00pm in 26-214 (QIP seminar) Debbie Leung (Waterloo) We first present a simple proof of universality in the graph state model based on the notion of composable simulation. Then, we give a simple proof for the existence of an accuracy threshold for graph-state computation invoking the threshold theorem derived for quantum circuit computation, and obtain lower bounds on the threshold for the graph-state model in terms of known bounds in the circuit model under the same noise process. (Joint work with A. Aliferis) :: Mon 12/5/05, 4.00pm in 26-214 (QIP seminar) Chris King (Northeastern) The multiplicativity question asks whether the maximal output p-norm of a product of linear maps on matrix algebras is achieved on a product state. For applications in quantum information theory the important class is the set of completely positive (CP) maps. Recent work has shown that the multiplicativity property can hold in some cases for other classes of maps. I will give examples of non-CP maps for which multiplicativity holds, and then explain some implications for the special case where one of the maps is a qubit channel. :: Mon 11/28/05, 4.00pm in 26-214 (QIP seminar) Sean Hallgren (NEC Labs) It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore, Russell, and Schulman that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. We show that entangled quantum measurements on at least Omega(n log n) coset states are necessary to get useful formation for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because highly entangled measurements seem hard to implement in general. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL(n,FFp^m) and Gn where G is finite and satisfies a suitable property. :: Mon 11/21/05, 4.00pm in 26-214 (QIP seminar) Chris Langer (NIST) In recent years, multiple groups have experimentally demonstrated all of the DiVincenzo criteria in ion-trap systems. Now, efforts are underway to build a large scale quantum information processor. For this goal to be realized, error rates must be suppressed to very low levels, and more complicated traps must be built. I will discuss our progress at NIST in these areas. In particular, our memory error during the detection interval is on the order of 10-5, and spontaneous emission errors during a 2-qubit gate interval are in the neighborhood of 5 x 10-4. Our experiments indicate that with sufficient laser power, errors due to spontaneous emission can be suppressed even further. I will also discuss our recent quantum computing experiments at NIST. :: Mon 11/14/05, 4.00pm in 26-214 (QIP seminar) Jacob Taylor (Harvard) Solid state approaches to quantum computation offer intriguing prospects for large scale integration and long term stability. However, achieving fault tolerant quantum computation entails significant mitigation of environmental couplings, which is particularly challenging in the solid-state. We will discuss the theoretical and experimental development of a scalable architecture for solid-state quantum computation based on actively protected two electron spin states in quantum dots. Specifically, we find a universal set of gates for two-spin states that can be implemented using only local electrical control, with explicit suppression of hyperfine interactions, the dominant source of error. The architecture allows for a modular, hierarchical design, and includes autonomous control and non-local coupling using controlled electron transport. Fault tolerance properties of the architecture will be considered. :: Mon 11/7/05, 4.00pm in 26-214 (QIP seminar) Lu-Ming Duan (Univ. of Michigan) In the first part of my talk, I will show to do efficient quantum computation with probabilistic entangling gates. For this special noise model, basically one can achieve fault tolerant computation with 100% error threshold. For the second part, I will show how to simulate a class of many-body physics with resonantly interacting fermions in an optical lattice. I derive an effective Hamiltonian for fermions in an optical lattice across Feshbach resonance, and the model describes a lattice resonance between local dressed molecules and valence bonds of atoms on neighboring sites. It reduces to the fundamental t-J model form atoms or the XXZ model for dressed molecules on different sides of such a resonance. :: Mon 10/31/05, 4.00pm in 26-214 (QIP seminar) Daniel Gottesman (Perimeter Institute) One of the central critical results in the theory of fault-tolerant quantum computation is that arbitrarily long reliable computation is possible provided the error rate per gate and per time step is below some threshold value. This was proved by a number of groups, but the detailed published proofs are complex and furthermore only hold for concatenation of quantum error-correcting codes able to correct 2 errors per block, while typically the best estimates of the threshold value are based on the 7-qubit code, which only corrects 1 error per block. I will describe recent work by Panos Aliferis, John Preskill, and myself which substantially simplifies existing proofs and applies as well to the concatenated 7-qubit code. The new proof also provides a nice framework in which to attempt to prove relatively high values of the threshold, which so far have only emerged as estimates from simulations of fault-tolerant circuits. :: Mon 10/24/05, 4.00pm in 26-214 (QIP seminar) Hans Mooij (Delft University of Technology) Flux qubits are superconducting two-level systems where the states are characterized by opposite circulating currents in a superconducting loop with three Josephson junctions, to which a magnetic flux of half a flux quantum is applied. Excitation is performed by means of microwave pulses. They are studied in several groups, the talk will focus on recent progress in Delft. Much of the effort is directed towards improving coherence and fidelity of readout. Relaxation times are typically around 5 microseconds, while dephasing times vary strongly with conditions. The best achieved result is a spin-echo-corrected dephasing time of 4 microseconds. The usual readout so far was by measuring the critical current of a SQUID. A new dispersive method has been developed where the SQUID inductance is measured. This non- destructive technique now yields a fidelity of 87%. Further improvement seems possible. We have studied the coupling of a flux qubit to a harmonic oscillator, where we see cohrent transitions on the blue and red sidebands. We have also studied two coupled flux qubits and performed conditional spectroscopy. Further optimalization is needed (and possible) to realize two-qubit gates. A new form of flux qubit based on phase-slip in superconducting wires will be discussed. This type may have advantages with respect to the 1/f noise that dominates in junctions qubits. :: Mon 10/17/05, 4.00pm in 26-214 (QIP seminar) Charles Marcus (Harvard University) This talk will describe recent experiments aimed at using the spin of electrons as a holder of a bit of information, for possible use in quantum computing schemes. The progress toward a viable application is modest, but the physics issues raised by these initial steps are very interesting. Along the way, surprises thatare of considerable fundamental interest have arisen that may have little to do with quantum information processing but are nonetheless worthwhile problems in solid state physics. Related references can be found the Sept. 30th 2005 issue of Science. :: Wed 10/12/05, 11.00am in 36-428 (EECS/RLE Seminar) Aephraim Steinberg (Univ. of Toronto) :: Thu 10/6/05, 7.00pm in 34-401A (recruitment presentation) Chip Elliott (BBN Technologies) Recruiting Info Session: Come hear from former MIT students, Dr. Gary Butler, Dr. Henry Houh and Dr. Kristin Rauschenbach. The DARPA Quantum Network, funded by the Defense Advanced Research Projects Agency (DARPA), provides extremely high levels of information security guaranteed by the laws of quantum physics. It has been fully operational since June 2004 and is the worlds first quantum cryptography network, linking the campuses of BBN Technologies, Harvard University, and Boston University. The network currently includes 10 interlinked nodes, with eight (including two free space link nodes) at BBNs offices in Cambridge, one at Harvard University, and another at Boston University. Most of the nodes were designed and built entirely by BBN Technologies. :: Mon 10/3/05, 4.00pm in 26-214 (QIP seminar) Patrick Hayden (McGill University) Over the past few years, most of the basic problems of single-sender, single-receiver quantum information theory have been solved. In particular, many varieties of capacity of a quantum channel are now not only understood, but understood to be intimately related to each other. In contrast, multiuser quantum information theory experienced a few false starts over the same period before entering its current phase of rapid advance, ushered in not only by improvements in technique, but by some judicious choices of problem formulation as well. In this seminar, I'll survey recent work with my collaborators on distributed data compression, single-sender/multiple-receiver (broadcast) quantum channels and multiple-sender/single-receiver (multiple access) quantum channels, emphasizing the many connections between the various problems, some of the pitfalls we've experienced along the way, and the many open problems remaining. :: Tue 9/27/05, 4.00pm in 32-141 (LIDS colloquium) Navin Khaneja (Harvard) In this talk I will discuss some control problems that arise in manipulation of coupled spin dynamics in NMR spectroscopy using radio frequency pulses. In control and manipulation of quantum systems, the system of interest is rarely isolated but interacts with its environment. This leads to phenomenon of relaxation which in practice results in signal loss and limits the range of applications. Finding optimal ways to manipulate dynamics of coupled nuclear spins to minimize relaxation losses is an important problem. I will present our work on optimal pulse sequence design for minimizing relaxation losses and improving the sensitivity of NMR experiments. Applications of these optimal control methods to NMR spectroscopy of very large proteins in solution will be discussed. These experiments involve steering an ensemble of quantum systems, which show dispersion in the parameters that govern their dynamics. This gives rise to interesting control problems of steering a continuum of dynamical systems with different dynamics using the same control that can compensate for the various dispersions. I will discuss our recent work on controllability of quantum ensembles. :: Mon 9/26/05, 4.00pm in 26-214 (QIP seminar) Chris Moseley (USMA, West Point) Khaneja, Brockett and Glaser have designed time-optimal controls for two- and three-spin NMR systems by finding sub-Riemannian geodesics on quotient spaces of SU(4) (Phys. Rev. A. 63: 032308, Phys. Rev. A. 65: 032301). In this talk, I will describe how to characterize sub-Riemannian geodesics for $SU(2^n)$ using the Griffiths formalism for the calculus of variations, using the two-spin case as an example, and describe work in progress on the four-spin case. :: Mon 9/26/05, 2.00pm in NE 25 4th floor seminar room (Nuclear/Particle Theory Seminar) Roberto Floreanini (Univ. of Trieste) :: Mon 9/26/05, 3.00pm in Jefferson Laboratory, Rm. 250, Harvard (Harvard Spec.Seminar) Michael Freedman (KITP & Microsoft) 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 compuation. Finally, I'll come to my (current) favorite system, FQHE at v=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, too numerous to mention!) :: Tue 9/20/05, 2.00pm in 509 Lake Hall (Northeastern University) (Northeastern) Koenraad Audenaert (Imperial College London) I consider inequalities for the Schatten q-norms, which are non-commutative generalistions of the l_q norms. Given a block partitioned matrix, one can try and bound the q-norm of the matrix itself in terms of the q-norms of the blocks. The inequalities that arise can be called norm compression inequalities, because the bound is stated in terms of the elements of the norm compression of the matrix, which is what you get when replacing every block of the matrix by its norm. In this talk I give an overview of previously known bounds of this kind. I then present some norm compression bounds for positive semidefinite 2X2 block matrices, complementing earlier work by Chris King. Finally, I give an overview of various conjectured norm compression inequalities, and discuss some of the implications their validity would have in quantum information theory. See also math.FA/0505680 :: Mon 9/12/05, 4.00pm in 26-214 (QIP seminar) David DiVincenzo (IBM) After almost four years of trying, we've finally got our good numbers: 90% visibility, 50nsec coherence time. We anticipate considerable improvements in the latter pretty soon. I will tell the theory part of this story. There are three unique things about our qubit: 1) it is gradiometric, making multiple controls very clean; 2) operations are mostly adiabatic, except that there is a crucial, small region of parameter space, which we call the "portal", where non-adiabatic things happen; 3) The qubit can be converted adiabatically to the 0/1 states of a harmonic oscillator. It is this embodiment of the quantum state that is very coherent. :: Mon 4/25/05, 4.00pm in 4-237 (QIP seminar) David Meyer (University of California at San Diego and Institute for Physical Sciences, Washington DC) Several different definitions of quantum games have been proposed over the past five years. Some of the results claimed for the differences between these quantum games and classical games identified as those to which they correspond have been criticized, however, as not being fair comparisons. In this talk I'll define classical and quantum versions of games with mediated communication, and argue that these are the classical and quantum games that should be compared. :: Mon 4/11/05, 4.00pm in 4-237 (QIP seminar) John Clarke (Berkeley) We have studied quantum coherence in a three-junction, superconducting flux qubit using a dc SQUID to measure its flux state. The qubit and SQUID are equipped with separate, on-chip flux bias lines, so that we can set the flux bias of each device independently. The chip is enclosed in a superconducting cavity, enabling us to obtain data over several days in a stable magnetic environment. Detailed spectroscopic measurements reveal the expected avoided crossing at the degeneracy point, and resonances that are ascribed to tunnel barrier defects; even at millikelvin temperatures these resonances shift with time. The Rabi oscillation frequency scales linearly with microwave amplitude. The linewidth of microwave-induced resonances yields the inhomogeneously broadened dephasing rate 1/T2', and echoes yield the dephasing rate 1/T2; these times are consistent with the value of 1/T2* determined from Ramsey fringes. A scheme is presented for controlling the coupling between two flux qubits by varying the dynamic inductance of the readout SQUID surrounding them. The mutual inductance between the qubits can be switched from zero to a predetermined value simply by changing the bias current in the SQUID in the zero-voltage state. :: Mon 4/4/05, 4.00pm in 4-237 (QIP seminar) William Olliver (MIT Lincoln Laboratories) MIT Lincoln Laboratory has a superconductor-based quantum computing (QC) program comprising experimental, theoretical, and fabrication efforts aimed at demonstrating and improving single-qubit figures of merit (e.g., Rabi fringe contrast, decoherence times), with a longer-term vision towards coupled qubits and, ultimately, demonstrations of the subsystem integration required for scalable quantum computing. We begin this talk with a presentation of our QC efforts during the past 12 months with our collaborators at the MIT campus; the focus will be qubit measurement and fabrication. MIT Lincoln Laboratory designed, implemented, and automated a time-resolved persistent-current-qubit readout in the MIT dilution refrigerator capable of nanosecond-scale resolution measurements. We used this readout to map the qubit energy-band diagram, match it to simulation, and demonstrate multi-photon transitions. We also have preliminary, albeit weak, Rabi oscillation data; we understand and will discuss what limits the oscillations for this particular qubit design. In addition, we have fabricated and prototyped a resonant-circuit-based qubit readout with the explicit aim of reducing qubit decoherence. In parallel, we have reassessed and refocused our qubit fabrication at MIT Lincoln Laboratory. We will present the results of this reassessment: a new deep-submicron qubit fabrication process (DSM-1). DSM-1 is a fully-planarized Nb-trilayer process which provides high-yield and reproducible structures, including Josephson junctions, capacitors, inductors, and resistors. It was specifically designed to realize the more sophisticated ancillary circuits required for improved qubit readout and decoherence times which are difficult to realize using the conventional shadow-evaporation approach. Using the DSM-1 process, we have demonstrated Josephson junctions smaller than 100 nm and critical current densities ranging from 30 A/cm2 to 10 KA/cm2. We have also fabricated and begun testing at 15 mK qubits using the DSM-1 process. We will discuss why these new DSM qubits should exhibit improved decoherence times. :: Mon 3/28/05, 4.00pm in 4-237 (QIP seminar) Herschel Rabitz (Princeton) Since the development of the laser some 40 years ago, a long-standing dream has been to utilize this special source of radiation to manipulate dynamical events at the atomic and molecular scales. Hints that this goal may become a reality began to emerge in the 1990's, due to a confluence of concepts and technologies involving (a) control theory, (b) ultrafast laser sources, (c) laser pulse shaping techniques, and (d) fast pattern recognition algorithms. These concepts and tools have resulted in a high speed instrument configuration capable of adaptively changing the driving laser pulse shapes, approaching the performance of thousands of independent experiments in a matter of minutes. Each particular shaped laser pulse acts as a "Photonic Reagent" much as an ordinary reagent would at the molecular scale. Although a Photonic Reagent has a fleeting existence, it can leave a permanent impact. Current demonstrations have ranged from manipulating simple systems (atoms) out to the highly complex (biomolecules), and applications to quantum information sciences are being pursued. In all cases, the fundamental concept is one of adaptively manipulating quantum systems. The principles involved will be discussed, along with the presentation of the state of the field. :: Mon 3/14/05, 4.15pm in 4-231 (Applied Mathematics Colloquium) Charles Bennett (IBM, Yorktown Heights) Any process whereby a quantum system passes from a sender to a receiver, possibly interacting with some environment en route, may be regarded as a quantum channel. Unlike their classical analogs, quantum channels have multiple capacities depending on what one is trying to use them for (e.g. classical or quantum communication) and what auxiliary resources are brought into play. I review these capacities and the progress in associating them with simple entropic expressions such as Holevo information and quantum mutual information. Among auxiliary resources, sender-receiver entanglement has a simplifying effect: in its presence all quantum channels become efficiently interconvertible (quantum reverse Shannon theorem). By contrast, classical feedback, or source-independent bidirectional classical side communication, which have no effect on a classical channel's single capacity, have a complicated effect on quantum channels, sometimes increasing both their quantum and capacities to values between the unassisted and the entanglement-assisted values. Joint work with Peter Shor, Igor Devetak, John Smolin and Andreas Winter. :: Mon 3/7/05, 4.00pm in 4-237 (QIP seminar) Seth Lloyd (MIT Dept. of Mechanical Engineering) :: Mon 2/14/05, 4.00pm in 4-237 (QIP seminar) Carlton M. Caves (University of New Mexico) Requiring that a quantum computer not need an exponentially growing amount of any physical resource places stringent constraints on the systems that can act as quantum computers. In particular, a quantum computer must be made up of subsystems, usually qubits, thus ruling out implementing a quantum computer in a single atom or by using the interference of classical waves. Furthermore, if a quantum computer made up of subsystems performs some computation exponentially faster than any classical computer, there must be global entanglement among all the subsystems at some point during the computation. Having thus led up to the conclusion that quantum entanglement is the essential ingredient for quantum computation, I will discuss why this conclusion isn't ironclad. :: Wed 2/9/05, 12.00pm in 12-132 (Chez Pierre Seminar) Boris Blinov (University of Michigan) Trapped atomic ions are widely regarded as one of the most promising candidates for a large-scale quantum computing. Individual ion qubits are localized in ultrahigh vacuum by radio-frequency electromagnetic fields; their logic states are manipulated using optical and microwave radiation. Entanglement necessary to carry out quantum computation is formed through ions' mutual Coulomb interaction. Minor problem: the ions are tightly trapped, localized in space, and cannot transmit quantum information over any meaningful distance. Coupling of trapped ion qubits to "flying qubits" (optical photons), accomplished by either spontaneous decay into free space or by stimulated emission into a high-finesse optical cavity, enables such quantum information transmission. At Michigan, we experiment with Cd+ ion qubits in a variety of ion trap geometries. We also investigate entanglement formation and properties in trapped ion single photon system. I will describe our recent experiments and ideas for future developments; I will also present my take on the bigger picture, and the place that trapped ions occupy in it. :: Mon 2/7/05, 12.00pm in 12-132 (Chez Pierre Seminar) Murray Barrett (University of Otago, NZ) Dramatic progress in micro- and nano-fabrication of hardware for information processing has made encoding information within a single atom a practical possibility. In this limit the quantum nature of the information carriers cannot be neglected, and it has been shown that quantum effects can provide significant improvements in efficiency for a small number of important computational problems. The importance of these problems has stimulated intensive efforts aimed at the development of large scale quantum information processing (QIP) and the ion-trap scheme is a promising candidate system. I will discuss details of the ion trap system and illustrate its potential for large scale quantum computing using a number of experiments carried out during my time as a Post-doc at the National Institute of Standards and Technology, Boulder, CO. :: Thu 12/9/04, 12.00pm in Lyman 425 (Harvard) (Condensed Matter Theory Seminar) Alexei Kitaev (Caltech) :: Tue 12/7/04, 4.00pm in 26-214 (Center for Ultracold Atoms Seminar) Steven Girvin (Yale) :: Mon 12/6/04, 4.00pm in 4-237 (QIP seminar) Robert Schoelkopf (Yale) I will describe recent experiments in which the strong coupling limit of cavity quantum electrodynamics has been realized for the first time using superconducting circuits. In our approach, we use a Cooper-pair box as an artificial atom, which is coupled to a one-dimensional cavity formed by a transmission line resonator. When the Cooper-pair box qubit is detuned from the cavity resonance frequency, we perform high-fidelity dispersive quantum non-demolition read-out of the qubit state. Using this read-out technique, we have characterized the qubit properties spectroscopically, performed Rabi oscillations of the qubit, and attained coherence times greater than 200 ns, indicating that this architecture is extremely attractive for quantum computing and control. In the case when the qubit is tuned into resonance with the cavity, we observe the vacuum Rabi splitting of the cavity mode, indicating that the strong coupling regime is attained, and coherent superpositions between the qubit and a single photon are generated. :: Tue 11/30/04, 2.30pm in 2-338 (Physical Mathematics Seminar) Russell Caflisch (UCLA) This talk will describe the simulation, design and optimization of a qubit for use in quantum communication or quantum computation. The qubit is realized as the spin of a single trapped electron in a semi-conductor quantum dot. The quantum dot and a quantum wire are formed by the combination of quantum wells and gates. The design goal for this system is a "double pinchoff", in which there is a single trapped electron in the dot and a single (or small number of) conduction states in the wire. Because of considerable experimental uncertainty in the system parameters, the optimal design should be "robust", in the sense that it is far away from unsuccessful designs. We use a Poisson-Schrodinger model for the electrostatic potential and electron wave function and a semi-analytic solution of this model. Through a Monte Carlo search, aided by an analysis of singular points on the design boundary, we find successful designs and optimize them to achieve maximal robustness. :: Mon 11/29/04, 4.00pm in 4-237 (QIP seminar) Reiner Blatt (University of Innsbruck, Austria) :: Fri 11/19/04, 2.00pm in 4-153 (QIP seminar) Tony Leggett (University of Illinois, Urbana-Champaign) I present the motivation for experiments which attampt to generate,and verify the existence of,quantum superpositions of two or more states which are by some reasonable criterion \'\'macroscopically\'\' distinct,and show that various a priori objections to this program made in the literature are flawed.I review the extent to which such experiments currently exist in the areas of free-space molecular diffraction,magnetic biomolecules, quantum optics and Josephson devices,and sketch possible future lines of development of the program. :: Mon 11/8/04, 4.00pm in 4-237 (QIP seminar) Mikhail Lukin (Harvard) Quantum communication holds promise for transmitting secure messages via quantum cryptography, and for communicating quantum information. However, extending quantum communication techniques to long distances represents a conceptual and technological challenge: on the one hand photon losses fundamentally limit the range of direct communication, on the other hand quantum signals cannot be amplified without adding noise. The so-called quantum repeater techniques provide a potential solution to this problem. Implementation of these techniques requires coherent light-matter interface including quantum memory nodes for photon state storage and the means for generation and purifying quantum entangled states. This talk will describe our progress toward developing the new tools and techniques required for constructing quantum repeaters. Two specific approaches based on atomic and solid state systems will be described. :: Mon 11/1/04, 4.00pm in 4-237 (QIP seminar) Andrew Landahl (MIT) Quantum circuits are built out of quantum wires and quantum gates. For applications in which quantum bits are spins packed at high density, like the hard drive of a quantum computer, it is worthwhile to examine how well spin-spin interactions can implement these wires and gates directly, without the need for external dynamical control. In this talk I present spin networks of Heisenberg and XY interactions that act as perfect quantum wires---quantum states transfer across them with unit fidelity. I show that perfect communication length scales logarithmically when all bonds have the same strength, and how to engineer bond strengths so that arbitrary length perfect quantum communication is possible. I conclude by showing how to extend perfect quantum wires to perfect quantum gates using some well-known ideas proven by Feynman in the late 1980s. :: Mon 10/25/04, 4.00pm in 4-237 (QIP seminar) Paolo Zanardi (ISI, Torino, Italy) We investigate bipartite entanglement in spin-1/2 systems on a generic lattice. For states that are an equal superposition of elements of a group G of spin flips acting on the fully polarized state $ket{0}^{otimes n}$, we find that the von Neumann entropy depends only on the boundary between the two subsystems A and B. These states are stabilized by the group G. A physical realization of such states is given by the ground state manifold of the Kitaev's model on a Riemann surface of genus g. For a square lattice, we find that the entropy of entanglement is bounded from above and below by functions linear in the perimeter of the subsystem A and is equal to the perimeter (up to an additive constant) when A is convex. The entropy of entanglement is shown to be related to the topological order of this model. Finally, we find that some of the ground states are absolutely entangled, i.e., no partition has zero entanglement. We also provide several examples for the square lattice. :: Mon 10/18/04, 4.00pm in 4-237 (QIP seminar) Peter Love (Tufts) Quantum lattice gases are known to reproduce the Dirac equation in one dimension and the Schroedinger equation in D dimensions. They also represent quantum algorithms for the simulation of quantum systems with an exponential performance advantage over their implementation on classical computers. These models are therefore of interest both as classical algorithms for modelling quantum systems and as algorithms which may be efficiently implemented on future quantum computers. In both cases, the role of decoherence arising from the interaction of the model with an environment is of interest. If we consider these models in the context of simulation of quantum systems, the introduction of an environment is of interest from the point of view of correspondence. If we consider these models as quantum algorithms the introduction of an environment enables us to study the effect of a finite error rate in our quantum computer. In this talk, we discuss one method of coupling quantum lattice gases to an environment and present simulation and analytic results for this error model. :: Thu 10/14/04, 4.00pm in 3-270 (QIP seminar) Rodney van Meter (Keio University) Shor's algorithm for factoring large numbers runs in polynomial time on a quantum computer. The most expensive portion of Shor's algorithm is the modular exponentiation performed before the more well-known quantum Fourier transform. The exact details of the polynomial, its degree and constant factors, determine the running time and consequently the practicality of the algorithm on a particular quantum computer. In this talk, we will show our circuits for performing the modular exponentiation. We show that the running time depends on the combination of algorithm and architecture, as well as clock speed. Following the main talk will be a brief demonstration and discussion of the quantum circuit compilation, optimization, and visualization tools I am currently developing, for those who are interested. :: Wed 10/6/04, 4.00pm in 32-G449 (Kiva) (Theory of Computation Seminar) Iordanis Kerenidis (MIT) Quantum computation and information has become a central research area in theoretical computer science. It studies how information is encoded in nature according to the laws of quantum mechanics and what this means for its computational power. The ability of a quantum system to be in a superposition of states enables us to store an exponential amount of information in a quantum system. However, this information is accessible only indirectly via measurements. Our goal is precisely to investigate the fundamental question of how information is encoded and processed in quantum mechanical systems. We investigate their power relative to classical encodings in the model of one-way communication complexity and show that they can be exponentially more efficient, answering a long-standing open question in the area of quantum communication complexity. Furthermore, we show how the theory developed for the study of quantum information can be employed in order to answer questions about classical coding theory and complexity by proving an exponential lower bound for 2-query Locally Decodable Codes. This is the first example where quantum techniques are essential in resolving a purely classical question. No previous knowledge of quantum computing is assumed. :: Mon 10/4/04, 4.00pm in 4-237 (QIP seminar) Jeff Shapiro (MIT Research Laboratory for Electronics) The capacity C for transmitting classical information is investigated for Bosonic channels with isotropic Gaussian noise. For the pure-loss channel -- in which signal photons may be lost in propagation -- the exact value of C is derived. The Holevo information of this channel is shown to be additive, and a \'\'classical\'\' encoding procedure employing coherent states is shown to achieve capacity. For active channel models -- in which noise photons are injected from an external environment or the signal is amplified with unavoidable quantum noise -- upper and lower bounds are obtained for the capacity. These bounds are asymptotically tight at low and high noise levels. Exact capacity results -- given by the lower bounds -- would follow from proving the conjecture that a coherent-state input minimizes the output entropy from such channels. :: Mon 9/27/04, 4.00pm in 4-237 (QIP seminar) Seth Lloyd (MIT Mechanical Engineering) This talk derives fundamental physical limits to the accuracy with which systems like the global positioning system (GPS) can map out the geometry of space and time. The so-called standard quantum limit may be standard and may be quantum, but it is not a limit: it can be surpassed using quantum effects such as entanglement and squeezing. Results from the physics of computation can be used to derive a new bound, the quantum geometric limit, for the accuracy to which distance and time can be measured. :: Mon 9/20/04, 4.15pm in 2-105 (Applied Mathematics Colloquium) Stephanie Singer Mathematicians love theorems; experimental scientists love predictions. Can theorems ever make testable predictions? The answer is yes. In this talk, we discuss one powerful kind of predictive theorem (classification of representations). For example, from the basic principles of quantum mechanics and the inherent spherical symmetry of the hydrogen atom it is possible to predict much of the electronic structure of the hydrogen atom. This is not an isolated example; rather, it is a simple case of a wide-ranging method. :: Tue 9/14/04, 4.00pm in 32-123 (EECS/LIDS Seminar) David MacKay (Cambridge) Quantum error-correcting codes based on sparse graphs are of interest for three reasons. First, the best codes currently known for classical channels are based on sparse graphs. Second, sparse-graph codes keep the number of quantum interactions associated with the quantum error correction process small: a constant number per quantum bit, independent of the block length. Third, sparse-graph codes often offer great flexibility with respect to block length and rate. We believe some of the codes we present are unsurpassed by previously published quantum error-correcting codes. Note: This lecture will assume no knowledge of quantum physics; a paper is available at http://arxiv.org:/abs/quant-ph/0304161 as well as http://www.inference.phy.cam.ac.uk/mackay/QECC.html :: Thu 9/9/04, 4.15pm in 10-250 (Physics Colloquium) Edward Farhi (MIT) The advantage of quantum computation over classical computation is that for certain problems a quantum computer may use fewer steps to solve the problem than the minimum number of steps required by any classical computer. In this talk I will try to show how ideas from physics can lead to this kind of algorithmic speedup. The existence of a large, perfectly functioning quantum computer will be assumed. :: Mon 5/17/04, 4.00pm in 4-237 (QIP seminar) Wim van Dam (MIT) 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 favour of the proposal. :: Mon 5/10/04, 4.00pm in 4-237 (QIP seminar) Chandrasekhar Ramanathan (MIT) Though solid-state NMR holds promise for scalable implementations of quantum information processing, significant obstacles remain in achieving accurate and universal control. I will discuss some of our recent efforts to study and control the dynamics of large numbers of nuclear spins in solids, and the implications for QIP and quantum simulation. :: Mon 5/3/04, 4.00pm in 4-237 (QIP seminar) Marcus Kindermann (MIT) It has been shown that non-interacting Fermions measured in the computational basis cannot be used to implement Quantum Algorithms with their inherent exponential speed-up. In this talk I will first describe an experimentally feasible scheme that allows to generate entangled quantum states of electrons without requiring two-particle interactions. The scheme can be extended to teleport quantum information. This suggests, that also universal Quantum Computation may be possible with non-interacting electrons. I will show, that this is indeed the case if one allows for a generalized measurement. :: Mon 4/26/04, 4.00pm in 4-237 (QIP seminar) Dieter Suter (Dortmund) Liquid-state NMR was the first technique that successfully demonstrated the potential of quantum information processing, and it still represents the most powerful implementation of a quantum computer. However, no viable solutions have been found for increasing the number of qubits in these systems into a range where the resulting processors are more powerful than conventional electronic computers. For this purpose, solid-state systems may have some advantages. Using a solid-state NMR system, we study the scaling of decoherence rates with the system size and discuss the basics of a (potentially) scalable system architecture. :: Tue 4/20/04, 4.00pm in 4-237 (QIP seminar) Lorenza Viola (Los Alamos National Laboratory) Characterizing and quantifying quantum correlations in complex systems is critical for quantum information science as well as for a variety of physical phenomena, including phase transitions in matter. In this talk, I will discuss a generalization of entanglement based on the idea that entanglement is relative to a distinguished subspace of physical observables rather than a distinguished subsystem decomposition. For multi-qubit systems, conventional entanglement is recovered in the special case where the set of all local observables on individual subsystems is preferred. By going beyond the standard distinguishable-subsystem framework, however, generalized entanglement naturally lends itself to applications in the condensed-matter setting. In particular, by focusing on the illustrative case of a one-dimensional spin-1/2 XY model in a transverse field, I will show how generalized entanglement provides useful diagnostic tools for identifying broken-symmetry quantum phase transitions. :: Mon 4/19/04, 1.30pm in Harvard, Jefferson Lab 250 (Loeb Lecture) Jeff Kimble (Caltech) :: Tue 4/6/04, 10.00am in 37-252 (Marlar Lounge) (Special Seminar) David Wineland (NIST, Boulder) At NIST, by using a few trapped atomic ions, we have been
able to implement the basic one- and two-qubit gate
operations required for quantum information processing [1].
The challenge is to scale up this system in order to perform
large-scale processing. One way this might be accomplished
is to use an array of ion trap zones, each of which contains
a small number of ions - to facilitate efficient gates. By
shuttling ions between zones, gates between selected ions in
the array could be achieved [2]. By separating ions
contained in one trap, moving them to separate trap zones,
and performing subsequent logic operations, we can now
implement the basic steps of this scheme. However, we now
face significant practical problems in how to actually
fabricate the required large trap structures, how to wire up
the trap electrodes and control their potentials, and how to
produce and manipulate the many laser beams that will be
needed in such a device. These and other issues will be
discussed. :: Mon 4/5/04, 4.00pm in 4-237 (QIP seminar) Ignacio Cirac (Max Planck Institute, Garching) Much of the current effort in Quantum Information Theory is devoted to the description and quantification of the entanglement contained in quantum states, since this intriguing property of Quantum Mechanics is the basic resource of most of the applications in this field, including quantum communication and computation. In this talk I will introduce a new notion of entanglement which captures the idea of how this property can be localized in small subsystems by performing measurement in the rest of the system. I will also show how this notion allows to detect hidden orders in spin systems at zero temperature, and how it behaves in quantum phase transitions. Finally, I will show how these ideas may help to develop simulation schemes for spin chains and lattices. :: Tue 3/30/04, 4.15pm in 32-D507 (Theory of Computation Seminar) Sean Hallgren (NEC Research) Computing the unit group of a number field is one of the main tasks in computational algebraic number theory. Factoring integers reduces to a special case of computing the unit group, but a reduction in the other direction is not known and appears more difficult. We give a polynomial-time quantum algorithm for computing the unit group when the number field has constant degree. :: Mon 3/29/04, 4.00pm in 4-237 (QIP seminar) Franco Wong (MIT) Photonics is a key quantum information technology area for applications ranging from quantum communication to quantum computation. I will describe some of the photonic resources we are assembling at MIT: high-flux sources of entangled photons, quantum-state frequency translation, and single-photon two-qubit quantum logic gates. :: Mon 3/15/04, 4.00pm in 4-237 (QIP seminar) Mike Mosca (Univ. Waterloo and Perimeter Institute) Suppose we have n algorithms, quantum or classical, each computing some
bit-value with bounded error probability. We describe a quantum algorithm
that uses O(n) repetitions of the base algorithms and with high
probability finds the index of a 1-bit among these n bits (if there is
such an index). This shows that it is not necessary to first
significantly reduce the error probability in the base algorithms to
O(1/poly(n)) (which would require $O(n/log n)$ repetitions in total).
Our technique is a recursive interleaving of amplitude amplification and
error-reduction, and may be of more general interest. Essentially, it
shows that quantum amplitude amplification can be made to work also with
a bounded-error verifier. :: Mon 3/15/04, 4.05pm in NE43-518 Dorit Aharonov (Berkeley) The fascinating field of quantum computation now faces major challenges which are intimately related to other areas in theoretical computer science: coding theory, Markov chains, lattices, and more. Starting with a (gentle) introduction to quantum computation, I will proceed to make these connections more explicit, while walking you through two of the most important issues in the field. The first is making quantum computers more resilient to noise, which is arguably the main bottleneck towards large scale realization of quantum computers; The second is breaking past our current barrier of designing new quantum algorithms. Our recent results in the latter area have led in a surprising way to a solution of an open question regarding the (totally classical) complexity of lattice problems. If time permits, I will tell you the story behind this unexpected connection. :: Thu 3/11/04, 4.05pm in NE43-518 Julia Kempe (UC Berkeley and University de Paris-Sud, France) Quantum Computing has entered the scene in areas as disparate as computer science, physics and engineering. Besides being a fascinating area of research in its own right it has also triggered a deeper understanding of the essence of information, computation and complexity. Theoretical algorithmic and cryptographic results have made the quest to build a quantum computer one of the biggest engineering challenges today. :: Mon 3/8/04, 4.00pm in 4-237 (QIP seminar) Andris Ambainis (Berkeley) I will present two new quantum algorithms based on quantum walks: - an O(N^{2/3}) query algorithm for element distinctness (the problem of finding two equal elements among N given elements). - an O(N^{1/2}log N) step quantum algorithm for finding a marked item on 2-dimensional grid. Both algorithms are based on the same general technique. I will also describe this technique and show how to decompose it into a sequence of steps which can then be applied to other problems. The second algorithm is a joint work with Julia Kempe and Alexander Rivosh. :: Wed 3/3/04, 2.45pm in 33-419 Pablo Parillo (ETH, Zurich) Sum of squares (SOS) programs are a particular class of convex
optimization problems, that combine in a very appealing way notions
from algebraic and numeric computation. They are based on the sum of
squares decomposition for multivariate polynomials, and have found many
interesting applications, mainly through semidefinite relaxations of
polynomial optimization problems. :: Tue 3/2/04, 4.00pm in 26-214 Hideo Mabuchi (Caltech) :: Mon 3/1/04, 4.00pm in E51-470 Hideo Mabuchi (Caltech) This talk will review our group\'s current work on real-time observation of quantum and bio-molecular systems, with an emphasis on analyzing and exploiting essential ties between experimental capabilities and optimal signal processing. Our work is motivated by applications ranging from the basic study of decoherence and quantum measurement theory to nano-biotechnology (lab-on-a-chip platforms). In the long run we aim towards the development of something like a nano-systems science, that will integrate existing control and systems theory with rigorous modeling of quantum and thermodynamic stochastic processes. This will necessitate new emphasis on proper treatment of statistical estimation problems and judicious use of uncertainty management through feedback. :: Mon 2/23/04, 4.00pm in 4-237 (QIP seminar) Louis Salvail (Univ. Aarhus) The concept of zero-knowledge (ZK) proof has become of
fundamental importance in cryptography. However, in a setting
where entities are modeled by quantum computers, classical
arguments for proving ZK fail to hold. Specifically, in the
quantum setting, the concept of rewinding is not generally
applicable, and protocols that are classically proven to be
ZK may be insecure. Moreover, known classical techniques that
avoid rewinding have various shortcomings in the quantum
setting. :: Mon 12/8/03, 4.00pm in 4-270 (QIP seminar) Peter Shor (MIT) Several of the unsolved questions in quantum information theory deal with the additivity of various entropy-related formulas and capacities. We will discuss these questions, and show that several of them are related. Namely, the additivity of the entanglement of formation, of the Holevo capacity, of the minimum entropy output, and the strong superadditivity of the entanglement of formation, are either all true or all false. :: Wed 12/3/03, 4.00pm in 13-2127 (Special Seminar) Johannes Majer (Yale) We have performed spectroscopy measurements on two coupled superconducting flux qubits. The qubits are coupled inductively, which results in a $sigma_z^1 sigma_z^2$ interaction. By applying microwave radiation, we observe resonances due to transitions from the ground state to the first two excited states. From the position of these resonances as a function of the magnetic field applied we observe the coupling of the qubits. The coupling strength agrees well with calculations of the mutual inductance. :: Mon 12/1/03, 4.00pm in 4-270 (QIP seminar) Karl Berggren (MIT) Superconductive systems are one of the few macroscopic
systems in which quantum mechanical behavior has been
observed. In a superconductor one can design, fabricate, and
test circuits described by using a wavefunction in which each
current and voltage state may be observed with some
probability amplitude. Interference of these amplitudes and
entanglement between physically separated circuits can be
observed in this system. These properties make
superconductive circuits ideal for application to quantum
computation. Also, because superconductive devices can be
fabricated using techniques of microelectronic processing,
the resulting circuits are potentially scalable to the level
of integration required to implement complex algorithms. :: Tue 11/25/03, 4.30pm in 6-120 Peter Zoller (Univ. Innsbruck) :: Mon 11/24/03, 4.00pm in 4-270 (QIP seminar) Igor Devetak (IBM) 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 bymaking them coherent. :: Mon 11/17/03, 4.00pm in 4-270 (QIP seminar) Eddie Farhi (MIT) The Quantum Adiabatic Algorithm is a promising candidate for solving some computationally interesting problems, but it has not been possible to determine the required run time of the algorithm in these cases. I will report on recent attempts to study the performance of the algorithm on randomly generated sets of instances. :: Mon 11/3/03, 4.00pm in 4-270 (QIP seminar) Dave Bacon (Caltech) There are distinct physical reasons why classical computers act as naturally error free devices. Not all classical systems can act as robust classical computers. Similarly we should not expect all quantum systems to be useful for quantum computation. More interestingly we can ask the question of whether there exist (or whether we can engineer) naturally fault-tolerant quantum computers. In this talk I will discuss recent progress toward this goal and present a sequence of examples which possess many of the properties of a naturally fault-tolerant quantum computer. :: Mon 10/27/03, 4.00pm in 4-270 (QIP seminar) Karol Zyczkowski (Smoluchowski Institute of Physics, Jagiellonian University, Cracow, and Center for Theoretical Physi) Wehrl entropy, defined as the average entropy of the Husimi
function, may be used to quantify the localization of any
quantum state in the phase space. The coherent states are as
much localized in phase space as possible. In a
finite-dimensional Hilbert space one defines the SU(2)
spin-coherent states, and according to the Lieb conjecture
their Wehrl entropy of is minimal in the set of all (mixed)
states. The same conjecture may be formulated for higher,
SU(N) coherent states. :: Mon 10/6/03, 4.00pm in 4-270 (QIP seminar) Dave Kielpinski (MIT) I will describe experiments now in preparation for laser-cooling of hydrogen. Our new laser cooling method, which uses mode-locked lasers, can cool atomic species whose level structure makes traditional laser cooling difficult, e.g. hydrogen. We will apply this technique to obtain up to 109 H atoms at mK temperatures, starting from a helium-cooled H beam at 10 K. The technique generalizes trivially to cooling of deuterium and antihydrogen. Laser cooling of carbon also appears feasible. :: Mon 9/29/03, 4.00pm in 4-270 (QIP seminar) Jeff Shapiro (MIT) In semiclassical theory, light is a classical electromagnetic wave and the fundamental source of photodetection noise is the shot effect arising from the discreteness of the electron charge. In quantum theory, light is a quantum-mechanical entity and the fundamental source of photodetection noise comes from measuring the photon-flux operator. The Glauber coherent states are Gaussian quantum states which represent classical electromagnetic radiation. Quantum photodetection of these states yields statistics that are indistinguishable from the corresponding Poisson point-process results of semiclassical photodetection. Optical parametric interactions, however, can be used to produce other Gaussian quantum states, states whose photodetection behavior cannot be characterized semiclassically. A unified analytical framework is presented for Gaussian-state photodetection that includes the full panoply of nonclassical effects that have been produced via parametric interactions. :: Mon 9/22/03, 4.00pm in 4-270 (QIP seminar) Daniel Gottesman (Perimeter Institute (Waterloo, CAN)) 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. :: Mon 9/15/03, 4.00pm in 4-270 (QIP seminar) Timothy Havel (MIT) We introduce a nonsymmetric real matrix which contains all the information that the usual Hermitian density matrix does, and which has exactly the same tensor product structure. The properties of this matrix are analyzed in detail in the case of multi-qubit (e.g. spin = 1/2) systems, where the transformation between the real and Hermitian density matrices is given explicitly as an operator sum, and used to convert the essential equations of the density matrix formalism into the real domain. :: Mon 6/2/03, 2.00pm in 6-322 (Special Seminar) Jiannis Pachos (Imperial College (London)) An economical dynamical control scheme is presented in order to perform quantum computation on a one dimensional optical lattice, where each atom encodes one qubit. The model is based on atom tunneling transitions between neighboring sites of the lattice. They can be activated by external laser beams resulting in a two-qubit phase gate or in an exchange interaction. A realization of the Toffoli gate is presented which requires only a single laser pulse and no individual atom addressing. :: Mon 5/12/03, 4.00pm in 4-237 (QIP seminar) Charles Marcus (Harvard) There have been a number of theoretical proposals to use the electron spin as a qubit. This talk reviews the experimental situation with controlling, measuring, and storing spin in semiconductor quantum dot systems. :: Fri 5/9/03, 3.00pm in 4-237 (QIP seminar) Peter Hoyer (University of Calgary) I would like to talk about the computational power of quantum circuits. In particular, I`d like to discuss the power of some of the weakest models one can think of: circuits of constant depth. You can think of circuits of constant depth as algorithms that run in constant time with polynomially many processors. Classically, such circuits have extremely limited power. :: Mon 5/5/03, 4.00pm in 4-237 (QIP seminar) Adrian Kent (Damtp, Cambridge) I describe a new protocol for cheat sensitive quantum bit commitment, and a protocol for quantum key distribution with (at least partial) security guaranteed by the impossibility of superluminal signalling. :: Tue 4/29/03, 1.30pm in 37-252 Berggren Karl (MIT) At the level of single atoms and electrons, matter exhibits strange quantum behaviors that we do not encounter in our everyday world. A computer using these behaviors--a quantum computer--would solve some problems much faster than a conventional computer... if it could be built. Two opposing constraints make realizing such a computer challenging: fabrication of atomic-scale objects is difficult, while large objects generally appear to obey the well-established laws of classical physics. In a superconductor, however, the quantum-mechanical wavefunction of the electron pairs extends for a large distance, so some of the stranger aspects of quantum mechanics remain observable at a macroscopic scale. Superconductors are, therefore, in principle well suited to quantum computation because they allow manipulation of quantum effects using devices with a more manageable length scale--in the 100s of nanometers, rather than the 10s of nanometers. In practice, however, the fabrication challenges of this approach remain daunting. For example, submicron Josephson junctions with very low leakage currents are required in a superconductive materials technology that can be integrated with complex electronics. This seminar will focus on the challenges faced in fabricating an elementary quantum computer using superconductive electronics. These challenges illustrate some of the difficulties of device fabrication in the nanometer-length-scale and quantum regimes. :: Mon 4/28/03, 4.00pm in 4-237 (QIP seminar) Julia Kempe (University of Paris Sud) We will present some recent results on alternative computational paradigms for quantum computation which complement the usual quantum circuit model and might offer new insights and tools both for the creation of new algorithms as well as new possibilities to implement them. :: Fri 4/25/03, 12.00pm in 6-322 (CTP Lunch Seminar) Andrew Landahl (MIT) Quantum computers get a lot of press because they can crack public-key cryptosystems. This emphasis says more about the society we live in than scientific advance. One discovery that should have broad and long-lasting scientific ramifications is that quantum systems can expel noise using software rather than hardware. In this talk I will give a gentle introduction to quantum error correction --- a scheme for achieving just this feat. Even if you`re not a genius, come anyway: the pizza is free and you`ll feel better about your quantum self afterwards. :: Wed 4/23/03, 4.00pm in 13-2137 (Special Seminar) Irinel Chiorescu (Delft University of Technology) Superconducting circuits with mesoscopic Josephson junctions are expected to behave according to the laws of quantum mechanics if they are separated sufficiently from external degrees of freedom. Such structures are attractive candidates for solid-state quantum computing as they can be scaled up to large numbers of qubits. We have observed coherent time evolution between two quantum states of a flux qubit comprising three Josephson junctions in a loop [Science 299, 1869 (2003)]. Readout by means of an attached SQUID revealed quantum-state oscillations with high fidelity. The superposition of the two states carrying opposite macroscopic persistent currents is manipulated by resonant microwave pulses. :: Mon 4/14/03, 4.00pm in 4-237 (QIP seminar) Leonid Gurvits (Los Alamos National Laboratory) I will talk about the sizes of largest balls around the fully mixed density matrix (i.e. normalized identity matrix) which do not contain entangled matrices. The following results will be presented: :: Mon 3/17/03, 4.00pm in 4-237 (QIP seminar) Scott Aaronson (Berkeley) When we gaze into the cosmos, we find P, NP, BQP, and farther off in the distance, PSPACE, NEXP, and NEEE. Yet I\'m told there\'s another cosmos, one that appears (3+1)-dimensional, Lorentz-invariant, isotropic, and accelerating. In this talk I\'ll propose research questions that connect the two cosmoses. I\'ll also give an actual result: contrary to a claim of Benioff, a \'quantum robot\' could search a 3-D spatial region in time O(sqrt(n)), or O(sqrt(n)polylog(n)) for a 2-D region. A naive Grover implementation fails because the speed of light is finite. This result has some interesting connections to black hole thermodynamics and cosmological entropy bounds. :: Fri 3/14/03, 11.45am in 12-132 (Chez Pierre) Lev Ioffe (Rutgers) 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 by 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 2K 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. :: Mon 3/10/03, 4.00pm in 4-237 (QIP seminar) Bruce Boghosian (Tufts University) Simulating the motion of a turbulent fluid is one of the most difficult problems in all of computational science. We begin by explaining why this problem is so difficult, and show that its classical algorithmic complexity scales as the cube of the Reynolds number of the fluid. We then describe a particular algorithm for hydrodynamic simulation that is classically reversible -- the hydrodynamic lattice gas -- and discuss how it may be adapted to simulate a Navier-Stokes fluid on a quantum computer. Finally, we compare a number of different possible implementations of this algorithm, and derive the quantum algorithmic complexity of each, under various sets of assumptions. :: Mon 3/3/03, 4.00pm in 4-237 (QIP seminar) Hideo Mabuchi (Caltech) Recent experimental work in our group has focused on the development of technical infrastructure for real-time quantum measurement and quantum feedback control. In this talk I will review our results on adaptive homodyne measurement of optical phase, and discuss our ongoing work on measurement and feedback control of collective spin variables in laser-cooled atoms. I will also discuss some ongoing theoretical work on the characterization of measurement-induced spin squeezing. :: Tue 2/25/03, 11.00am in 13-2127 (von Hippel room) (Special Seminar) Alexei Ustinov (Erlangen-Nuremberg, Germany) In the talk I will present and discuss our recent experiment that demonstrates quantum tunneling of a single superconducting vortex in a long Josephson junction. The vortex behaves as a macroscopic particle with a spatial extent of several micrometers which tunnels through a potential barrier created by a magnetic field applied to the junction. We probe the quantum properties of this particle directly by investigating the statistics of individual tunneling events. Measurements of vortex escape in the presence of microwave radiation clearly indicate the quantization of the vortex energy levels in the potential well. Both the tunneling rate and the energy level separation can be tuned in experiment by varying the applied magnetic field. Engineering an energy profile for a vortex in a long Josephson junction opens an opportunity for designing a vortex qubit. The design of the qubit based on two states of the vortex in a heart-shaped long Josephson junction will be discussed. In the classical regime, experimental test of preparation and read-out of vortex states in this qubit will be presented. :: Mon 2/10/03, 4.00pm in 4-237 (QIP seminar) Alexander Sergienko (Boston University) A pair of photons (two-photon state) generated in the nonlinear optical process of spontaneous parametric down conversion (SPDC) is strongly entangled in energy, time, polarization, and space (momentum). This simultaneous entanglement in more than one pair of quantum variables (hyper-entanglement) serves as a powerful tool in the development of novel information processing techniques and in the construction of new quantum measurement technologies. :: Mon 2/3/03, 3.00pm in 12-132 (Special Seminar) Marcus Kindermann (Leiden University) The current--voltage or charge--phase duality plays a central role in quantum transport. It was studied originally in connection with superconducting Josephson junctions and more recently in the context of single-electron tunneling. Quantum mechanically, the duality appears because current $I$ and voltage $V$ are non commuting operators. This is manifested in the canonical commutator $[\Phi,Q]=ie$ of the transferred charge $Q=\int_{0}^{\tau}I(t)dt$ with the accumulated phase $\Phi=(e/\hbar)\int_{0}^{\tau}V(t)dt$ (in a given detection time $\tau$). :: Fri 1/24/03, 4.00pm in 12-134 (Special Seminar) Jean-Noel Fuchs (Ecole Normale, Paris) We consider an ultra-cold gas of (non-condensed) bosons or fermions with two internal levels (treated as a pseudo-spin 1/2). Spin transport properties of a spin polarized sample are studied using a quantum kinetic equation, which describes the time evolution of the Wigner distribution associated to the single-particle density operator. It treats orbital variables classically, whereas spin variables remain quantum-mechanical. The gas behavior is very different from that of a classical gas, even though the system is not degenerate. These effects result from the existence of quantum coherences in internal (spin) space. As an example, we discuss a recent JILA experiment, where transient spin state separation was observed as a result of initial transverse spin polarization. At the maximum of separation, the system is in a macroscopic superposition of internal states and is far from local equilibrium. The subsequent relaxation towards equilibrium is studied, with a brief comment on the role of decoherence. :: Mon 12/16/02, 4.00pm in 4-231 (QIP seminar) Jeffrey Goldstone (MIT) I will report on what Farhi et al. have been up to lately, namely: :: Mon 12/9/02, 4.00pm in 4-231 (QIP seminar) Sean Barrett (Yale University) Understanding nuclear spin dynamics in Si:P is an important step (B.E. Kane, quant-ph/0003031) towards the realization of semiconductor spin-based qubits (B.E. Kane, Nature 393, 133 (1998)). In support of this effort, our group has been measuring NMR spectra and relaxation times for both Si-29 and P-31 nuclei, in fields up to 15.3 Tesla. While doing this, we have discovered several surprising features of Si-29 NMR in multiple pulse experiments: even/odd echo asymmetry, and effects reminiscent of spin-locking and stimulated echoes, but with interesting twists (e.g., longer \'\'coherence\'\' times). Our progress towards understanding these phenomena, and their possible implications for QIP, will be described. :: Tue 12/3/02, 4.15pm in 12-132 (QIP seminar) Alessandro Silva (Weizmann Institute of Science) In controlled dephasing an environment (the dephasor) is engineered to cause dephasing of coherent transport through a nanoscale system (the dephasee). The resulting dephasing can be detected by inserting the dephasee in one arm of an Aharonov-Bohm interferometer. I will discuss the situation where the dephasor is a biased Quantum Point Contact and the dephasee is a Quantum Dot either at a Coulomb Blockade resonance or in the regime where the Kondo effect is observed. By means of a direct comparison of the two problems I will discuss the qualitative influence of the strong correlations present in the Kondo regime on the response of the Quantum Dot to the interaction with the Quantum Point Contact. :: Mon 11/25/02, 4.00pm in 4-231 (QIP seminar) Dorit Aharonov (MSRI, Hebrew University of Jerusalem) The design of new quantum algorithms has proven to be an extremely difficult task. We consider a different approach to the problem, by systematically studying the problem of quantum state generation. We first prove that a wide class of algorithmic problems (called \'\'statistical zero knowledge\'\') can be reduced to the problem of generating certain superpositions efficiently. This gives a general recipe to reduce graph isomorphism, certain versions of closest vector in a lattice, and many other problems that are natural candidates for efficient quantum algorithms, to the quantum state generation problem. :: Mon 11/18/02, 4.00pm in 4-231 (QIP seminar) John Martinis (NIST Boulder) The Josephson junction is an ideal solid-state system for building electrical \'\'atoms\'\' which can function as quantum bits for a quantum computer. I will discuss recent experimental work based on qubits made from large area (10um by 10um) current-biased Josephson junctions. We calculate coherence times longer than 1-10 us should be possible based on a 2-junction SQUID circuit that isolates the qubit from dissipation of the leads. I will discuss recent measurements on a single qubit that shows Rabi oscillations and fidelity of state preparation and measurement of 85%. We believe the construction of a quantum computer with 10-100 qubits might be reasonably straightforward with this approach. :: Mon 11/4/02, 4.00pm in 4-231 (QIP seminar) Hans Mooji (Delft University of Technology) The superconducting persistent current quantum bit (designed in collaboration with MIT) consists of a closed ring with three small Josephson junctions. The two quantum states have opposite circulating current. Previously, quantum superpositions of these two macroscopic states were demonstrated. Recently, we succeeded in demonstrating coherent quantum oscillations driven by microwave pulses. Also, simple two- and three-pulse sequence were successfully applied. First experiments were also performed on two coupled qubits. Present limitations and plans for the near future will be discussed. :: Mon 10/28/02, 4.00pm in 4-231 (QIP seminar) Hoi-Kwong Lo (Magiq Technologies) :: Wed 10/23/02, 4.15pm in E15-070 Edward Fredkin (MIT visitor) Finite Nature is the assumption that all quantities of physics, including space and time, are discrete. It is the basis of Cellular Automaton models of physics. QST is an advance over earlier CA models; it consistently demonstrates many more aspects of physics. It has a very simple space-time structure and mechanism for the evolution of state. QST representations of angular momentum, mass, energy, momentum, charge, force and CPT are all easy to understand. There is a proof that translation, rotation and time symmetries must arise in QST models at scales above the fixed CA lattice. Possible bases for the laws of QM and the Standard Model can almost be seen by waving one\'s hand. Unlike contemporary physics, every basic aspect of such models can be understood, entirely, without any kind of advanced mathematics. Experimental data that might verify the existence of the lattice has been collected (for other reasons) and is now awaiting analysis. :: Mon 10/21/02, 4.00pm in 4-231 (QIP seminar) Claudio Altafini (SISSA) The controllability of the Schrodinger equation and of the Markovian master equation for N-level quantum mechanical systems is discussed using Lie algebraic tools and notions from Lie semigroup theory. This allows, in particular, to characterize the generators of Quantum Dynamical Semigroups that are controllable via unitary control. The two level case is treated in detail. :: Mon 10/7/02, 4.00pm in 4-231 (QIP seminar) Andreas Winter (University of Bristol) :: Mon 10/7/02, 4.00pm in 4-231 (QIP seminar) Patrick Hayden (Caltech) 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 isn\'t. (The answers, as it turns out, are strikingly different.) Moreover, this trade-off curve appears to control not only the rates of exchange between bits and qubits in data compression but also those between bits and ebits in the remote preparation of pure states, both pure and entangled. I\'ll end by describing a probability-free version of the trade-off theorem that can be interpreted as an answer to the question: \'\'How many classical bits does a qubit cost?\'\' :: Mon 9/30/02, 4.00pm in 4-231 (QIP seminar) Jose Ignacio Latorre (University of Barcelona) Majorization theory establishes a far more refined relation of order between probability distributions than the concept of entropy. The solutions to a quite a number of problems in quantum information have been proven to relay on majorization relations. We shall show that the known efficient quantum algorithms do carry a step-by-step majorization in their computational basis. :: Mon 9/23/02, 4.00pm in 35-225 Arun Pati (MSRI, Berkeley) Arbitary quantum states cannot be copied. To make a copy we must provide complete information about the system. But can a quantum system self-replicate? This question would be important for understanding artifical living systems. Out of many characteristics, one basic important feature of a living system is self-reproduction of original information. Trying to mechanize living system, von Neumann showed that it is possible to design a \`universal constructor\' which not only can replicate itself but also can produce a copy of the program that does the replication using classical laws of physics. Wigner has argued that if quantum mechanics is fundamental laws of nature it should reason out self-replication process--an important property of a artificial or real living system. In this talk We will show that there is no deterministic universal quantum constructor which can self-replicate an arbitrary state with finite resource. We delineate conditions under which universal constructor can be designed deterministically and probabilistically. :: Mon 9/16/02, 4.00pm in 35-225 Navin Khaneja (Harvard) Optimal Control of Spin Dynamics in the Presence of Relaxation Experiments in coherent spectroscopy correspond to control of quantum mechanical ensembles guiding them from initial to final target states. The control inputs (pulse sequences) that accomplish these transformations should be designed to minimize the effects of relaxation and to optimize the sensitivity of the experiments. For example in nuclear magnetic resonance (NMR) spectroscopy, a question of fundamental importance is what is the maximum efficiency of coherence or polarization transfer between two spins in the presence of relaxation. Furthermore, what is the optimal pulse sequence which achieves this efficiency? In this talk, I will initiate the study of a class of control systems, which leads to analytical answers to the above questions. Unexpected gains in sensitivity are reported for the most commonly used experiments in NMR spectroscopy. :: Thu 9/12/02, 4.15pm in 10-250 Steven Girvin (Yale University) Recent experimental breakthroughs have led to the construction of artificial superconducting ?atomsi: electrical circuits whose state variables (voltages and currents) are intrinsically quantum mechanical. These two-state systems can be used as quantum bits. Through proper engineering, decoherence rates of these ?atoms? are beginning to approach the theoretical limits set by spontaneous emission of microwave photons into the cold vacuum and complete quantum control has been demonstrated with as many as 104 coherent Ramsey fringe oscillations being detected. Rapid progress is also occurring in the development of novel high-efficiency read out schemes. This talk will give an introduction to these remarkable experimental developments and discuss some of the related theoretical issues that they open up. :: Thu 6/13/02, 4.00pm in 56-114 Daniel Collins (Univ. Bristol) We show that quantum entanglement has a very close classical analogue, namely secret classical correlations. The fundamental analogy stems from the behaviour of quantum entanglement under local operations and classical communication and the behaviour of secret correlations under local operations and public communication. A large number of derived analogies follow. In particular, teleportation is analogous to the one-time-pad, the concept of \'\'pure state\'\' exists in the classical domain, entanglement concentration and dilution are essentially classical secrecy protocols, and single copy entanglement manipulations have such a close classical analog that the majorization results are reproduced in the classical setting. This analogy allows one to import questions from the quantum domain into the classical one, and vice-versa, helping to get a better understanding of both. Also, by identifying classical aspects of quantum entanglement it allows one to identify those aspects of entanglement which are uniquely quantum mechanical. :: Mon 5/6/02, 4.00pm in 56-114 Philip H. Bucksbaum (Univ. Michigan) Ultrafast light pulses can be used to sculpt quantum wave packets in atoms and molecules. I will describe how this technology works, and then show some of the applications in the fields of quantum information, coherent control of chemical bonds, and modulation of x-rays. :: Mon 4/29/02, 4.00pm in 56-114 Juan-Pablo Paz (Univ. Buenos Aires) In this talk I will present a review of how to build families of quantum circuits representing unitary operators which are quantizations of classical chaotic systems. I will show how to represent the dynamics of these systems in phase space by means of the discrete Wigner function. Finally, I will analyze the behavior of the above systems when they evolve coupled to an external environment that produces decoherence. In particular, I will show that for a large variety of cases the rate of entropy production is determined by the classical Lyapunov exponent. :: Mon 4/22/02, 4.00pm in 56-114 Richard Cleve (Univ. Calgary, Canada) Communication complexity is concerned with the amount of communication required to perform distributed information processing tasks. We give examples of information processing tasks that can be accomplished with significant savings in communication when quantum resources are available. We also point out some interesting connections between quantum communication complexity and quantum information theory, quantum algorithms, as well as Bell\'s Theorem. :: Wed 4/10/02, 4.30pm in 6-322 Alexei Kitaev (Caltech) Anyons are quasiparticles that can be characterized as defects in a topologically orded state of a two-dimensional quantum system. I describe a toy model that gives rise to Abelian anyons. The ground state of such a system on the torus is degenerate; this phenomenon can be used to implement a decoherence-protected quantum memory. With non-Abelian anyons, degeneracy occurs even in the planar topology. Sufficiently nontrivial non-Abelian systems allow universal quantum computation. Unitary gates are represented as braiding of anyons whereas measurements are perfomed by fusing quasiparticles in pairs and observing the outcome. :: Tue 4/9/02, 4.00pm in 12-132 Alexei Kitaev (Caltech) A spin 1/2 system on a honeycomb lattice is studied. The interactions between nearest neighbors are of XX, YY or ZZ type, depending on the direction of the link; different types of interactions may differ in strength. The model is solved exactly; a phase diagram in the parameter space is obtained. One of the phases has an energy gap and carries excitations that are Abelian anyons. The other phase is gapless, but acquires a gap in the presence of magnetic field. In the latter case, the excitations are non-Abelian anyons. :: Mon 4/8/02, 4.00pm in 56-114 Marlan O. Scully (Texas A&M University) The second law of thermodynamics embodies deep truths and profound insights. Indeed thermodynamics was the main spring of quantum theory. Some think the time is ripe for quantum mechanics to return the favor by challenging the foundations of thermodynamics, and Norman Ramsey(1) has shown how negative temperatures do just that. Aspects of current research into and controversy surrounding such issues will be discussed as follows: :: Mon 4/1/02, 4.00pm in 56-114 Wim Van Dam (UC Berkeley, MSRI & HP) Homomorphic encryption concerns the situation where one party (Alice) has a secret input x, and another party (Bob) has a secret function F. Alice wants Bob to evaluate the function value F(x), but she does not want Bob to know x or F(x). Bob, on his part, is only willing to tell Alice the specific value F(x), not the general description of his function F. A solution to this problem is possible with the help of a \'homomorphic\' encryption scheme E that allows Bob to calculate the encrypted answer E(F(x)), given the encrypted input E(x). :: Mon 3/18/02, 4.00pm in 56-114 Jeffrey H. Shapiro (M.I.T.) The preeminent obstacle to the development of quantum information technology is the difficulty of transmitting quantum information over noisy and lossy quantum communication channels, recovering and refreshing the quantum information that is received, and then storing it in a reliable quantum memory. A team of researchers from the Massachusetts Institute of Technology and Northwestern University (MIT/NU) is developing a singlet-based quantum communication approach that uses a novel ultrabright source of polarization-entangled photon pairs and a trapped-atom quantum memory. :: Mon 3/11/02, 4.00pm in 56-114 Dorje Brody (Imperial College, London) For a given quantum system, each of its physical characteristics can be represented by geometrical features that are preferentially identified in the space of pure quantum states. In this talk, I will construct a number of examples of such features as they arise in the state spaces for elementary spin particles. Special attention will be drawn to the meaning of quantum entanglement, as well as various statistical aspects of quantum physics. :: Mon 3/4/02, 4.00pm in 56-114 William K. Wootters (Williams College, MA) Quantum entanglement bears some resemblance to ordinary classical correlation, but there are important differences. In particular, whereas any number of classical variables can in principle be perfectly correlated with each other--the temperature fluctuations in ten different cities could conceivably be exactly parallel--any entanglement that exists between two quantum objects has the effect of limiting the entanglement that either of these objects can have with the rest of the world. In this talk I will discuss a number of examples of quantum systems in which this restriction on the sharing of entanglement can be expressed quantitatively. For instance, in the special case of three spin-1/2 particles A, B, and C, the measure of entanglement called \'\'concurrence\'\' shows a simple trade-off between the AB entanglement and the AC entanglement. For a collection of several spin-1/2 particles arranged in a ring, the entanglement sharing problem points to an interesting feature of antiferromagnetic chains, namely, that in a certain sense they favor states with maximum entanglement. :: Mon 2/25/02, 4.00pm in 56-114 Brian King (McMaster University) In NIST\'s Laser Cooling and Trapping Group, we have been constructing an experiment to test various ideas for neutral atom quantum information processing. The experiment is based around a beam-loaded, Ioffe-trapped 87Rb Bose Einstein Condensate. I will give a brief overview of quantum computing, and go on to talk about promising schemes for neutral atom \'\'quantum computer\'\' architectures. I\'ll then discuss recent progress on the experiment, including the achievement of BEC in 87Rb and studies of loading the BEC into an optical lattice. :: Thu 2/14/02, 11.00am in 13-3038 Lara Faoro (Institute for Scientific Interchange, Torino, Italy) Non abelian phases can be generated in certain network of Josephson junctions. Here we explicitly construct such a device and show how it can be applied both for adiabatic pumping and as an implementation of a quantum computer. :: Mon 2/11/02, 4.00pm in 3-343 William D. Oliver (Stanford University) In this talk, I will present our experimental and theoretical efforts to generate and detect EPR pair-type electron entanglement inmesoscopic electron systems. On the detection side, we have developed a set of quantum electron optical \'\'tools\'\': an electron beamsplitter, a Hong, Ou, Mandel-type electron collision analyzer, and a Hanbury Brown and Twiss-type intensity interferometer. On the generation side, we have recently proposed a means to generate entangled electrons via a quantum dot in analogy to a Chi-(3) four-wave mixing process with photons. An electron bunching/antibunching experiment comprising the quantum electron optical \'\'tools\'\' can be used to characterize the degree of entanglement of such an electron entangler. Finally, I will present current noise measurements of a quantum point contact biased at the 0.7 structure, discuss the physical implications of the noise suppression observed, and present our proposed experiment to determine if the 0.7 effect is akin to a polarization beam splitter. |
| |
 |  |
