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

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

• Nadish de Silva, University of Cambridge
• Friday 29 November 2019, 12:00-13:00
• MR15, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

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.

This talk is included in these lists:

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

Note that ex-directory lists are not shown.