Chicago Journal of Theoretical Computer Science

Volume 2010

Article 1

Published by the Department of Computer Science, The University of Chicago.

Quantum Boolean Functions

Ashley Montanaro
Department of Computer Science.
University of Bristol
Woodland Road, Bristol BS8 1UB UK

Tobias J. Osborne
Department of Mathematics
Royal Holloway, University of London
Egham TW20 0EX UK

Jan 13, 2010

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.

DOI: 10.4086/cjtcs.2010.001

[] Volume 2009, Article 3
[back] Volume 2009 [back] Published articles
[CJCTS home]