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.2013.126
URN: urn:nbn:de:0030-drops-43164
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4316/
Go to the corresponding LIPIcs Volume Portal

Zatloukal, Kevin C.

Classical and Quantum Algorithms for Testing Equivalence of Group Extensions

pdf-format:
22.pdf (0.5 MB)

Abstract

While efficient algorithms are known for solving many important problems related to groups, no efficient algorithm is known for determining whether two arbitrary groups are isomorphic. The particular case of 2-nilpotent groups, a special type of central extension, is widely believed to contain the essential hard cases. However, looking specifically at central extensions, the natural formulation of being "the same" is not isomorphism but rather "equivalence," which requires an isomorphism to preserves the structure of the extension. In this paper, we show that equivalence of central extensions can be computed efficiently on a classical computer when the groups are small enough to be given by their multiplication tables. However, in the model of black box groups, which allows the groups to be much larger, we show that equivalence can be computed efficiently on a quantum computer but not a classical one (under common complexity assumptions). Our quantum algorithm demonstrates a new application of the hidden subgroup problem for general abelian groups.

BibTeX - Entry

@InProceedings{zatloukal:LIPIcs:2013:4316,
  author =	{Kevin C. Zatloukal},
  title =	{{Classical and Quantum Algorithms for Testing Equivalence of Group Extensions}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{126--145},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Simone Severini and Fernando Brandao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4316},
  URN =		{urn:nbn:de:0030-drops-43164},
  doi =		{10.4230/LIPIcs.TQC.2013.126},
  annote =	{Keywords: quantum computing, algorithms, computational group theory}
}

Keywords: quantum computing, algorithms, computational group theory
Collection: 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)
Issue Date: 2013
Date of publication: 13.11.2013

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