All Abstracts | Poster Abstracts | Talk Abstracts

An Improved Query for the Hidden Subgroup Problem

Asif Shakeel, University of California at San Diego

(Session 10b : Saturday from 5:30pm-6:00pm)

Abstract. An equal superposition query with |0> in the response register is used in the "standard method" of single-query algorithms for the Hidden Subgroup Problem (HSP). Here we introduce a different query, the character query, a generalization of the well-known phase kickback trick. This query maximizes the success probability of subgroup identification under a uniform prior, for the HSP in which the oracle functions take values in a finite abelian group. We then apply our results to the case when the subgroups are drawn from a set of conjugate subgroups and obtain a success probability greater than that found by Moore and Russell.