PIRSA:08120019 Scientific Series Quantum Information

DOI10.48660/08120019

Series: Perimeter Institute Quantum Discussions

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

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

@misc{ pirsa_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},
  year = {2008},
  month = {dec},
  note = {PIRSA:08120019 see, \url{https://pirsa.org}}
}

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.

Resources

Next talk

Related Talks