Please use this identifier to cite or link to this item:
Title: Hidden symmetry subgroup problems
Authors: Decker, T.
Ivanyos, G.
Santha, M. 
Wocjan, P.
Keywords: Hidden polynomial problem
Hidden subgroup problem
Quantum algorithms
Issue Date: 2013
Citation: Decker, T., Ivanyos, G., Santha, M., Wocjan, P. (2013). Hidden symmetry subgroup problems. SIAM Journal on Computing 42 (5) : 1987-2007. ScholarBank@NUS Repository.
Abstract: We advocate a new approach for addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the hidden symmetry subgroup problem (HSSP), which is a generalization of the well-studied hidden subgroup problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSSP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSSP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSSP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSSP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms. © 2013 Society for Industrial and Applied Mathematics.
Source Title: SIAM Journal on Computing
ISSN: 00975397
DOI: 10.1137/120864416
Appears in Collections:Staff Publications

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


checked on Oct 18, 2021


checked on Oct 18, 2021

Page view(s)

checked on Oct 14, 2021

Google ScholarTM



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