University of Cambridge > Talks.cam > CQIF Seminar > On Computational Power of Classical and Quantum Branching Programs

On Computational Power of Classical and Quantum Branching Programs

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity