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

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

On Computational Power of Classical and Quantum Branching Programs

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Perham Seminar Room, Sanger Building Carving object representation at it’s multi-level joints State of Exception, Spaces of Terror: The Concentrationary Gothic and Whiteness as Spectral Terrorist

Other talks

TBC Title TBC Genomic Medicine CPC Title to be confirmed Tea and Coffee Break Talk title TBC
 

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