Algorithms for Quantum Branching Programs Based on Fingerprinting

Farid Ablayev
Alexander Vasiliev

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.

In S. Barry Cooper and Vincent Danos: Proceedings Fifth Workshop on Developments in Computational Models — Computational Models From Nature (DCM 2009), Rhodes, Greece, 11th July 2009, Electronic Proceedings in Theoretical Computer Science 9, pp. 1–11.
Published: 15th November 2009.

ArXived at: bibtex PDF

Comments and questions to:
For website issues: