Quantum algorithms for testing and learning Boolean functions

Dominik Floess, Anna Erika Elisabeth Andersson, Mark Hillery

Research output: Contribution to journalArticle

151 Downloads (Pure)

Abstract

We discuss quantum algorithms based on the Bernstein-Vazirani algorithm for finding which input variables a Boolean function depends on. There are 2(n) possible linear Boolean functions of n input variables; given a linear Boolean function, the Bernstein-Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. We show how the same quantum algorithm can also be used to learn which input variables any other type of Boolean function depends on. The success probability of learning that the function depends on a particular input variable depends on the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure based on another quantum algorithm, the Grover search, to amplify further the success probability. Finally, we discuss quantum algorithms for learning the exact form of certain quadratic and cubic Boolean functions.

Original languageEnglish
Pages (from-to)386-398
Number of pages13
JournalMathematical Structures in Computer Science
Volume23
Issue number2
Early online date28 Feb 2013
DOIs
Publication statusPublished - Apr 2013

Keywords

  • BOUNDS

Cite this