other seminars:

:: Fri 9/11/15, 1:30pm in 6C442 Chris Monroe and Jungsang Kim (University of Maryland; Duke) :: Fri 9/18/15, 1:30pm in 6C442 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 hardcore 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) In quantum mechanics, the state rho of a ddimensional 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 RobinsonSchenstedKnuth algorithm. In this talk we will discuss new probabilistic, combinatorial, and representationtheoretic 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 6C442 Barry Sanders (University of Calgary) Quantum information processing is possible via multichannel linear (passive) interferometry with photon number states as some or all of the inputs and photoncoincidence detection at the output ports. The KnillLaflammeMilburn nonlinear sign gate on dualrail photonic qubits and the AaronsonArkhipov BosonSampling scheme are salient examples of linear photonic quantum information processing. Implementations of quantum walks also make use of linear photon interferometry. The famous HongOuMandel 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 HongOuMandel dip setup, extend this theory for accurate and precise characterization of multichannel interferometry based on photon coincidences, extend the HongOuMandel dip concept beyond twochannel to multichannel interferometry, develop theory and (classical) algorithms for computing irreducible representations of SU(m) whose elements represent all mchannel interferometers, and determine the effects of extraneous multiphoton contributions to the desired outputs. Our approach allows for nonsimultaneous 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 proofofprinciple 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 6C442 Michael Walter (Stanford) TBA :: Fri 10/30/15, 1:30pm in 6C442 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 boundederror 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 averagecase exponential speedup. :: Fri 11/6/15, 1:30pm in 6C442 Beni Yoshida (Caltech) In this talk, I will establish the connection among classifications of gapped boundaries in topological phases of matter, bosonic symmetryprotected topological (SPT) phases and faulttolerantly implementable logical gates in quantum errorcorrecting codes. We begin by presenting constructions of gapped boundaries for the ddimensional quantum double model by using dcocycles functions (d geq 2). We point out that the system supports mdimensional excitations (m < d), which we shall call fluctuating charges, that are superpositions of pointlike electric charges characterized by mdimensional 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 codimension2 fluctuating charges exhibit nontrivial multiexcitation 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 multiexcitation braiding statistics, generalizing the notion of the Lagrangian subgroup. As an application, we construct faulttolerantly implementable logical gates for the ddimensional quantum double model by using dcocycle functions. Namely, corresponding logical gates belong to the dth level of the Clifford hierarchy, but are outside of the (d1)th level, if cocycle functions have nontrivial sequences of slant products. :: Fri 11/13/15, 1:30pm in 6C442 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 righthand 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^(1s)} 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 finitedimensional, but otherwise general, quantum states. This upper bound, up to a statesdependent factor, matches the multiplestate generalization of Nussbaum and Szkola's lower bound. Specialized to the case r=2, we give an alternative proof to the achievability of the binaryhypothesis Chernoff distance, which was originally proved by Audenaert et al. :: Fri 11/20/15, 1:30pm in 6C442 David Gosset (Caltech) Frustrationfree local Hamiltonians are a commonly studied subclass of (general) local Hamiltonians. A frustrationfree 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 frustrationfreeness. 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, frustrationfree 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 translationinvariant frustrationfree 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 frustrationfreeness 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 frustrationfree 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 6C442 John Wright (CMU) TBA :: Fri 12/11/15, 1:30pm in 2105 Dave Touchette (Caltech) TBA 