Classical lower bounds from quantum upper bounds

Shalev Ben-David, Adam Bouland, Ankit Garg +1

We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove t…