dorsal/arxiv
View SchemaA quantum lower bound for the query complexity of Simon's problem
| Authors | Pascal Koiran, Vincent Nesme, Natacha Portier |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0501060 |
| URL | https://arxiv.org/abs/quant-ph/0501060 |
Abstract
Simon in his FOCS'94 paper was the first to show an exponential gap between classical and quantum computation. The problem he dealt with is now part of a well-studied class of problems, the hidden subgroup problems. We study Simon's problem from the point of view of quantum query complexity and give here a first nontrivial lower bound on the query complexity of a hidden subgroup problem, namely Simon's problem. Our bound is optimal up to a constant factor.
{
"annotation_id": "0457f2ec-6abd-4f4a-8dc6-d643aa163352",
"date_created": "2026-03-02T18:02:13.516000Z",
"date_modified": "2026-03-02T18:02:13.516000Z",
"file_hash": "9a93c97793bf7d1f50ddfdb22a5ba578e9c6bb815fe9b50975f514bc56a6c589",
"private": false,
"record": {
"abstract": "Simon in his FOCS\u002794 paper was the first to show an exponential gap between\nclassical and quantum computation. The problem he dealt with is now part of a\nwell-studied class of problems, the hidden subgroup problems. We study Simon\u0027s\nproblem from the point of view of quantum query complexity and give here a\nfirst nontrivial lower bound on the query complexity of a hidden subgroup\nproblem, namely Simon\u0027s problem. Our bound is optimal up to a constant factor.",
"arxiv_id": "quant-ph/0501060",
"authors": [
"Pascal Koiran",
"Vincent Nesme",
"Natacha Portier"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "A quantum lower bound for the query complexity of Simon\u0027s problem",
"url": "https://arxiv.org/abs/quant-ph/0501060"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "dc002eb3-2495-46e5-b79b-5d741b37b6c4",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}