qis.mit.edu homepeopleseminarscoursesvisitorslinks

Seminar Listing

(single keywords like: Ambainis, adiabatic...)

[photo of a speaker] (c) D.Nagaj

Typical Weekly Calendar

other seminars:


2015 - 2016 (academic year)


:: Fri 9/11/15, 1:30pm in 6C-442

Chris Monroe and Jungsang Kim (University of Maryland; Duke)
Time to Build: Co-designing a Quantum Computer with Trapped Ions

:: Fri 9/18/15, 1:30pm in 6C-442

Or Sattath (MIT)
When must a local Hamiltonian be unfrustrated?

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 10/2/15, 2:10pm in MSR, Horace Mann Conference Room, One Memorial Drive (note different place and time)

Ryan O'Donnell (CMU)
Quantum tomography and random Young diagrams

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 10/9/15, 1:30 in 6C-442

Barry Sanders (University of Calgary)
Multi-Channel Photon Interferometry for Quantum Information Processing

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/23/15, 1:30pm in 6C-442

Michael Walter (Stanford)
Random tensor networks as models of holography


:: Fri 10/30/15, 1:30pm in 6C-442

Ashley Montanaro (U. Bristol)
Quantum walk speedup of backtracking algorithms

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 11/6/15, 1:30pm in 6C-442

Beni Yoshida (Caltech)
Gapped boundaries, group cohomology and fault-tolerant logical gates

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 11/13/15, 1:30pm in 6C-442

Discriminating quantum states: the multiple Chernoff distance

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/20/15, 1:30pm in 6C-442

David Gosset (Caltech)
Some consequences of frustration-freeness

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 12/4/15, 1:30 in 6C-442

John Wright (CMU)
Random words, longest increasing subsequences, and quantum PCA

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 12/11/15, 1:30pm in 2-105

Dave Touchette (Caltech)
The Quantum Information Cost of Forgetting Classical Information

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.

:: Tue 1/5/16, 1:30pm in 6C-442

David Sutter (ETH Zurich)
Relative entropy, recovery maps, and approximate quantum Markov chains

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

:: Thu 1/7/16, 1:30pm in 6C-442

Philipp Kammerlander (ETH Zurich)
Subjectivity in classical and quantum thermodynamics

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.

:: Fri 2/5/16, 1:30pm in 6C-442

Marissa Giustina (University of Vienna)
Significant-loophole-free test of local realism with entangled photons

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.


home :: people :: seminars :: courses :: visitors :: links

qis@mit MIT