Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

Daniel Grier, Daniel M. Kane, Jackson Morris +2

We construct a family of distributions $\{{\mathcal{D}}_n{\}}_n$ with ${\mathcal{D}}_n$ over $\{0,1{\}}^n$ and a family of depth-$7$ quantum circuits $\{C_n{\}}_n$ such that ${\mathcal{D}}_n$…