What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries?
Ettinger, Hoyer, and Knill give a result that the success probability is $1-4r/2^{s/2}$, where $r$ is the number of subgroups of $G$ and $s$ is the query number. However, this result seems to come from a specific set-up for the algorithm that departs from simply measuring a list of characters of $G$. Does someone work out what the error probability in reconstructing the hidden subgroup would be just as a function of the number of characters measured?
Simplified cases where $G$ is cyclic or a product of $Z_2$ groups would also be of interest.
