Comparative complexity of quantum and classical OBDDs for total and partial functions

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...

Full description

Saved in:
Bibliographic Details
Published in:Russian mathematics 2015-11, Vol.59 (11), p.26-35
Main Author: Gainutdinova, A. F.
Format: Article
Language:English
Subjects:
Mathematics
Mathematics and Statistics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 .
ISSN:1066-369X
1934-810X
DOI:10.3103/S1066369X15110031