Interactive Shallow Clifford Circuits- Quantum Advantage Against NC and Beyond

Explore the cutting-edge research on interactive shallow Clifford circuits and their quantum advantage in this 26-minute conference talk. Delve into the Hidden Linear Function Problem and its complexity, examining upper bounds and the main results of the study. Understand the fixes implemented, including the introduction of interactive problems and the reduction for classical solutions. Analyze the impact of interactivity on classical devices and the revised theorems presented. Gain insights into Pauli errors, adversarial tomography, and the implications for smaller grids. Discover how this research contributes to the ongoing exploration of quantum computing's potential superiority over classical systems in specific computational tasks.

Intro
Title Breakdown
Previous Work
Hidden Linear Function Problem
How hard is HLF? (Upper Bound)
Complexity Class Map
Main Result
Fix 1: Interactive problem
Fix 1: Interactive Task
Fix 2: Reduction only for classical solutions
Interactivity and classical devices
Revised Theorem 2
Sketch of reduction
Pauli Errors
Adversarial Tomography
Revised Theorem 3
Weaker results on smaller grids