Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-540-78773-0_65
Title: An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
Authors: Ivanyos, G.
Sanselme, L.
Santha, M. 
Issue Date: 2008
Citation: Ivanyos, G., Sanselme, L., Santha, M. (2008). An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4957 LNCS : 759-771. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-540-78773-0_65
Abstract: In this paper we extend the algorithm for extraspecial groups in [12], and show that the hidden subgroup problem in nil-2 groups, that is in groups of nilpotency class at most 2, can be solved efficiently by a quantum procedure. The algorithm presented here has several additional features. It contains a powerful classical reduction for the hidden subgroup problem in nilpotent groups of constant nilpotency class to the specific case where the group is a p-group of exponent p and the subgroup is either trivial or cyclic. This reduction might also be useful for dealing with groups of higher nilpotency class. The quantum part of the algorithm uses well chosen group actions based on some automorphisms of nil-2 groups. The right choice of the actions requires the solution of a system of quadratic and linear equations. The existence of a solution is guaranteed by the Chevalley-Warning theorem, and we prove that it can also be found efficiently. © 2008 Springer-Verlag Berlin Heidelberg.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/115379
ISBN: 3540787720
ISSN: 03029743
DOI: 10.1007/978-3-540-78773-0_65
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

10
checked on Sep 26, 2022

WEB OF SCIENCETM
Citations

8
checked on Sep 26, 2022

Page view(s)

119
checked on Sep 22, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.