  In this paper we introduce the study of quantum boolean functions, which are
unitary operators f whose square is the identity: f^2 = I. 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.
