Classical and quantum algorithms for testing equivalence of group extensions
From MaRDI portal
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.
Recommendations
- An efficient quantum algorithm for some instances of the group isomorphism problem
- Quantum algorithms for solvable groups
- Efficient isomorphism testing for a class of group extensions
- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
- The Hidden Subgroup Problem and Quantum Computation Using Group Representations
Cited in
(2)
This page was built for publication: Classical and quantum algorithms for testing equivalence of group extensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2958416)
