Journal
RUSSIAN MATHEMATICS
Volume 59, Issue 11, Pages 26-35Publisher
PLEIADES PUBLISHING INC
DOI: 10.3103/S1066369X15110031
Keywords
ordered binary decision diagrams; partial functions; quantum computation; non-determinism; probabilistic OBDDs; complexity
Categories
Funding
- Russian Foundation for Basic Research [14-07-00878]
Ask authors/readers for more resources
We consider a model of computation for discrete functions-Ordered Binary Decision Diagrams (OBDD). We investigate comparative complexity of quantum, deterministic, probabilistic and nondeterministic (quantum and classical) OBDDs for total and partial functions. The measure of complexity is a width of OBDD. It is known that for total functions bounded error quantum OBDDs can be exponentially more effective than deterministic and bounded error probabilistic OBDDs. We show that such quantum OBDDs also can be exponentially more effective than nondeterministic OBDDs (both quantum and classical). For partial functions the gap can be more significant. For partial function depending on a parameter k exact quantum OBDD has the width two. Deterministic and bounded error probabilistic OBDD for this function must have a width exponentially depending on k.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available