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

International Conference on Quantum, Nano and Micro Technologies (ICQNM)

The Hidden Subgroup Problem for Generalized Quaternions

Julia Tumasova Upton

Published Feb 1, 2010• 1 citation
Publisher

Abstract

The hidden subgroup problem is a pivotal problem in quantum computation since it reflects the structure of tasks for which quantum algorithms significantly outperform classical algorithms. In this paper, a quantum algorithm that solves the hidden subgroup problem over the generalized quaternion group is developed. The algorithm employs the abelian quantum Fourier transform and Kuperberg sieve to reveal the hidden subgroup.

DOI
10.1109/icqnm.2010.23

Related papers

The hidden subgroup problem for generalized quaternions

Julia Tumasova Upton

The hidden subgroup problem is a pivotal problem in quantum computation since it reflects the structure of tasks for which quantum algorithms significantly outperform classical algorithms. In this dissertation, a quantum algorithm that solves the hidden subgroup problem over the generalized quaternion group is developed. The algorithm employs the abelian quantum Fourier transform and Kuperberg sieve to reveal the hidden subgroup. (Published By University of Alabama Libraries)

•Jan 1, 2009•0 citations

Solution to the Hidden Subgroup Problem for a Class of Noncommutative Groups

Demerson Nunes Gonçalves, Renato Portugal

The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms can be casted in the HSP structure. In this paper, we present a new polynomial-time quantum algorithm that solves the HSP over the group $\Z_{p^r} \rtimes \Z_{q^s}$, when $p^r/q= \up{poly}(\log p^r)$, where $p$, $q$ are any odd prime numbers and $r, s$ are any positive integers. To find the hidden subgroup, our algorithm uses the abelian quantum Fourier transform and a reduction procedure that simplifies the problem to find cyclic subgroups.

arXiv:1104.1361•Apr 7, 2011•3 citations

Hidden subgroup problem in quantum computing

Shuhong Gao, Prasit Limbupasiriporn

We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups. We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture. For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem. In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.

•Jan 1, 2005•0 citations

The Hidden Subgroup Problem and Quantum Computation Using Group Representations

Sean Hallgren, Alexander C. Russell, Amnon Ta‐Shma

The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.

SIAM Journal on Computing•Jan 1, 2003•105 citations

An exact quantum hidden subgroup algorithm and applications to solvable groups

Muhammad Imran, Gábor Ivanyos

We present a polynomial time exact quantum algorithm for the hidden subgroup problem in $\Z_{m^k}^n$. The algorithm uses the quantum Fourier transform modulo $m$ and does not require factorization of $m$. For smooth $m$, i.e., when the prime factors of $m$ are of size $(\log m)^{O(1)}$, the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general $m$, the algorithm of Mosca and Zalka is available. Even for $m=3$ and $k=1$ our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as $m$. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.

arXiv:2202.04047•Quantum Information and Computation•May 30, 2022•1 citation

Polynomial-time quantum algorithm for solving the hidden subgroup problem

Hefeng Wang

The hidden subgroup problem~(HSP) is one of the most important problems in quantum computation. Many problems for which quantum algorithm achieves exponential speedup over its classical counterparts can be reduced to the Abelian HSP. However, there is no efficient quantum algorithm for solving the non-Abelian HSP. We find that the HSP can be reduced to a nested structured search problem that is solved efficiently by using a quantum algorithm via multistep quantum computation. Then we solve the HSP and problems that can be reduced to both the Abelian and the non-Abelian HSP in polynomial time by using this algorithm.

arXiv:2204.03295•Apr 7, 2022•0 citations
The hidden subgroup problem is a pivotal problem in quantum computation since it reflects the structure of tasks for which quantum algorithms significantly outperform classical algorithms. In this paper, a quantum algorithm that solves the hidden subgroup problem over the generalized quaternion group is developed. The algorithm employs the abelian quantum Fourier transform and Kuperberg sieve to reveal the hidden subgroup.
The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms can be casted in the HSP structure. In this paper, we present a new polynomial-time quantum algorithm that solves the HSP over the group Zpr⋊Zqs\Z_{p^r} \rtimes \Z_{q^s}Zpr​⋊Zqs​, when $p^r/q= \up{poly}(\log p^r)$, where ppp, qqq are any odd prime numbers and r,sr, sr,s are any positive integers. To find the hidden subgroup, our algorithm uses the abelian quantum Fourier transform and a reduction procedure that simplifies the problem to find cyclic subgroups.
We study quantum algorithms for the hidden subgroup problem (HSP). The HSP provides a unified framework for many important problems, including factoring integers, graph isomorphism problem, etc. It has been known that the problem for abelian groups can be efficiently solved. However, for non-abelian groups, it remains widely open. In this dissertation we study the problem for some specific non-abelian groups, called q-hedral groups. We start with a quantum algorithm, proposed by Moore et al. (2003), for finding some hidden conjugate subgroups of affine groups, a special case of q-hedral groups for large q. We then adapt their algorithm to construct an algorithm for solving the hidden conjugate problem for q-hedral groups for large q and point out a difficulty in complexity analysis that involves certain exponential sums. We discuss certain bounds on these sums and present some computational data on their values to make a conjecture. For small q, Regev (2003) gave an efficient algorithm for solving the HSP for dihedral groups (q = 2) using an oracle that solves a certain subset sum problem (SSP). A crucial step of his algorithm relies on the probability that elements in a cyclic group ZN can be expressed as sums of random elements in the group. We generalize this problem to any finite group and prove the following theorem: for any finite group G and r ≥ 32 log2 |G| + 5, if r elements from G are chosen randomly, then the 2r possible sums (or products) of the r elements will cover all the elements in G with high probability. Also, by making a further generalization of the SSP, we show that Regev's algorithm can be generalized for q-hedral groups for any fixed q. We also study this generalized subset sum problem. In addition to the algorithm developing for small q, we give an efficient quantum algorithm for solving the coset problem and an efficient quantum algorithm for solving the hidden conjugate problem. Furthermore, we also give a survey of an algorithm for finding the largest normal subgroup in a hidden subgroup of any finite group, introduced by Hallgren et al. (2000) and provide a simplified and unified proof.
The hidden subgroup problem is the foundation of many quantum algorithms. An efficient solution is known for the problem over abelian groups, employed by both Simon's algorithm and Shor's factoring and discrete log algorithms. The nonabelian case, however, remains open; an efficient solution would give rise to an efficient quantum algorithm for graph isomorphism. We fully analyze a natural generalization of the algorithm for the abelian case to the nonabelian case and show that the algorithm determines the normal core of a hidden subgroup: in particular, normal subgroups can be determined. We show, however, that this immediate generalization of the abelian algorithm does not efficiently solve graph isomorphism.
We present a polynomial time exact quantum algorithm for the hidden subgroup problem in Zmkn\Z_{m^k}^nZmkn​. The algorithm uses the quantum Fourier transform modulo mmm and does not require factorization of mmm. For smooth mmm, i.e., when the prime factors of mmm are of size (log⁡m)O(1)(\log m)^{O(1)}(logm)O(1), the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general mmm, the algorithm of Mosca and Zalka is available. Even for m=3m=3m=3 and k=1k=1k=1 our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as mmm. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.
The hidden subgroup problem~(HSP) is one of the most important problems in quantum computation. Many problems for which quantum algorithm achieves exponential speedup over its classical counterparts can be reduced to the Abelian HSP. However, there is no efficient quantum algorithm for solving the non-Abelian HSP. We find that the HSP can be reduced to a nested structured search problem that is solved efficiently by using a quantum algorithm via multistep quantum computation. Then we solve the HSP and problems that can be reduced to both the Abelian and the non-Abelian HSP in polynomial time by using this algorithm.