Quantum algorithms for testing Boolean functions

Dominik F. Floess
Erika Andersson
Mark Hillery

We discuss quantum algorithms, based on the Bernstein-Vazirani algorithm, for finding which variables a Boolean function depends on. There are 2^n possible linear Boolean functions of n 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. The same quantum algorithm can also be used to learn which input variables other types of Boolean functions depend on, with a success probability that 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 to futher amplify the success probability, based on another quantum algorithm, the Grover search.

In S. Barry Cooper, Prakash Panangaden and Elham Kashefi: Proceedings Sixth Workshop on Developments in Computational Models: Causality, Computation, and Physics (DCM 2010), Edinburgh, Scotland, 9-10th July 2010, Electronic Proceedings in Theoretical Computer Science 26, pp. 101–108.
Published: 9th June 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.26.9 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org