Published by the Department of Computer Science, The University of Chicago.
In this paper we introduce the study of quantum boolean
functions, which are unitary operators f whose square is the
identity. We describe several generalisations of
well-known results in the theory of boolean functions, including
quantum property testing; a quantum version of the Goldreich-Levin
algorithm for finding the large Fourier coefficients of boolean
functions; and two quantum versions of a theorem of Friedgut, Kalai
and Naor on the Fourier spectra of boolean functions. In order to
obtain one of these generalisations, we prove a quantum extension of
the hypercontractive inequality of Bonami, Gross and Beckner.
Submitted March 6 2009, revised version submitted January 12 2010, published January 13, 2010.