Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




Revision #2
Authors: Airat Khasianov
Accepted on: 28th July 2010 14:34
Downloads: 918
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
Downloads: 1152
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
Downloads: 1153
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