Video URL

https://pirsa.org/08120019

Quantum boolean functions

Montanaro, A. (2008). Quantum boolean functions. Perimeter Institute for Theoretical Physics. https://pirsa.org/08120019

Montanaro, Ashley. Quantum boolean functions. Perimeter Institute for Theoretical Physics, Dec. 03, 2008, https://pirsa.org/08120019 

          @misc{ scivideos_PIRSA:08120019,
            doi = {10.48660/08120019},
            url = {https://pirsa.org/08120019},
            author = {Montanaro, Ashley},
            keywords = {Quantum Information},
            language = {en},
            title = {Quantum boolean functions},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2008},
            month = {dec},
            note = {PIRSA:08120019 see, \url{https://scivideos.org/pirsa/08120019}}
          }

Ashley Montanaro University of Bristol

DOI 10.48660/08120019
Source Repository PIRSA
Collection
Talk Type Scientific Series
Subject

Abstract

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.