Algorithms for Quantum Branching Programs Based on Fingerprinting
    Download PDF
Farid Ablayev,Alexander Vasiliev. Algorithms for Quantum Branching Programs Based on Fingerprinting. International Journal of Software and Informatics, 2013,7(4):485~500
Hits: 2466
Download times: 1424
Fund:This work is sponsored by Russian Foundation for Basic Research under Grants 09-01-97004 and 11-07-00465.
Abstract: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 ˉngerprinting 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 MODm, EQn, Palindromen, and PERMn (testing whether given Boolean matrix is the Permutation Matrix). We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.
keywords:quantum informatics  quantum branching programs  QOBDD  fingerprinting  characteristic polynomials
View Full Text  View/Add Comment  Download reader



Top Paper  |  FAQ  |  Guest Editors  |  Email Alert  |  Links  |  Copyright  |  Contact Us

© Copyright by Institute of Software, the Chinese Academy of Sciences
ICP: Jing ICP Bei No.10016592

京公网安备 11040202500065号