Very narrow quantum OBDDs and width hierarchies for classical OBDDs

Resumo

In the paper we investigate Ordered Binary Decision Diagrams (OBDDs)–a model for computing Boolean functions. We present a series of results on the comparative complexity for several variants of OBDDmodels.

• We present 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 nondeterminismcan bemore efficient than classical nondeterminism. In particular, an explicit function is presented that is computed by a quantum nondeterministic OBDD of constant width but any classical nondeterministic OBDD for this function needs non-constant width.

• We also present new hierarchies on widths of deterministic and nondeterministic OBDDs.