Quantum boolean functions

Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other compatible player.

Recording Details

Scientific Areas: 
PIRSA Number: 


In recent years, the analysis of boolean functions has arisen as an important theme in theoretical computer science. In this talk I will discuss an extension of the concept of a boolean function to quantum computation. It turns out that many important classical results in the theory of boolean functions have natural quantum analogues. These include property testing of boolean functions; the Goldreich-Levin algorithm for approximately learning boolean functions; and a theorem of Friedgut, Kalai and Naor on the Fourier spectra of boolean functions. The quantum generalisation of this theorem uses a quantum extension of the hypercontractive inequality of Bonami, Gross and Beckner. This talk is based on joint work with Tobias Osborne.