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.
See also http://arxiv.org/abs/0811.3208

This talk is part of the MITACS QIP Seminar Series http://www.iqis.org/mitacs-qip/Seminars.htm