dorsal/arxiv
View SchemaExplicit Multiregister Measurements for Hidden Subgroup Problems
| Authors | Cristopher Moore, Alexander Russell |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0504067 |
| URL | https://arxiv.org/abs/quant-ph/0504067 |
Abstract
We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement uses $k=\log_2 |G|$ registers, and each of the $2^k$ subsets of the registers contributes some information. While this does not, in general, yield an efficient algorithm, it generalizes the relationship between Subset Sum and the HSP in the dihedral group, and sheds some light on how quantum algorithms for Graph Isomorphism might work.
{
"annotation_id": "868baf8a-39fb-4e41-bde3-0d3b6d8c7587",
"date_created": "2026-03-02T18:02:17.046000Z",
"date_modified": "2026-03-02T18:02:17.046000Z",
"file_hash": "fe5656fca8c4f09ffda903ee0580f16588d3bcf3b8258b37fc94928b12960f47",
"private": false,
"record": {
"abstract": "We present an explicit measurement in the Fourier basis that solves an\nimportant case of the Hidden Subgroup Problem, including the case to which\nGraph Isomorphism reduces. This entangled measurement uses $k=\\log_2 |G|$\nregisters, and each of the $2^k$ subsets of the registers contributes some\ninformation. While this does not, in general, yield an efficient algorithm, it\ngeneralizes the relationship between Subset Sum and the HSP in the dihedral\ngroup, and sheds some light on how quantum algorithms for Graph Isomorphism\nmight work.",
"arxiv_id": "quant-ph/0504067",
"authors": [
"Cristopher Moore",
"Alexander Russell"
],
"categories": [
"quant-ph"
],
"title": "Explicit Multiregister Measurements for Hidden Subgroup Problems",
"url": "https://arxiv.org/abs/quant-ph/0504067"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "ed77aaf7-541d-4cf4-8460-653997478ed1",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}