DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2013.126

Classical and Quantum Algorithms for Testing Equivalence of Group Extensions

Authors: Kevin C. Zatloukal

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

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.

Cite as

Kevin C. Zatloukal. Classical and Quantum Algorithms for Testing Equivalence of Group Extensions. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 126-145, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{zatloukal:LIPIcs.TQC.2013.126,
  author =	{Zatloukal, Kevin C.},
  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 =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.126},
  URN =		{urn:nbn:de:0030-drops-43164},
  doi =		{10.4230/LIPIcs.TQC.2013.126},
  annote =	{Keywords: quantum computing, algorithms, computational group theory}
}

Search Results

Documents authored by Zatloukal, Kevin C.

Classical and Quantum Algorithms for Testing Equivalence of Group Extensions

Abstract

Cite as

Thanks for your feedback!

Could not send message