An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group
- Publisher:
- Springer
- Publication Type:
- Conference Proceeding
- Citation:
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8635 LNCS, (PART 2), pp. 226-238
- Issue Date:
- 2014-01-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
In the theory of algebraic groups, parabolic subgroups form a crucial building block in the structural studies. In the case of general linear groups over a finite field, given a sequence of positive integers n 1 , ⋯, n k , where n=n 1 +⋯+n k , a parabolic subgroup of parameter (n 1 , ⋯, n k ) in GL is a conjugate of the subgroup consisting of block lower triangular matrices where the ith block is of size n i . Our main result is a quantum algorithm of time polynomial in logq and n for solving the hidden subgroup problem in GL, when the hidden subgroup is promised to be a parabolic subgroup. Our algorithm works with no prior knowledge of the parameter of the hidden parabolic subgroup. Prior to this work, such an efficient quantum algorithm was only known for minimal parabolic subgroups (Borel subgroups), for the case when q is not much smaller than n (G. Ivanyos: Quantum Inf. Comput., Vol. 12, pp. 661-669). © 2014 Springer-Verlag Berlin Heidelberg.
Please use this identifier to cite or link to this item: