dorsal/arxiv
View SchemaOptimal measurements for the dihedral hidden subgroup problem
| Authors | Dave Bacon, Andrew M. Childs, Wim van Dam |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0501044 |
| URL | https://arxiv.org/abs/quant-ph/0501044 |
| DOI | 10.4086/cjtcs.2006.002 |
| Journal | Chicago Journal of Theoretical Computer Science (2006), no. 2 |
Abstract
We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.
{
"annotation_id": "49ac2156-51f2-40f1-8e6b-1df1a76148c5",
"date_created": "2026-03-02T18:02:13.027000Z",
"date_modified": "2026-03-02T18:02:13.027000Z",
"file_hash": "eaa1e5761a9e4eba73498263c47a50f501579fa20190cf31f739335bdace725b",
"private": false,
"record": {
"abstract": "We consider the dihedral hidden subgroup problem as the problem of\ndistinguishing hidden subgroup states. We show that the optimal measurement for\nsolving this problem is the so-called pretty good measurement. We then prove\nthat the success probability of this measurement exhibits a sharp threshold as\na function of the density nu=k/log N, where k is the number of copies of the\nhidden subgroup state and 2N is the order of the dihedral group. In particular,\nfor nu\u003c1 the optimal measurement (and hence any measurement) identifies the\nhidden subgroup with a probability that is exponentially small in log N, while\nfor nu\u003e1 the optimal measurement identifies the hidden subgroup with a\nprobability of order unity. Thus the dihedral group provides an example of a\ngroup G for which Omega(log|G|) hidden subgroup states are necessary to solve\nthe hidden subgroup problem. We also consider the optimal measurement for\ndetermining a single bit of the answer, and show that it exhibits the same\nthreshold. Finally, we consider implementing the optimal measurement by a\nquantum circuit, and thereby establish further connections between the dihedral\nhidden subgroup problem and average case subset sum problems. In particular, we\nshow that an efficient quantum algorithm for a restricted version of the\noptimal measurement would imply an efficient quantum algorithm for the subset\nsum problem, and conversely, that the ability to quantum sample from subset sum\nsolutions allows one to implement the optimal measurement.",
"arxiv_id": "quant-ph/0501044",
"authors": [
"Dave Bacon",
"Andrew M. Childs",
"Wim van Dam"
],
"categories": [
"quant-ph"
],
"doi": "10.4086/cjtcs.2006.002",
"journal_ref": "Chicago Journal of Theoretical Computer Science (2006), no. 2",
"title": "Optimal measurements for the dihedral hidden subgroup problem",
"url": "https://arxiv.org/abs/quant-ph/0501044"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8b1b01d5-c77a-498d-b5f3-42b6a37a7d97",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}