### Revision(s):

__
Revision #2 to TR10-030 | 28th July 2010 14:34
__
#### Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem

**Abstract:**
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.

**Changes to previous version:**
Some minor typos fixed.

__
Revision #1 to TR10-030 | 5th March 2010 07:18
__
#### Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem

**Abstract:**
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.

**Changes to previous version:**
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.

### Paper:

__
TR10-030 | 18th February 2010 15:24
__

#### Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem

**Abstract:**
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.