xQIT W. M. Keck Foundation Center For Extreme Quantum Information Theory at the Massachusetts Institute of Technology
News About People Research Publications Events Courses Positions Contact
     
 

Seminars

Workshops

Minicourses

Conference

  Events

xQIT: Seminars

Date and Time: Monday , 6.9.2008, 3:00PM

Location: 6C-442

Speaker :  Peter Young (UCSC)
Title: Size Dependence of the Minimum Excitation Gap in the Quantum Adiabatic Algorithm

Abstract:

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

 

 

Date and Time: Monday , 6.9.2008, 3:00PM

Location: 6C-442

Speaker :  Peter Young (UCSC)
Title: Size Dependence of the Minimum Excitation Gap in the Quantum Adiabatic Algorithm

Abstract:

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

 

Date and Time: Monday , 5.12.2008, 4:15PM

Location: Room 36-428

Speaker :  Carlos Mochon (Perimeter Institute)
Title: Quantum weak coin flipping with arbitrarily small bias

Abstract:

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.

Quantum coin flipping has been a longstanding open problem, and its solution uses an innovative formalism developed by Alexei Kitaev for mapping quantum games into convex optimization problems. The optimizations are carried out over duals to the cone of operator monotone functions, though the mapped problem can also be described in

a very simple language that involves moving points in the plane.

Time permitting, I will discuss both Kitaev's formalism, and the solution that leads to quantum weak coin flipping with arbitrarily small bias.

 

Date and Time: Monday , 5.5.2008, 4:15PM

Location: Room 36-428

Speaker :  Barbara Terhal (IBM)
Title: Simulation of Many-Body Hamiltonians using Perturbation Theory withBounded-Strength Interactions

Abstract:

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.

 

Date and Time: Monday , 4.14.2008, 4:15PM

Location: Room 36-428

Speaker : Michel Devoret (Yale)
Title: Quantum-Mechanical Circuits

Abstract:

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.

 

Date and Time: Monday , 4.7.2008, 4:15PM

Location: Room 36-428

Speaker : John Watrous (Waterloo)
Title: Entanglement exchange in multi-prover quantum interactive proofs

Abstract:

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.

In this talk I will discuss a simple and general way that multiple provers can manipulate entanglement in multi-prover quantum interactive proofs.  The method, called entanglement exchange, allows for simple proofs of some interesting facts about multi-prover quantum interactive proofs and provides the answer to a fundamental question

about them: how much entanglement do the provers need to implement an

optimal strategy for a given input?

The talk will be based on joint work with Debbie Leung and Ben Toner.

 

Date and Time: Monday , 3.31.2008, 4:15PM

Location: Room 36-428

Speaker : Alain Tapp (Montreal)
Title: Anonymous quantum communication

Abstract:

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

Joint work with Gilles Brassard, Anne Broadbent, Joseph Fitzsimons and

Sebastien Gambs.

 

Date and Time: Monday , 3.17.2008, 4:15PM

Location: Room 36-428

Speaker : Markus Grassl (Innsbruck)
Title: New families of non-additive quantum codes from Goethals and Preparata codes

Abstract:

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.

We extend the framework of stabilizer codes to the union of stabilizer codes which allows to construct non-additive codes from any stabilizer code.  Using constructions similar to those of CSS codes, families of non-additive quantum codes based on the binary Goethals and Preparata codes are presented.  In combination with Steane's enlargement

construction, we obtain a family of non-additive quantum codes with parameters ((2m,22^m-5m+1,8)). The dimension of these codes is eight times higher than the dimension of the best known additive quantum codes of equal length and minimum distance.

This is joint work with Martin Roetteler.

 

Date and Time: Monday , 2.11.2008, 11:00AM

Location: Room 36-462

Speaker : David Vitali (University of Camerino)
Title: Emergence of atom-light-mirror entanglement inside an optical cavity

Abstract:

We propose a scheme for the realization of a hybrid, strongly quantum-correlated system formed of an atomic ensemble surrounded by a high-finesse optical cavity with a vibrating mirror. We show that the steady state of the system shows tripartite and bipartite continuous variable entanglement in experimentally accessible parameter regimes, which is robust against temperature.

 

Date and Time: Monday , 12.03.2007, 4:00PM

Location: Room 36-428

Speaker :  Saikat Guha (MIT RLE)
Title: The entropy photon-number inequality and capacity of bosonic channels

Abstract:

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.

 

Date and Time: Monday , 11.19.2007, 4:00PM

Location: Room 36-428

Speaker :  Mohammad Amin (D-Wave)
Title: Adiabatic Quantum Computation with Noisy Qubits

Abstract:

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.

 

Date and Time: Monday , 11.05.2007, 4:00PM

Location: Room 36-428

Speaker :  Pawel Wocjan (UCF)
Title: Classical Problems Characterizing the Power of Quantum Computing

Abstract:

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.

 Starting from this physically motivated problem, we formulate two simple purely classical PromiseBQP-complete problems. Roughly speaking, the first problem is to decide whether a diagonal entry of a power of a sparse matrix is greater or smaller than a certain value.  The second is the following combinatorial problem. We are given three strings s, t, and t' over some finite alphabet and a symmetric relation on substrings of constant length. The relation specifies which substrings are allowed to be replaced with each other. The problem is to decide for a specific value m whether there are more possibilities to obtain

t or t' from s after exactly m replacements.

This talk is based on joint projects with Dominik Janzing and Shengyu Zhang.

 

Date and Time: Thursday, 11.01.2007, 2:30PM

Location: Room 32-D677 [LIDS Seminar Room]

Speaker :  Ramon van Handel (California Institute of Technology)
Title: Observability and Nonlinear Filtering

Abstract:

The important connection between the notions of controllability and observability in linear systems theory and the asymptotic properties of the Kalman filter has been common knowledge since the early 1960s. Whether such a connection can be made beyond the linear case has remained unclear, however, despite much recent work on the asymptotic properties of nonlinear filters.  In this talk, I will show that notions of observability, controllability, and detectability are fundamentally related to the asymptotic properties of nonlinear filters.  The central result---that observability implies stability of the nonlinear filter in a suitable sense---requires almost no assumptions on the filtering model, and its proof follows from basic probabilistic and functional analytic arguments.  In the special case that the signal is a finite state Markov process and the observations are of the additive white noise type, the (Wonham) filter is stable if and only if a detectability condition is satisfied in the spirit of the linear case.  I will finally discuss some shortcomings of the current results and some directions towards a more general asymptotic theory for hidden Markov processes.

 

Date and Time: Thursday, 11.01.2007, 3:00PM

Location: Room 6C-442 (ctp)

Speaker :  Sahel Ashhab (RIKEN)
Title: Landau-Zener crossings in quantum-computing systems

Abstract:

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

 

 

Date and Time: Thursday, 11.01.2007, 2:30PM

Location: Room 32-D677 [LIDS Seminar Room]

Speaker :  Ramon van Handel (California Institute of Technology)
Title: Observability and Nonlinear Filtering

Abstract:

The important connection between the notions of controllability and observability in linear systems theory and the asymptotic properties of the Kalman filter has been common knowledge since the early 1960s. Whether such a connection can be made beyond the linear case has remained unclear, however, despite much recent work on the asymptotic properties of nonlinear filters.  In this talk, I will show that notions of observability, controllability, and detectability are fundamentally related to the asymptotic properties of nonlinear filters.  The central result---that observability implies stability of the nonlinear filter in a suitable sense---requires almost no assumptions on the filtering model, and its proof follows from basic probabilistic and functional analytic arguments.  In the special case that the signal is a finite state Markov process and the observations are of the additive white noise type, the (Wonham) filter is stable if and only if a detectability condition is satisfied in the spirit of the linear case.  I will finally discuss some shortcomings of the current results and some directions towards a more general asymptotic theory for hidden Markov processes.

 

Date and Time: Wednesday, 10.31.2007, 1:00PM

Location: Room 32-D451

Speaker :  Ramon van Handel (California Institute of Technology)
Title: An introduction to filtering in noncommutative probability

Abstract:

Signals measured in a laboratory are always ordinary stochastic processes, yet quantum mechanics tells us that many physical quantities do not behave in  this classical probabilistic way.  The mathematical framework in which both these observations take their proper place is that of noncommutative probability, where classical notions of probability spaces, random variables, etc., are replaced by operator algebraic counterparts. A stereotypical experiment which can be modelled in this framework is that of laser light which is scattered off an atom and is subsequently measured using a configuration of photodetectors.  This gives rise to a classical stochastic process (the photocurrent), and it is natural to ask what can be inferred about the atomic observables (position, momentum, ...) from the observed process.  The pursuit of this question leads to a theory which is almost identical to the classical theory of nonlinear filtering, and is an important ingredient in quantum stochastic control problems.  This talk is intended as an introduction to noncommutative probability and quantum filtering theory, with an emphasis on the role of the abstract Bayes formula in the noncommutative setting.

 

Date and Time: Monday, 10.29.2007, 4:00PM

Location: Room 36-428

Speaker :  Umesh Vazirani (UC Berkeley)
Title: Two challenges in quantum algorithms

Abstract:

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.

The second challenge is to exploit the strong negative results about the non-abelian hidden subgroup problem to design quantum resistant cryptographic primitives. I will outline a one-way function, whose security is closely related to solving the hidden subgroup problem over the general linear group.

 

Date and Time: Monday, 10.22.2007, 4:00PM

Location: Room 36-428

Speaker :  Cris Moore (UNM)
Title: On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism, and Thoughts on Classical Cryptosystems Secure Against Quantum Attack

Abstract:

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.

I will then discuss joint work with Alex Russell and Umesh Vazirani in which we assume that the hidden subgroup problem over the general linear group GL_n(q) is hard, and use this to define a one-way function secure against quantum attack: that is, a function f which can be computed classically, but which is hard even for quantum computers to invert. I will also show that a natural attack on the McEliece cryptosystem leads to a difficult case of the hidden subgroup problem, suggesting that this cryptosystem may be secure against quantum attack.

 

Date and Time: Monday, 10.15.2007, 4:00PM

Location: Room 36-428

Speaker :  Yaoyun Shi (Michigan)
Title: Quantum communication complexity of block-composed functions

Abstract:

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
F(x, y) = f(x1 y1, x2 y2, ..., xn yn),
where f is a symmetric Boolean function on n Boolean inputs, and xi, yi are the i'th bit of x and y, respectively. His elegant proof critically depends on the symmetry of f.

We develop a lower-bound method that does not require symmetry and prove the conjecture for a broader class of functions. Each of those functions F(x, y) is obtained by what we call the "block-composition'' of a "building block''

g : {0, 1}k by {0, 1}k -> {0, 1}, with an f : {0, 1}n -->{0, 1},
such that
F(x, y) = f(g(x1,y1), ..., g(xn, yn)),
where xi and yi are the i'th k-bit block of x and y, respectively.
We show that as long as g itself is "hard'' enough, its block-composition with an arbitrary f has polynomially related quantum and classical communication complexities. Our approach gives an alternative proof for Razborov's result (albeit with a slightly weaker parameter), and establishes new quantum lower bounds. For example, when g is the Inner Product function for k= Ω(log n), the deterministic communication complexity of its block-composition with any f is asymptotically at most the quantum complexity to the power of 7.
This is a joint work with my student Yufan Zhu.

 

Date and Time: Monday, 10.10.2007, 3:00PM

Location: Room 26-214

Speaker :  Graeme Smith (IBM)
Title: Capacities of a quantum channel with symmetric assistance

Abstract:

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.

 

Date and Time: Monday, 10.01.2007, 4:00PM

Location: Room 36-428

Speaker :  Seth Lloyd (MIT)
Title: Quantum Private Queries

Abstract:

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.

 

Date and Time: Monday, 09.24.2007, 4:00PM

Location: Room 36-428

Speaker :  Iordanis Kerenidis (Universite Paris-Sud)

Title: Quantum honest verifier statistical zero-knowledge for all interactive proofs

Abstract:

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.

This is joint work with Andre Chailloux (Univ Paris-Sud)

 

Date and Time: Monday, 05.21.2007, 4:00PM

Location: Room 26-214

Speaker : Peter Love (Haverford College)

Title: Quantum cellular automata over finite groups and quantum simulation

Abstract:

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.

 

Date and Time: Monday, 05.16.2007, 4:00PM

Location: Room 26-214

Speaker :  Lorenza Viola (Dartmouth)

Title: Physical and information-theoretic aspects of generalized entanglement

Abstract:

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

 

Date and Time: Monday, 05.14.2007, 4:00PM

Location: Room 26-214

Speaker : Itai Arad (Hebrew U, Jerusalem)

Title: Efficient quantum algorithms for an additive approximation of the Tutte   polynomial and the q-state Potts model

Abstract:

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.

Our methods generalize the recent AJL algorithm for the approximation of the Jones polynomial; instead of using unitary representations, we allow non-unitarity, which seems counter intuitive in the quantum world.  Significant contribution of this is a proof that non-unitary operators can be used for universal quantum computation.

 

 

xQIT: Workshops

xQIT workshops will bring together all MIT participants in the Center along with potential industry collaborators,as well as other Boston-area quantum information researchers. Its primary purpose is to harmonize the elements of our research with programs elsewhere
and to foster collaboration.

 

xQIT: Minicourses

xQIT minicourses will be taught by the Center's personnel with aim of conveying our current work in quantum information theory to industry collaborators and to visiting scientists and engineers.

 

xQIT: Conference

The xQIT Conference on Extreme Quantum Information Theory
May 3-4, 2011

The xQIT Conference on Extreme Quantum Information Theory
November 19-20, 2008

 

 

 

"xQIT will serve as the focal point for research in quantum information theory at MIT."