Quantum computational algorithms for hidden subgroup problems and initialization

Hidden Subgroup Problem(HSP) seeks to identify an unknown subgroup H of a group G for a given injective function f defined on cosets of H. Here we present an initialization-free quantum algorithm for solving HSP in the case where G is a finite abelian group. Our algorithm can adopt an arbitrary unknown mixed state as the auxiliary register and removes the need for initialization while preserving computational cost comparable to existing methods. Our algorithm also restores the state of the auxiliary register to its original form after completing the computations. Since the recovered state can be utilized for other operations, a single preparation of the auxiliary register in an arbitrarily unknown mixed state is sufficient to execute the iterative procedure in solving hidden subgroup problems. This approach provides a promising direction for improving quantum algorithm efficiency by reducing operational time of initialization.Hidden Subgroup Problem(HSP) seeks to identify an unknown subgroup H of a group G for a given injective function f defined on cosets of H. Here we present an initialization-free quantum algorithm for solving HSP in the case where G is a finite abelian group. Our algorithm can adopt an arbitrary unknown mixed state as the auxiliary register and removes the need for initialization while preserving computational cost comparable to existing methods. Our algorithm also restores the state of the auxiliary register to its original form after completing the computations. Since the recovered state can be utilized for other operations, a single preparation of the auxiliary register in an arbitrarily unknown mixed state is sufficient to execute the iterative procedure in solving hidden subgroup problems. This approach provides a promising direction for improving quantum algorithm efficiency by reducing operational time of initialization.

arXiv:2507.18088Jul 24, 20250 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.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.1361Apr 7, 20113 citations

Quantum Algorithms for a Set of Group Theoretic Problems

Stephen Fenner, Yong Zhang

Lecture notes in computer scienceJan 1, 20055 citations

Quantum Algorithm for a Special Case of the Dihedral Hidden Subgroup Problem

Hachiro Fujita

Communications in computer and information scienceJan 1, 20250 citations

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.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.03295Apr 7, 20220 citations

\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.