We consider the \emph{Hidden Subgroup} in the context of quantum \emph{Ordered Binary Decision Diagrams}.
We show several lower bounds for this function.
In this paper we also consider a slightly more general definition of the
hidden subgroup problem (in contrast to that in \cite{khashsp1}). It turns out that in this case
the problem is intractable for the quantum OBDD. We prove exponential lower
bounds for this function.

Some minor typos fixed.

We consider the \emph{Hidden Subgroup} in the context of quantum \emph{Ordered Binary Decision Diagrams}.
We show several lower bounds for this function.
In this paper we also consider a slightly more general definition of the
hidden subgroup problem (in contrast to that in \cite{khashsp1}). It turns out that in this case
the problem is intractable for the quantum OBDD. We prove exponential lower
bounds for this function.

The internal version of the paper was accidentally submitted as the previous revision. The lower bound proof for Disjointness sketched only. This revision presents complete lower bound proofs, corrected typos and clearer presentation.

We consider the \emph{Hidden Subgroup} in the context of quantum \emph{Ordered Binary Decision Diagrams}.
We show several lower bounds for this function.
In this paper we also consider a slightly more general definition of the
hidden subgroup problem (in contrast to that in \cite{khashsp1}). It turns out that in this case
the problem is intractable for the quantum OBDD. We prove exponential lower
bounds for this function.