BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//RLASKEY//CALENDEROUS//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VEVENT
DTSTAMP:20260831T080403Z
LAST-MODIFIED:20121116T203436Z
DTSTART:20120224T170000Z
DTEND:20120224T180000Z
UID:event679@bu.edu
URL:http://physics.bu.edu/internal/events/show/679
SUMMARY:Statistical mechanics of classical and quantum computational comple
	xity
DESCRIPTION:Featuring Roderich Moessner\, Max Planck Institute\, Dresden\nH
	osted by: Claudio Chamon\n\nPart of the Biophysics/Condensed Matter Seminar
	 Series.\n\nAbstract:\nThe quest for quantum computers is motivated by thei
	r potential for solving problems that defy existing\, classical\, computers
	. The theory of  computational complexity provides a rigorous framewor
	k for classifying  the hardness of problems according to the computati
	onal resources\, most  notably time\, needed to solve them. Its extens
	ion to quantum computers  allows the relative power of quantum compute
	rs 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. T
	hat is\, they identify problems of comparable worst-case difficulty without
	 directly determining the individual hardness of any given instance. Statis
	tical mechanical methods can be used to complement this classification by d
	irectly extracting information about particular families of instances---typ
	ically those that involve optimization---by studying random ensembles of th
	em. These pose unusual and interesting (quantum) statistical mechanical que
	stions and the results shed light on the difficulty of problems for large c
	lasses of algorithms as well as providing a window on the contrast between 
	typical and worst case complexity. This talk presents an introduction to th
	is set of ideas with our recent work on quantum satisfiability as primary e
	xample. It also touches on the connection of computational hardness with th
	e physical notion of glassiness.  arXiv:1009.1635 <http://arxiv.org/abs/100
	9.1635>\, arXiv:0910.2058 <http://arxiv.org/abs/0910.2058>\, arXiv:0903.190
	4 <http://arxiv.org/abs/0903.1904>
LOCATION:SCI 352\, 590 Commonwealth Avenue\, 02215
STATUS:CONFIRMED
CLASS:PUBLIC
END:VEVENT
END:VCALENDAR