University of Cambridge > Talks.cam > CQIF Seminar > Quantum advantage with shallow circuits (Bravyi-Gosset-König)

Quantum advantage with shallow circuits (Bravyi-Gosset-König)

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

If you have a question about this talk, please contact Sathyawageeswar Subramanian.

Rigorously separating classical and quantum computational power is a central problem of quantum computer science.  Known results tend to rely on the use of oracles or unproven complexity-theoretic assumptions.  In contrast, BGK prove an unconditional separation between the power of constant-depth classical and quantum circuits to solve a certain problem.  Their proof exploits the logical structure of nonlocal games.  

This seminar talk aims to give a self-contained and accessible overview of their proof; it is based on https://arxiv.org/abs/1704.00690 (Science, 2018) and https://arxiv.org/abs/1904.01502.

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-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity