Please use this identifier to cite or link to this item:
Title: An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
Authors: Ivanyos, G.
Sanselme, L.
Santha, M. 
Keywords: Efficient algorithm
Hidden subgroup problem
Nilpotent group
Quantum computing
Issue Date: Feb-2012
Citation: Ivanyos, G., Sanselme, L., Santha, M. (2012-02). An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups. Algorithmica (New York) 62 (1-2) : 480-498. ScholarBank@NUS Repository.
Abstract: In this paper we 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 is an extension of our earlier method for extraspecial groups in Ivanyos et al. (Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science (STACS), vol. 4393, pp. 586-597, 2007), but it 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. © 2010 Springer Science+Business Media, LLC.
Source Title: Algorithmica (New York)
ISSN: 01784617
DOI: 10.1007/s00453-010-9467-0
Appears in Collections:Staff Publications

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


checked on Jan 12, 2019


checked on Jan 2, 2019

Page view(s)

checked on Jan 18, 2019

Google ScholarTM



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