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

DOI10.1007/978-3-540-70918-3_50MaRDI QIDQ3590968zbMATH OpenOpenAlexFDO

Authors Gábor Ivanyos, Luc Sanselme, Miklos Santha

Publication date 3 September 2007

Published in STACS 2007 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0701235, http://cds.cern.ch/record/1014439

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)

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.

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

Cited in

(7)

• An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups
• 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
• An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group
• scientific article; zbMATH DE number 1304334 (Why is no real title available?)
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

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)