Title: Quantum advantage, security, and cost, by Boolean function analysis

Abstract: Using tools from Boolean function analysis, we address questions regarding quantum advantage, security, and cost: 

(Advantage) We establish unconditional quantum advantages over classical computation in the query and communication models. 

(Security) We prove sharp security bounds for cryptographic salting, a natural heuristic to prevent classical/quantum attacks with pre-processing. 

(Cost) We obtain optimal T-cost in Clifford+T circuits for constructing quantum states and batches of small quantum gates.