An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups

DOI10.1007/978-3-540-70918-3_50zbMATH Open1186.20015arXivquant-ph/0701235OpenAlexW1535463230MaRDI QIDQ3590968FDOQ3590968

Authors: Gábor Ivanyos, Luc Sanselme, Miklos Santha 

Publication date: 3 September 2007

Published in: STACS 2007 (Search for Journal in Brave)

Abstract: Extraspecial groups form a remarkable subclass of p-groups. They are also present in quantum information theory, in particular in quantum error correction. We give here a polynomial time quantum algorithm for finding hidden subgroups in extraspecial groups. Our approach is quite different from the recent algorithms presented in [17] and [2] for the Heisenberg group, the extraspecial p-group of size p3 and exponent p. Exploiting certain nice automorphisms of the extraspecial groups we define specific group actions which are used to reduce the problem to hidden subgroup instances in abelian groups that can be dealt with directly.

Full work available at URL: https://arxiv.org/abs/quant-ph/0701235

Recommendations

• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
• EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
• Hidden subgroup quantum algorithms for a class of semi-direct product groups
• The quantum query complexity of the hidden subgroup problem is polynomial

zbMATH Keywords

extraspecial \(p\)-groupfinite \(p\)-group

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Finite nilpotent groups, (p)-groups (20D15)

Cited In (7)

• An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group
• Hidden subgroup quantum algorithms for a class of semi-direct product groups
• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
• Title not available (Why is that?)
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups

This page was built for publication: An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3590968)