Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic colloquium on computational complexity

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

Airat Khasianov

Published Jan 1, 2010• 0 citations
OpenAlex

Abstract

We consider the Hidden Subgroup in the context of quantum 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 [KH10]). It turns out that in this case the problem is intractable for the quantum OBDD. We prove exponential lower bounds for this function.

Related papers

On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

Farid Mansurovich Ablayev, Airat Khasianov, Alexander Vasiliev

We consider the Hidden Subgroup, and Equality-related problems in the context of quantum Ordered Binary Decision Diagrams. For the decision versions of considered problems we show polynomial upper bounds in terms of quantum OBDD width. We apply a new modification of the fingerprinting technique and present the algorithms in circuit notation. Our algorithms require at most logarithmic number of qubits. 1

Electronic colloquium on computational complexity•Jan 1, 2008•11 citations

COMPLEXITY BOUNDS ON SOME FUNDAMENTAL COMPUTATIONAL PROBLEMS FOR QUANTUM BRANCHING PROGRAMS

Airat Khasianov

We study quantum computational complexity of several problems connected to the Hidden Subgroup Problem. This problem drew substantial attention when a polynomial time quantum algorithm for it was found. The algorithm generalized the quantum algorithms for factoring integers and finding discrete logarithms. We consider the the problems in the context of quantum ordered read-once decision diagrams. Our presentation starts with some fundamental functions related to the Hidden Subgroup Problem. These functions include Equality, Periodicity and simplified "Simon". We show linear upper and lower bounds on the width of quantum OBDD representations of these functions. In the second part of the research we show upper and lower bounds for the Hidden Subgroup Test.

•Jan 1, 2005•3 citations

ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM

Stephen Fenner, Yong Zhang

We study the computational complexity of the HIDDEN SUBGROUP problem, a well-studied problem in quantum computing. First we show that several proposed generalizations or variants of this problem, including HIDDEN COSET, HIDDEN SHIFT, and ORBIT COSET, are all equivalent or reducible to HIDDEN SUBGROUP. Then we study the relationship between the decision version and search version of HIDDEN SUBGROUP over various group classes. We show that the two versions are polynomial-time equivalent over permutation groups, and over dihedral groups given the order of the group is smooth. Finally, we give nonadaptive program checkers for HIDDEN SUBGROUP and its decision version.

International Journal of Foundations of Computer Science•Dec 1, 2013•2 citations

The central nature of the Hidden Subgroup problem

Stephen Fenner, Yong Zhang

We show that several problems that figure prominently in quantum computing, including Hidden Coset, Hidden Shift, and Orbit Coset, are equivalent or reducible to Hidden Subgroup for a large variety of groups. We also show that, over permutation groups, the decision version and search version of Hidden Subgroup are polynomial-time equivalent. For Hidden Subgroup over dihedral groups, such an equivalence can be obtained if the order of the group is smooth. Finally, we give nonadaptive program checkers for Hidden Subgroup and its decision version.

arXiv:cs/0610086•Oct 13, 2006•2 citations

Quantum solution to the hidden subgroup problem for Poly-Near-Hamiltonian groups

Dmitry Gavinsky

The Hidden Subgroup Problem (HSP) has been widely studied in the context of quantum computing and is known to be efficiently solvable for Abelian groups, yet appears to be difficult for many non-Abelian ones. An efficient algorithm for the HSP over a group \f G\ runs in time polynomial in \f{n\deq\log|G|.} For any subgroup \f H\ of \f G, let \f{N(H)} denote the normalizer of \f H. Let \MG\ denote the intersection of all normalizers in \f G (i.e., \f{\MG=\cap_{H\leq G}N(H)}). \MG\ is always a subgroup of \f G and the index \f{[G:\MG]} can be taken as a measure of ``how non-Abelian'' \f G is (\f{[G:\MG] = 1} for Abelian groups). This measure was considered by Grigni, Schulman, Vazirani and Vazirani, who showed that whenever \f{[G:\MG]\in\exp(O(\log^{1/2}n))} the corresponding HSP can be solved efficiently (under certain assumptions). We show that whenever \f{[G:\MG]\in\poly(n)} the corresponding HSP can be solved efficiently, under the same assumptions (actually, we solve a slightly more general case of the HSP and also show that some assumptions may be relaxed).

Quantum Information and Computation•May 1, 2004•28 citations

Quantum and classical nondeterministic OBDDs

Aida Gainutdinova

A model of nondeterministic ordered binary decision diagrams (NOBDDs) was analyzed. A method for proving a lower bound on the complexity of quantum NOBDDs was developed. Two functions were introduced: one function has linear complexity in the quantum NOBDD but constant complexity in the classical NOBDD, while the other function demonstrates the same complexity in both quantum and classical NOBDD models. The relationships among the complexity classes specific to the OBDD model were described.

Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki•Dec 22, 2024•1 citation
We consider the Hidden Subgroup in the context of quantum 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 [KH10]). It turns out that in this case the problem is intractable for the quantum OBDD. We prove exponential lower bounds for this function.
We study quantum computational complexity of several problems connected to the Hidden Subgroup Problem. This problem drew substantial attention when a polynomial time quantum algorithm for it was found. The algorithm generalized the quantum algorithms for factoring integers and finding discrete logarithms. We consider the the problems in the context of quantum ordered read-once decision diagrams. Our presentation starts with some fundamental functions related to the Hidden Subgroup Problem. These functions include Equality, Periodicity and simplified "Simon". We show linear upper and lower bounds on the width of quantum OBDD representations of these functions. In the second part of the research we show upper and lower bounds for the Hidden Subgroup Test.
We study the computational complexity of the HIDDEN SUBGROUP problem, a well-studied problem in quantum computing. First we show that several proposed generalizations or variants of this problem, including HIDDEN COSET, HIDDEN SHIFT, and ORBIT COSET, are all equivalent or reducible to HIDDEN SUBGROUP. Then we study the relationship between the decision version and search version of HIDDEN SUBGROUP over various group classes. We show that the two versions are polynomial-time equivalent over permutation groups, and over dihedral groups given the order of the group is smooth. Finally, we give nonadaptive program checkers for HIDDEN SUBGROUP and its decision version.
We show that several problems that figure prominently in quantum computing, including Hidden Coset, Hidden Shift, and Orbit Coset, are equivalent or reducible to Hidden Subgroup for a large variety of groups. We also show that, over permutation groups, the decision version and search version of Hidden Subgroup are polynomial-time equivalent. For Hidden Subgroup over dihedral groups, such an equivalence can be obtained if the order of the group is smooth. Finally, we give nonadaptive program checkers for Hidden Subgroup and its decision version.
The Hidden Subgroup Problem (HSP) has been widely studied in the context of quantum computing and is known to be efficiently solvable for Abelian groups, yet appears to be difficult for many non-Abelian ones. An efficient algorithm for the HSP over a group \f G\ runs in time polynomial in \f{n\deq\log|G|.} For any subgroup \f H\ of \f G, let \f{N(H)} denote the normalizer of \f H. Let \MG\ denote the intersection of all normalizers in \f G (i.e., \f{\MG=\cap_{H\leq G}N(H)}). \MG\ is always a subgroup of \f G and the index \f{[G:\MG]} can be taken as a measure of ``how non-Abelian'' \f G is (\f{[G:\MG] = 1} for Abelian groups). This measure was considered by Grigni, Schulman, Vazirani and Vazirani, who showed that whenever \f{[G:\MG]\in\exp(O(\log^{1/2}n))} the corresponding HSP can be solved efficiently (under certain assumptions). We show that whenever \f{[G:\MG]\in\poly(n)} the corresponding HSP can be solved efficiently, under the same assumptions (actually, we solve a slightly more general case of the HSP and also show that some assumptions may be relaxed).