Title: Quantum algorithms for highly non-linear Boolean functions
Speaker: Martin Roetteler, NEC Laboratories
Date: Wednesday, April 21, 2010 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We provide new examples for exponential separations between quantum and classical query complexity by considering hidden shift problems over families of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time and with a polynomial number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms.
Based on a SODA'10 paper. See also http://arxiv.org/abs/0811.3208