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:2102.04171

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

Gergely Csáji

Published Feb 8, 2021• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2102.04171

Related papers

Quantum algorithm for a generalized hidden shift problem

Andrew M. Childs, Wim van Dam

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.

arXiv:quant-ph/0507190•Symposium on Discrete Algorithms•Jul 19, 2005•42 citations

Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem

Greg Kuperberg

We give an algorithm for the hidden subgroup problem for the dihedral group $D_N$, or equivalently the cyclic hidden shift problem, that supersedes our first algorithm and is suggested by Regev's algorithm. It runs in $\exp(O(\sqrt{\log N}))$ quantum time and uses $\exp(O(\sqrt{\log N}))$ classical space, but only $O(\log N)$ quantum space. The algorithm also runs faster with quantumly addressable classical space than with fully classical space. In the hidden shift form, which is more natural for this algorithm regardless, it can also make use of multiple hidden shifts. It can also be extended with two parameters that trade classical space and classical time for quantum time. At the extreme space-saving end, the algorithm becomes Regev's algorithm. At the other end, if the algorithm is allowed classical memory with quantum random access, then many trade-offs between classical and quantum time are possible.

arXiv:1112.3333•Dec 14, 2011•26 citations

On solving systems of random linear disequations

Gábor Ivanyos

An important special case of the hidden subgroup problem is equivalent to the hidden shift problem over abelian groups. An efficient solution to the latter problem could serve as a building block of quantum hidden subgroup algorithms over solvable groups. The main idea of a promising approach to the hidden shift problem is a reduction to solving systems of certain random disequations in finite abelian groups. By a disequation we mean a constraint of the form $f(x)\neq 0$. In our case, the functions on the left hand side are generalizations of linear functions. The input is a random sample of functions according to a distribution which is up to a constant factor uniform over the "linear" functions $f$ such that $f(u)\neq 0$ for a fixed, although unknown element $u\in A$. The goal is to find $u$, or, more precisely, all the elements $u'\in A$ satisfying the same disequations as $u$. In this paper we give a classical probabilistic algorithm which solves the problem in an abelian $p$-group $A$ in time polynomial in the sample size $N$, where $N=(\log\size{A})^{O(q^2)}$, and $q$ is the exponent of $A$.

arXiv:0704.2988•Quantum Information and Computation•Jul 1, 2008•11 citations

Hidden Translation and Translating Coset in Quantum Computing

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez +2 more

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of nonabelian solvable groups, including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in $\mathbb{Z}_p^n$, whenever $p$ is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group $G$ is reducible to instances of Translating Coset in $G/N$ and $N$, for appropriate normal subgroups $N$ of $G$. Our self-reducibility framework, combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.

arXiv:quant-ph/0211091•SIAM Journal on Computing•Jan 1, 2014•15 citations

Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups

Y. Inui, François Le Gall

In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_q$, for $p$ and $q$ prime. We first present a classification of these groups in five classes. Then, we describe a polynomial-time quantum algorithm solving the HSP over all the groups of one of these classes: the groups of the form $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_p$, where $p$ is an odd prime. Our algorithm works even in the most general case where the group is presented as a black-box group with not necessarily unique encoding. Finally, we extend this result and present an efficient algorithm solving the HSP over the groups $\mathbb{Z}^m_{p^r}\rtimes\mathbb{Z}_p$.

arXiv:quant-ph/0412033•Quantum Information and Computation•Jul 1, 2007•12 citations

Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem

Gábor Ivanyos, Frédéric Magniez, Miklós Sántha

In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden normal subgroups of solvable groups and permutation groups, finding hidden subgroups of groups with small commutator subgroup and of groups admitting an elementary Abelian normal 2-subgroup of small index or with cyclic factor group.

arXiv:quant-ph/0102014•Feb 2, 2001•2 citations
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.
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 give an algorithm for the hidden subgroup problem for the dihedral group DND_NDN​, or equivalently the cyclic hidden shift problem, that supersedes our first algorithm and is suggested by Regev's algorithm. It runs in exp⁡(O(log⁡N))\exp(O(\sqrt{\log N}))exp(O(logN​)) quantum time and uses exp⁡(O(log⁡N))\exp(O(\sqrt{\log N}))exp(O(logN​)) classical space, but only O(log⁡N)O(\log N)O(logN) quantum space. The algorithm also runs faster with quantumly addressable classical space than with fully classical space. In the hidden shift form, which is more natural for this algorithm regardless, it can also make use of multiple hidden shifts. It can also be extended with two parameters that trade classical space and classical time for quantum time. At the extreme space-saving end, the algorithm becomes Regev's algorithm. At the other end, if the algorithm is allowed classical memory with quantum random access, then many trade-offs between classical and quantum time are possible.
An important special case of the hidden subgroup problem is equivalent to the hidden shift problem over abelian groups. An efficient solution to the latter problem could serve as a building block of quantum hidden subgroup algorithms over solvable groups. The main idea of a promising approach to the hidden shift problem is a reduction to solving systems of certain random disequations in finite abelian groups. By a disequation we mean a constraint of the form f(x)≠0f(x)\neq 0f(x)=0. In our case, the functions on the left hand side are generalizations of linear functions. The input is a random sample of functions according to a distribution which is up to a constant factor uniform over the "linear" functions fff such that f(u)≠0f(u)\neq 0f(u)=0 for a fixed, although unknown element u∈Au\in Au∈A. The goal is to find uuu, or, more precisely, all the elements u′∈Au'\in Au′∈A satisfying the same disequations as uuu. In this paper we give a classical probabilistic algorithm which solves the problem in an abelian ppp-group AAA in time polynomial in the sample size NNN, where $N=(\log\size{A})^{O(q^2)}$, and qqq is the exponent of AAA.
We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of nonabelian solvable groups, including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Zpn\mathbb{Z}_p^nZpn​, whenever ppp is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group GGG is reducible to instances of Translating Coset in G/NG/NG/N and NNN, for appropriate normal subgroups NNN of GGG. Our self-reducibility framework, combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.
In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups Zpr⋊Zq\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_qZpr​⋊Zq​, for ppp and qqq prime. We first present a classification of these groups in five classes. Then, we describe a polynomial-time quantum algorithm solving the HSP over all the groups of one of these classes: the groups of the form Zpr⋊Zp\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_pZpr​⋊Zp​, where ppp is an odd prime. Our algorithm works even in the most general case where the group is presented as a black-box group with not necessarily unique encoding. Finally, we extend this result and present an efficient algorithm solving the HSP over the groups Zprm⋊Zp\mathbb{Z}^m_{p^r}\rtimes\mathbb{Z}_pZprm​⋊Zp​.