Quantum algorithms for abelian di?erence sets and applications to dihedral hidden subgroups - Roetteler, Martin; Roetteler, Martin (Proceedings of the 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), 2016)
Diﬀerence 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) diﬀerence set. We present a generic quantum algorithm that can be used to tackle any hidden shift problem for any diﬀerence set in any abelian group. We discuss special cases of this framework where the resulting quantum algorithm is eﬃcient. This includes: a) Paley diﬀerence sets based on quadratic residues in ﬁnite ﬁelds, which allows to recover the shifted Legendre function quantum algorithm, b) Hadamard diﬀerence sets, which allows to recover the shifted bent function quantum algorithm, and c) Singer diﬀerence sets based on ﬁnite geometries. The latter class allows us to deﬁne instances of the dihedral hidden subgroup problem that can be eﬃciently solved on a quantum computer
Leibniz International Proceedings in Informatics (LIPIcs)