Date and Time: Monday , 6.9.2008, 3:00PM
Location: 6C442
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: 6C442
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 36428
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 twoparty 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 36428
Speaker : Barbara Terhal (IBM)
Title: Simulation of ManyBody Hamiltonians using Perturbation Theory withBoundedStrength Interactions
Abstract:
We show how to map a given nqubit target Hamiltonian with boundedstrength kbody interactions onto a simulator Hamiltonian with twobody interactions, such that the groundstate 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 lowenergy Hamiltonian which relies on the SchriefferWolff transformation of manybody physics.
Date and Time: Monday , 4.14.2008, 4:15PM
Location: Room 36428
Speaker : Michel Devoret (Yale)
Title: QuantumMechanical Circuits
Abstract:
Can the collective variables that describe the state of a radiofrequency circuit, in other words currents and voltages, behave quantummechanically? 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 nonlinear elements are sufficiently nondissipative 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 solidstate
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 36428
Speaker : John Watrous (Waterloo)
Title: Entanglement exchange in multiprover quantum interactive proofs
Abstract:
Little is known about the expressive power of multiprover 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 multiprover 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 multiprover quantum interactive proofs. The method, called entanglement exchange, allows for simple proofs of some interesting facts about multiprover 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 36428
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 informationtheoretically 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 36428
Speaker : Markus Grassl (Innsbruck)
Title: New families of nonadditive quantum codes from Goethals and Preparata codes
Abstract:
Most of the quantum errorcorrecting codes (QECCs) are based on the stabilizer formalism which relates quantum codes to certain additive codes over GF(4). However, it is known that nonadditive 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 oneerrorcorrecting codes of length 9 and 10 have been found. So far, all these nonadditive 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 nonadditive codes from any stabilizer code. Using constructions similar to those of CSS codes, families of nonadditive quantum codes based on the binary Goethals and Preparata codes are presented. In combination with Steane's enlargement
construction, we obtain a family of nonadditive quantum codes with parameters ((2m,22^m5m+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
36462
Speaker : David Vitali (University of Camerino)
Title: Emergence of atomlightmirror entanglement inside an optical cavity
Abstract:
We propose a scheme for the realization of a hybrid, strongly quantumcorrelated system formed of an atomic ensemble surrounded by a highfinesse 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 36428
Speaker : Saikat Guha (MIT RLE)
Title: The entropy photonnumber inequality and capacity of bosonic channels
Abstract:
Determining the ultimate classical information carrying capacity of electromagnetic waves requires quantummechanical analysis to properly account for the bosonic nature of these waves. Our previous work has established capacity theorems for the bosonic singleuser 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 singleuser 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 inputstate 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 Photonnumber 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 36428
Speaker : Mohammad Amin (DWave)
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 doublewell potential. At a more microscopic level, I will present a nonMarkovian 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 36428
Speaker : Pawel Wocjan (UCF)
Title: Classical Problems Characterizing the Power of Quantum Computing
Abstract:
We construct a translation invariant finiterange interaction on a onedimensional qudit chain and prove that a singleshot 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 PromiseBQPcomplete 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 32D677 [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 resultthat observability implies stability of the nonlinear filter in a suitable senserequires 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 6C442 (ctp)
Speaker : Sahel Ashhab (RIKEN)
Title:
LandauZener crossings in quantumcomputing systems
Abstract:
I will talk about two applications of the LandauZener 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 twolevel 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 32D677 [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 resultthat observability implies stability of the nonlinear filter in a suitable senserequires 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
32D451
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 36428
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 nonabelian hidden subgroup problem rules out a promising direction. In this talk I will outline a proposal where rather than increasing complexity by moving to nonabelian groups, the challenge is to find hidden nonlinear 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 blackbox setting.
The second challenge is to exploit the strong negative results about the nonabelian hidden subgroup problem to design quantum resistant cryptographic primitives. I will outline a oneway 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 36428
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 oneway 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 36428
Speaker : Yaoyun Shi (Michigan)
Title: Quantum communication complexity of blockcomposed 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 twoparty 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 lowerbound 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 "blockcomposition'' 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 kbit block of x and y, respectively.
We show that as long as g itself is "hard'' enough, its blockcomposition 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 blockcomposition 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 26214
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 36428
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 36428
Speaker : Iordanis Kerenidis (Universite ParisSud)
Title: Quantum honest verifier statistical zeroknowledge for all interactive proofs
Abstract:
Statistical ZeroKnowledge (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 ZeroKnowledge 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 ParisSud)
Date and Time: Monday, 05.21.2007, 4:00PM
Location: Room 26214
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 representationtheoretic 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 26214
Speaker : Lorenza Viola (Dartmouth)
Title: Physical and informationtheoretic aspects of generalized entanglement
Abstract:
Generalized entanglement has recently emerged as a unifying framework capable of overcoming the limitations of standard subsystembased entanglement and of bridging to various physical and informationtheoretic 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 unentangled 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 26214
Speaker :
Itai Arad (Hebrew U, Jerusalem)
Title: Efficient quantum algorithms for an additive approximation of the Tutte polynomial and the qstate 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 qstate 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 nonunitarity, which seems counter intuitive in the quantum world. Significant contribution of this is a proof that nonunitary operators can be used for universal quantum computation.
xQIT workshops will bring together all MIT participants in
the Center along with potential industry collaborators,as well
as other Bostonarea quantum information researchers. Its primary
purpose is to harmonize the elements of our research with programs
elsewhere
and to foster collaboration.
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.
The xQIT Conference on Extreme Quantum Information Theory
May 34, 2011
The xQIT Conference on Extreme Quantum Information Theory
November 1920, 2008
