Princeton Quantum Seminar
Kewen Wu, UC- Berkeley
"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.

Host: Professor Ran Raz, Professor of Computer Science