Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Exponential Separation between Quantum and Classical Ordered Binary
  Decision Diagrams, Reordering Method and Hierarchies   In this paper, we study quantum Ordered Binary Decision Diagrams($OBDD$)
model; it is a restricted version of read-once quantum branching programs, with
respect to "width" complexity. It is known that the maximal gap between
deterministic and quantum complexities is exponential. But there are few
examples of functions with such a gap. We present a new technique
("reordering") for proving lower bounds and upper bounds for OBDD with an
arbitrary order of input variables if we have similar bounds for the natural
order. Using this transformation, we construct a total function $REQ$ such that
the deterministic $OBDD$ complexity of it is at least $2^{\Omega(n / \log n)}$,
and the quantum $OBDD$ complexity of it is at most $O(n^2/\log n)$. It is the
biggest known gap for explicit functions not representable by $OBDD$s of a
linear width. Another function(shifted equality function) allows us to obtain a
gap $2^{\Omega(n)}$ vs $O(n^2)$.
  Moreover, we prove the bounded error quantum and probabilistic $OBDD$ width
hierarchies for complexity classes of Boolean functions. Additionally, using
"reordering" method we extend a hierarchy for read-$k$-times Ordered Binary
Decision Diagrams ($k$-$OBDD$) of polynomial width, for $k = o(n / \log^3 n)$.
We prove a similar hierarchy for bounded error probabilistic $k$-$OBDD$s of
polynomial, superpolynomial and subexponential width.
  The extended abstract of this work was presented on International
  Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June
  8 -- 12, 2017

24
The categories of this paper are: dg-ga
37
The categories of this paper are: supr-con
25
The categories of this paper are: patt-sol
11
The categories of this paper are: hep-lat
12
The categories of this paper are: nucl-th
18
The categories of this paper are: econ
30
The categories of this paper are: q-alg
35
The categories of this paper are: mtrl-th
3
The categories of this paper are: physics
29
The categories of this paper are: funct-an
27
The categories of this paper are: comp-gas
22
The categories of this paper are: chao-dyn
9
The categories of this paper are: nlin
26
The categories of this paper are: bayes-an
7
The categories of this paper are: hep-th
15
The categories of this paper are: nucl-ex