All Abstracts | Poster Abstracts | Talk Abstracts | Tutorial Abstracts

Towards an optimal algorithm for the hidden subgroup problem of dihedral group of order 2p (p: prime greater than 2)

Asif Shakeel, University of California at San Diego

(Session 5 : Friday from 5:00-7:00)

Abstract. Pretty Good Measurement is optimal for the problem of determining order two subgroups of dihedral group consisting of the identity and a reflection. Importantly, the work of Moore and Russell provides a representation theoretic proof of that. The main result of this paper is development of a multi-query algorithm that exploits the representation of dihedral group. Bacon, Van Dam and Childs and prior to them Regev show that the solution of the subset sum problem may be central to an algorithm implementing the Pretty Good Measurement. In our work, subset sum problem surfaces in the identification of irreducible sub-representations. Rest of the computations are explicitly shown in terms of Fourier transform on dihedral group, which is implemented by abelian transforms.