dorsal/arxiv
View SchemaThe quantum query complexity of the hidden subgroup problem is polynomial
| Authors | Mark Ettinger, Peter Hoyer, Emanuel Knill |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0401083 |
| URL | https://arxiv.org/abs/quant-ph/0401083 |
| DOI | 10.1016/j.ipl.2004.01.024 |
| Journal | Information Processing Letters, 91(1), 43-48, 16 July 2004 |
Abstract
We present a quantum algorithm which identifies with certainty a hidden subgroup of an arbitrary finite group G in only a polynomial (in log |G|) number of calls to the oracle. This is exponentially better than the best classical algorithm. However our quantum algorithm requires exponential time, as in the classical case. Our algorithm utilizes a new technique for constructing error-free algorithms for non-decision problems on quantum computers.
{
"annotation_id": "eceb9c0b-5762-4a39-993f-7f04c603381b",
"date_created": "2026-03-02T18:02:03.308000Z",
"date_modified": "2026-03-02T18:02:03.308000Z",
"file_hash": "2ed4302097707fcf78f2cf813d7c542f0e64b1310bb444b91ce271e872ba6024",
"private": false,
"record": {
"abstract": "We present a quantum algorithm which identifies with certainty a hidden\nsubgroup of an arbitrary finite group G in only a polynomial (in log |G|)\nnumber of calls to the oracle. This is exponentially better than the best\nclassical algorithm. However our quantum algorithm requires exponential time,\nas in the classical case. Our algorithm utilizes a new technique for\nconstructing error-free algorithms for non-decision problems on quantum\ncomputers.",
"arxiv_id": "quant-ph/0401083",
"authors": [
"Mark Ettinger",
"Peter Hoyer",
"Emanuel Knill"
],
"categories": [
"quant-ph"
],
"doi": "10.1016/j.ipl.2004.01.024",
"journal_ref": "Information Processing Letters, 91(1), 43-48, 16 July 2004",
"title": "The quantum query complexity of the hidden subgroup problem is polynomial",
"url": "https://arxiv.org/abs/quant-ph/0401083"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e98d8362-0238-420f-9c21-117dbe5a85fa",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}