BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:On Computational Power of Classical and Quantum Branching Programs
  - Farid Ablayev (University of Kazan)
DTSTART:20110512T131500Z
DTEND:20110512T141500Z
UID:TALK31020@talks.cam.ac.uk
CONTACT:Ashley Montanaro
DESCRIPTION:The model of Branching programs (BPs) is a well-known circuit 
 model of computation for computing Boolean functions. \n\nIn this talk\, I
  will review the results of the last decade on comparative computational p
 ower of classical and quantum read-once BPs and present algebraic and circ
 uit representation of classical and quantum BPs. \nAlgebraic representatio
 n is adequate  for proving  lower bounds for quantum BPs complexity. Circu
 it representation is convenient for explicit description of quantum algori
 thms for Boolean functions.  \nThis talk is based on the paper (co-authore
 d with Alexander Vasiliev) entitled On Computational Power of Quantum Read
 -Once Branching Programs (arXiv:1103.2268) and earlier results cited in th
 at paper.
LOCATION:MR4\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR