On the Need for Large Quantum Depth

Explore the intricacies of quantum computing depth in this 22-minute ACM conference talk. Delve into Google's claims of quantum supremacy and examine the necessity for small circuit depths in near-term quantum computing. Investigate the relationship between log(n)-depth quantum circuits combined with classical computing and their equivalence to poly(n)-depth circuits. Learn about oracle problems in the quantum circuit model and understand the design process for such problems. Discover why Simon's Problem is surprisingly manageable for constant-depth quantum circuits paired with classical computing. Analyze the d-Shuffling Simon's Problem (d-SSP) and its implications. Conclude with a discussion on open problems and future directions in the field of quantum computing depth.

Syllabus

Intro
Google claims 'quantum supremacy for computer
Near-term QC Must Have Small Circuit Depth
Log(n)-depth QC + Classical C = Poly(n)-depth
Facts and Conjectures
What Is An Oracles Problem?
Quantum Circuit Model with Oracle
Design The Oracle Problem
Simon's Problem is Actually Easy for constant-depth QC + classical C
The d-Shuffling Simon's Problem (d-SSP)
Discussion and Open Problems