Quantum algorithms for testing Boolean functions

Details Quantum algorithms for testing Boolean functions Quantum algorithms for testing Boolean functions

2010-06-08

arxiv.org/abs/1006.1423v1

EPTCS 26, 2010, pp. 101-108

Physics

Quantum Physics

Scientific paper

10.4204/EPTCS.26.9

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.

Affiliated with

Also associated with

No associations

Rating

Quantum algorithms for testing Boolean functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum algorithms for testing Boolean functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum algorithms for testing Boolean functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-29411