On the complexity of computing the “Shuffled Inequality” function in classical and quantum NOBDDs

We investigate Ordered Binary Decision Diagrams (OBDDs) — a model for computing Boolean functions. It is known that OBDD’s complexity can extremely depend on the order of reading variables. There are techniques for constructing functions that do not allow choosing the optimal order for reading the input, one of which we use in this paper. A function “Shuffled Inequality” NEQS is presented, for which a lower and an upper bounds for the complexity of nondeterministic OBDD are proved. The upper bound is an improvement of a previously known result. A quantum measure-many non-deterministic OBDD is constructed that is more efficient than the classical one. The hierarchy of complexity classes defined on the basis of OBDD models is clarified.