dorsal/arxiv
View SchemaFor Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
| Authors | Cristopher Moore, Alexander Russell |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0501177 |
| URL | https://arxiv.org/abs/quant-ph/0501177 |
Abstract
Recently Bacon, Childs and van Dam showed that the ``pretty good measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral group D_n in the case where the hidden subgroup is chosen uniformly from the n involutions. We show that, for any group and any subgroup H, the PGM is the optimal one-register experiment in the case where the hidden subgroup is a uniformly random conjugate of H. We go on to show that when H forms a Gel'fand pair with its parent group, the PGM is the optimal measurement for any number of registers. In both cases we bound the probability that the optimal measurement succeeds. This generalizes the case of the dihedral group, and includes a number of other examples of interest.
{
"annotation_id": "1cac6ab1-0877-4b74-a5f0-a589008098c7",
"date_created": "2026-03-02T18:02:13.522000Z",
"date_modified": "2026-03-02T18:02:13.522000Z",
"file_hash": "05cc6f8d2c326d17f093a8250dacfc62edb19e7287559148bae4612605172c18",
"private": false,
"record": {
"abstract": "Recently Bacon, Childs and van Dam showed that the ``pretty good\nmeasurement\u0027\u0027 (PGM) is optimal for the Hidden Subgroup Problem on the dihedral\ngroup D_n in the case where the hidden subgroup is chosen uniformly from the n\ninvolutions. We show that, for any group and any subgroup H, the PGM is the\noptimal one-register experiment in the case where the hidden subgroup is a\nuniformly random conjugate of H. We go on to show that when H forms a Gel\u0027fand\npair with its parent group, the PGM is the optimal measurement for any number\nof registers. In both cases we bound the probability that the optimal\nmeasurement succeeds. This generalizes the case of the dihedral group, and\nincludes a number of other examples of interest.",
"arxiv_id": "quant-ph/0501177",
"authors": [
"Cristopher Moore",
"Alexander Russell"
],
"categories": [
"quant-ph"
],
"title": "For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets",
"url": "https://arxiv.org/abs/quant-ph/0501177"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "bc3a6829-4467-4711-ab23-2c3207c317cf",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}