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:On Computational Power of Classical and Quantum Br
anching Programs - Farid Ablayev (University of Ka
zan)
DTSTART;TZID=Europe/London:20110512T141500
DTEND;TZID=Europe/London:20110512T151500
UID:TALK31020AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/31020
DESCRIPTION:The model of Branching programs (BPs) is a well-kn
own circuit model of computation for computing Boo
lean functions. \n\nIn this talk\, I will review t
he results of the last decade on comparative compu
tational power of classical and quantum read-once
BPs and present algebraic and circuit representati
on of classical and quantum BPs. \nAlgebraic repre
sentation is adequate for proving lower bounds f
or quantum BPs complexity. Circuit representation
is convenient for explicit description of quantum
algorithms for Boolean functions. \nThis talk is
based on the paper (co-authored with Alexander Vas
iliev) entitled On Computational Power of Quantum
Read-Once Branching Programs (arXiv:1103.2268) and
earlier results cited in that paper.
LOCATION:MR4\, Centre for Mathematical Sciences
CONTACT:Ashley Montanaro
END:VEVENT
END:VCALENDAR