q-2018-05-22-65.pdf

verify 14 1 Introduction 2 Preliminaries: Anticoncentration and quantum speedups 3 Anticoncentration of circuit-based schemes 3.1 Anticoncentration of unitary 2-designs 3.2 Applications: a “recipe” for quantum speedups 4 Anticoncentration of…