An Improved Query for the Hidden Subgroup Problem
arXiv:1101.1053
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, generalizing 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.
26 pages. Expanded the introduction
References in corpus (10)
- Quantum Algorithms Revisited
- From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
- A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
- The Hidden Subgroup Problem - Review and Open Problems
- A Quantum Observable for the Graph Isomorphism Problem
- The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer
- For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
- The Optimal Single Copy Measurement for the Hidden Subgroup Problem
- The Hidden Subgroup Problem
- How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem