Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #2 to TR10-030 | 28th July 2010 14:34

Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem

Revision #2
Authors: Airat Khasianov
Accepted on: 28th July 2010 14:34
Keywords:

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

Revision #1
Authors: Airat Khasianov
Accepted on: 5th March 2010 07:18
Keywords:

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

TR10-030
Authors: Airat Khasianov
Publication: 4th March 2010 14:05
Keywords:

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.

ISSN 1433-8092 | Imprint