All Abstracts | Poster Abstracts | Talk Abstracts | Tutorial Abstracts

Distinguishing the Borel subgroups of PSL(2; q)

Aaron Denney, University of New Mexico

(Session 8 : Saturday from 5:00-5:30)

Abstract. The Hidden Subgroup Problem (HSP) has been a fruitful framework for expressing many quantum algorithms, and the Abelian case is completely understood. Most efforts to attack non-Abelian groups have been based on splitting these groups into simpler factors. The non-Abelian simple group PSL(2; q) has no non-trivial factors, so cannot be attacked in this way. Further, it has no known efficient quantum Fourier transform. As such, the standard method for distinguishing subgroups fails almost from the beginning. However, we can use the 3-transitivity of PSL(2; q) to distinguish among a large set of stabilizer subgroups by working with their intersections, and reducing to a smaller group with an efficient transform. These stabilizer subgroups are conjugates of the Borel subgroup of upper triangular matrices. Although restricted to this one class of subgroups, this is the first efficient algorithm for a case of the HSP in a family of non-Abelian simple groups.