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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.