42 min listen
004: Shallow quantum circuits with David Gosset
004: Shallow quantum circuits with David Gosset
ratings:
Length:
74 minutes
Released:
Jul 25, 2021
Format:
Podcast episode
Description
The point of building quantum computers is that we expect them to be capable of things that classical computers aren't. But how can we prove that this is the case? In this episode we talk to David Gosset, a professor at the University of Waterloo, about his research on quantum advantage for shallow circuits. Hosts: Vincent Russo (vprusso.github.io), William Slofstra (elliptic.space), Henry Yuen (henryyuen.net) Main papers discussed in this episode: 1) Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science Vol. 362, Issue 6412, pp. 308-311 (2018). https://doi.org/10.1126/science.aar3106 2) Sergey Bravyi, David Gosset, Robert König and Marco Tomamichel. Quantum advantage with noisy shallow circuits. Nat. Phys. 16, pp. 1040–1045 (2020). https://doi.org/10.1038/s41567-020-0948-z 3) Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. STOC 2019, pp. 515-526. https://doi.org/10.1145/3313276.3316404 4) Daniel Grier and Luke Schaeffer. Interactive shallow Clifford circuits: quantum advantage against NC1 and beyond. STOC 2020, pp. 875-888. https://doi.org/10.1145/3357713.3384332 5) David Gosset, Daniel Grier, Alex Kerzner, and Luke Schaeffer. Fast simulation of planar Clifford circuits. https://arxiv.org/abs/2009.03218 William got the citation to (1) slightly wrong in the episode: it appeared as an invited short talk at STOC, not in the proceedings. Theme music is WLIIAW by Vincent Russo.
Released:
Jul 25, 2021
Format:
Podcast episode
Titles in the series (4)
001: The origin of the Mermin-Peres magic square: The Mermin-Peres magic square is a simple game which is at the heart of many results in quantum cryptography and quantum complexity theory. In this episode, we trace the origin of the Mermin-Peres square back to two short papers by N. David Mermin and... by Nonlocal: a quantum computing podcast