Dear Friends,
On Thursday, April 18, there will be an ITAMP topical lunch discussion.
Tea Room (P-226) @ CfA (60 Garden Street)
Time: 12:00-1:30
As always pizza will be served.
Speaker: Chris Laumann
Title: The hardness of approximating quantum optimization problems
Abstract:
The quest for quantum computers is motivated by their potential for solving
problems that defy existing, classical, computers. The theory of
computational complexity provides a rigorous framework for classifying the
hardness of problems according to the computational resources, most notably
time, needed to solve them. Its extension to quantum computers allows the
relative power of quantum computers to be analyzed. This framework
identifies families of problems which are likely hard for classical
computers (“NP-complete”) and those which are likely hard for quantum
computers (“QMA-complete”) by indirect methods. That is, they identify
problems of comparable worst-case difficulty without directly determining
the individual hardness of any given instance. Statistical mechanical
methods can be used to complement this classification by directly
extracting information about particular families of instances by studying
random ensembles of them. These pose unusual and interesting (quantum)
statistical mechanical questions and the results shed light on the
difficulty of problems for large classes of algorithms as well as providing
a window on the contrast between typical and worst case complexity.
In this lunch talk, I will provide a brief background tour of the theory of
computational complexity and its extension to quantum computers with
reference to the quantum satisfiability problem. I will also introduce some
of the related notions of 'hard' free energy landscapes in spin glasses and
how they apply to ensembles of typical optimization problems. This will
lead us to a study of the phase diagram of quantum satisfiability where we
will find transitions between classically easy, classically hard and
intrinsically quantum phases as a function of clause and energy density.
Looking forward to seeing you there,
Misha Lemeshko
--
Dr. Mikhail Lemeshko
Institute for Theoretical Atomic, Molecular, and Optical Physics (ITAMP)
Harvard-Smithsonian Center for Astrophysics MS-14
60 Garden St.
Cambridge, MA 02138
U.S.A.
mlemeshko(a)cfa.harvard.edu
http://sites.google.com/site/mishalemeshko/
Tel. +1 (617) 496-7610
Fax +1 (617) 496-7668