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$ .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.2988Quantum Information and ComputationJul 1, 200811 citations

On decomposing finite abelian groups

Sándor Szabó

Acta Mathematica Academiae Scientiarum HungaricaeMar 1, 19808 citations

Quantum algorithms for Abelian groups

Alexei Kitaev, Alexander Khanievich Shen', M. Vyalyi

Graduate studies in mathematicsMay 31, 20020 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.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.02005Aug 5, 20164 citations

Deterministic algorithms for the hidden subgroup problem

Zekun Ye, Lvzhou Li

arXiv:2110.00827Information and ComputationOct 14, 20223 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 and present a general 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 which include a) Paley difference sets based on quadratic residues in finite fields which allow to recover the shifted Legendre function quantum algorithm, b) Hadamard difference sets which allow to recover the shifted bent function quantum algorithm, and c) Singer difference sets which allow us to define instances of the dihedral hidden subgroup problem which can be efficiently solved on a quantum computer.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 and present a general 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 which include a) Paley difference sets based on quadratic residues in finite fields which allow to recover the shifted Legendre function quantum algorithm, b) Hadamard difference sets which allow to recover the shifted bent function quantum algorithm, and c) Singer difference sets which allow us to define instances of the dihedral hidden subgroup problem which can be efficiently solved on a quantum computer.

Leibniz international proceedings in informaticsJan 1, 20160 citations

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