BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Quantum algorithms from foundations to application
s - Ashley Montanaro\, University of Bristol
DTSTART;TZID=Europe/London:20190531T120000
DTEND;TZID=Europe/London:20190531T130000
UID:TALK124120AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/124120
DESCRIPTION:Quantum computers are designed to use quantum mech
anics to outperform any standard\, “classical” com
puter based only on the laws of classical physics.
Following many years of experimental and theoreti
cal developments\, it is anticipated that quantum
computers will soon be built that cannot be simula
ted by today’s most powerful supercomputers. But t
o take advantage of a quantum computer requires a
quantum algorithm: and designing and applying quan
tum algorithms requires contributions to be made a
t all levels of the theoretical “stack”\, from und
erpinning mathematics through to detailed running
time analysis. In this talk\, I will describe one
example of this process. First\, an abstract quant
um algorithm due to Aleksandrs Belovs is used to s
peed up classical search algorithms based on the t
echnique known as backtracking (“trial and error”)
. Then this quantum algorithm can be applied to fu
ndamental constraint satisfaction problems such as
graph colouring\, sometimes achieving substantial
speedups over leading classical algorithms. The t
alk will aim to give a flavour of the mathematics
involved in quantum algorithm design\, rather than
going into full details.
LOCATION:MR14\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Johannes Bausch
END:VEVENT
END:VCALENDAR