License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2016.8
URN: urn:nbn:de:0030-drops-66896
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6689/
Go to the corresponding LIPIcs Volume Portal

Roetteler, Martin

Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups

pdf-format:
LIPIcs-TQC-2016-8.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{roetteler:LIPIcs:2016:6689,
  author =	{Martin Roetteler},
  title =	{{Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-019-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{61},
  editor =	{Anne Broadbent},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6689},
  URN =		{urn:nbn:de:0030-drops-66896},
  doi =		{10.4230/LIPIcs.TQC.2016.8},
  annote =	{Keywords: Quantum algorithms, hidden shift problem, hidden subgroup problem, difference sets, Fourier transforms}
}

Keywords: Quantum algorithms, hidden shift problem, hidden subgroup problem, difference sets, Fourier transforms
Collection: 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
Issue Date: 2016
Date of publication: 22.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI