On Computational Power of Classical and Quantum Branching Programs

Add to your list(s) Download to your calendar using vCal

• Farid Ablayev (University of Kazan)
• Thursday 12 May 2011, 14:15-15:15
• MR4, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Ashley Montanaro.

The model of Branching programs (BPs) is a well-known circuit model of computation for computing Boolean functions.

In this talk, I will review the results of the last decade on comparative computational power of classical and quantum read-once BPs and present algebraic and circuit representation of classical and quantum BPs. Algebraic representation is adequate for proving lower bounds for quantum BPs complexity. Circuit representation is convenient for explicit description of quantum algorithms for Boolean functions. This talk is based on the paper (co-authored with Alexander Vasiliev) entitled On Computational Power of Quantum Read-Once Branching Programs (arXiv:1103.2268) and earlier results cited in that paper.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR4, Centre for Mathematical Sciences
• bld31

Note that ex-directory lists are not shown.