Kazan (Volga region) Federal University, KFU
KAZAN
FEDERAL UNIVERSITY
 
VERY NARROW QUANTUM OBDDS AND WIDTH HIERARCHIES FOR CLASSICAL OBDDS
Form of presentationArticles in international journals and collections
Year of publication2014
Языкрусский
  • Ablaev Farid Mansurovich, author
  • Gaynutdinova Aida Faritovna, author
  • Khadiev Kamil Ravilevich, author
  • Bibliographic description in the original language Farid Ablayev, Aida Gainutdinova, Kamil Khadiev, Abuzer Yakaryılmaz, «Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs«, LNCS vol. 8614 pp. 53-64, 2014
    Annotation In the paper we investigate a model for computing of Boolean functions ? Ordered Binary Decision Diagrams (OBDDs), which is a restricted version of Branching Programs. We present several results on the comparative complexity for several variants of OBDD models. We present some results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k + 1. We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficient than classical nondeterminism. In particular, an explicit function is presented which is computed by a quantum nondeterministic OBDD with constant width, but any classical nondeterministic OBDD for this function needs non-constant width. We also present new hierarchies on widths of determ. & nonde
    Keywords quantum computation, OBDD, nondeterminism
    The name of the journal Lecture Notes in Computer Science
    URL http://link.springer.com/chapter/10.1007/978-3-319-09704-6_6
    Please use this ID to quote from or refer to the card https://repository.kpfu.ru/eng/?p_id=84826&p_lang=2

    Full metadata record