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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.