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

arXiv:quant-ph/0507190 · Symposium on Discrete Algorithms

Quantum algorithm for a generalized hidden shift problem

Andrew M. Childs, Wim van Dam

Published Jul 19, 2005• 42 citations
arXivHTMLPDF

Abstract

Consider the following generalized hidden shift problem: given a function f on {0,...,M-1} x Z_N satisfying f(b,x)=f(b+1,x+s) for b=0,1,...,M-2, find the unknown shift s in Z_N. For M=N, this problem is an instance of the abelian hidden subgroup problem, which can be solved efficiently on a quantum computer, whereas for M=2, it is equivalent to the dihedral hidden subgroup problem, for which no efficient algorithm is known. For any fixed positive epsilon, we give an efficient (i.e., poly(log N)) quantum algorithm for this problem provided M > N^epsilon. The algorithm is based on the "pretty good measurement" and uses H. Lenstra's (classical) algorithm for integer programming as a subroutine.

DOI
10.48550/arxiv.quant-ph/0507190

Related papers

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

A hidden shift quantum algorithm

Jason Twamley

We examine the application of quantum algorithms to the non-Abelian hidden subgroup problem and focus on the dihedral hidden subgroup problem (DHSP). Ettinger and Høyer have recently discovered an algorithm which, although efficient in the number of operations of the quantum computation, requires classical post-processing which grows exponentially with the size of the input. We first show that the DHSP can be reduced to another problem: how to efficiently estimate an unknown shift k , in a one-to-one map f : M → M , given two oracles which provide x → f ( x ), and x → f ( x ⊕ k ), with k and f unknown. We devise an algorithm which uses amplitude amplification to obtain an estimate for the unknown shift k in a number (( M ) 1/2 ) oracle calls.

Journal of Physics A Mathematical and General•Nov 24, 2000•5 citations

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over some Non-Abelian Groups

Demerson Nunes Gonçalves, Renato Portugal, Tharso D. Fernandes

The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms are special cases of the HSP. In this paper we show that there exist a new efficient quantum algorithm for the HSP on groups ZN o Zqs where N is an integer with a special prime factorization.

Proceeding Series of the Brazilian Society of Computational and Applied Mathematics•Nov 18, 2015•0 citations

Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups

Martin Roetteler

Difference sets are basic combinatorial structures that have applications in signal processing, coding theory, and cryptography. We consider the problem of identifying a shifted version of the characteristic function of a (known) difference set. We present a generic quantum algorithm that can be used to tackle any hidden shift problem for any difference set in any abelian group. We discuss special cases of this framework where the resulting quantum algorithm is efficient. This includes: a) Paley difference sets based on quadratic residues in finite fields, which allows to recover the shifted Legendre function quantum algorithm, b) Hadamard difference sets, which allows to recover the shifted bent function quantum algorithm, and c) Singer difference sets based on finite geometries. The latter class allows us to define instances of the dihedral hidden subgroup problem that can be efficiently solved on a quantum computer.

arXiv:1608.02005•Aug 5, 2016•4 citations

A new quantum algorithm for the hidden shift problem in $\mathbb{Z}_{2^t}^n$

Gergely Csáji

In this paper we make a step towards a time and space efficient algorithm for the hidden shift problem for groups of the form $\mathbb{Z}_k^n$. We give a solution to the case when $k$ is a power of 2, which has polynomial running time in $n$, and only uses quadratic classical, and linear quantum space in $n\log (k)$. It can be a useful tool in the general case of the hidden shift and hidden subgroup problems too, since one of the main algorithms made to solve them can use this algorithm as a subroutine in its recursive steps, making it more efficient in some instances.

arXiv:2102.04171•Feb 8, 2021•1 citation

The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups

Mauro E. S. Morales

Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively. In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form $G=A\rtimes_{\varphi} \mathbb{Z}_{p^k}$, with $A$ finite Abelian, $p$ prime, $k\in \mathbb{N}$ and the action of $\mathbb Z_{p^k}$ is generated by the scalar automorphism $a\mapstoμa$, for some $μ\in\mathbb Z_{\operatorname{Exp}(A)}^\times$, where $\mathrm{Exp}(A)$ is the exponent of $A$. Our algorithm is efficient when $A$ has bounded generator rank and $\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)$. This includes the case $A=\mathbb{Z}_N$ for $N\in\mathbb{N}$ and $k=1$, studied by Bacon, Childs and van Dam (FOCS 2005), and $A=\mathbb{Z}_{q^r}$ with $q$ prime and $r\in \mathbb{N}$ studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).

quant-pharXiv:2608.05321•Aug 7, 2026•0 citations
Consider the following generalized hidden shift problem: given a function f on {0,...,M-1} x Z_N satisfying f(b,x)=f(b+1,x+s) for b=0,1,...,M-2, find the unknown shift s in Z_N. For M=N, this problem is an instance of the abelian hidden subgroup problem, which can be solved efficiently on a quantum computer, whereas for M=2, it is equivalent to the dihedral hidden subgroup problem, for which no efficient algorithm is known. For any fixed positive epsilon, we give an efficient (i.e., poly(log N)) quantum algorithm for this problem provided M > N^epsilon. The algorithm is based on the "pretty good measurement" and uses H. Lenstra's (classical) algorithm for integer programming as a subroutine.
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.
We examine the application of quantum algorithms to the non-Abelian hidden subgroup problem and focus on the dihedral hidden subgroup problem (DHSP). Ettinger and Høyer have recently discovered an algorithm which, although efficient in the number of operations of the quantum computation, requires classical post-processing which grows exponentially with the size of the input. We first show that the DHSP can be reduced to another problem: how to efficiently estimate an unknown shift k , in a one-to-one map f : M → M , given two oracles which provide x → f ( x ), and x → f ( x ⊕ k ), with k and f unknown. We devise an algorithm which uses amplitude amplification to obtain an estimate for the unknown shift k in a number (( M ) 1/2 ) oracle calls.
Difference sets are basic combinatorial structures that have applications in signal processing, coding theory, and cryptography. We consider the problem of identifying a shifted version of the characteristic function of a (known) difference set. We present a generic quantum algorithm that can be used to tackle any hidden shift problem for any difference set in any abelian group. We discuss special cases of this framework where the resulting quantum algorithm is efficient. This includes: a) Paley difference sets based on quadratic residues in finite fields, which allows to recover the shifted Legendre function quantum algorithm, b) Hadamard difference sets, which allows to recover the shifted bent function quantum algorithm, and c) Singer difference sets based on finite geometries. The latter class allows us to define instances of the dihedral hidden subgroup problem that can be efficiently solved on a quantum computer.
A new quantum algorithm for the hidden shift problem in Z2tn\mathbb{Z}_{2^t}^nZ2tn​
In this paper we make a step towards a time and space efficient algorithm for the hidden shift problem for groups of the form Zkn\mathbb{Z}_k^nZkn​. We give a solution to the case when kkk is a power of 2, which has polynomial running time in nnn, and only uses quadratic classical, and linear quantum space in nlog⁡(k)n\log (k)nlog(k). It can be a useful tool in the general case of the hidden shift and hidden subgroup problems too, since one of the main algorithms made to solve them can use this algorithm as a subroutine in its recursive steps, making it more efficient in some instances.
Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively. In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form G=A⋊φZpkG=A\rtimes_{\varphi} \mathbb{Z}_{p^k}G=A⋊φ​Zpk​, with AAA finite Abelian, ppp prime, k∈Nk\in \mathbb{N}k∈N and the action of Zpk\mathbb Z_{p^k}Zpk​ is generated by the scalar automorphism a↦μaa\mapstoμaa↦μa, for some μ∈ZExp⁡(A)×μ\in\mathbb Z_{\operatorname{Exp}(A)}^\timesμ∈ZExp(A)×​, where Exp(A)\mathrm{Exp}(A)Exp(A) is the exponent of AAA. Our algorithm is efficient when AAA has bounded generator rank and Exp(A)/p=polylog(∣G∣)\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)Exp(A)/p=polylog(∣G∣). This includes the case A=ZNA=\mathbb{Z}_NA=ZN​ for N∈NN\in\mathbb{N}N∈N and k=1k=1k=1, studied by Bacon, Childs and van Dam (FOCS 2005), and A=ZqrA=\mathbb{Z}_{q^r}A=Zqr​ with qqq prime and r∈Nr\in \mathbb{N}r∈N studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).