In the paper we develop a method for constructing quantum
algorithms for computing Boolean functions by quantum ordered
read-once branching programs (quantum OBDDs). Our method is based on
fingerprinting technique and representation of Boolean functions by
their characteristic polynomials. We use circuit notation for
branching programs for desired algorithms presentation. For several
known functions our approach provides optimal
QOBDDs. Namely we consider such functions as Equality,
Palindrome, and Permutation Matrix Test. We also propose a generalization of our
method and apply it to the Boolean variant of the Hidden Subgroup Problem. |