dorsal/arxiv
View SchemaAn Exact Quantum Polynomial-Time Algorithm for Simon's Problem
| Authors | Gilles Brassard, Peter Hoyer |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9704027 |
| URL | https://arxiv.org/abs/quant-ph/9704027 |
| DOI | 10.1109/ISTCS.1997.595153 |
| Journal | Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS'97), pp. 12-23, June 1997 |
Abstract
We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas previous algorithms required quantum polynomial time in the expected sense only, without upper bounds on the worst-case running time. This is achieved by generalizing both Simon's and Grover's algorithms and combining them in a novel way. It follows that there is a decision problem that can be solved in exact quantum polynomial time, which would require expected exponential time on any classical bounded-error probabilistic computer if the data is supplied as a black box.
{
"annotation_id": "973366b7-9013-42e4-a1d7-8d413419569f",
"date_created": "2026-03-02T18:02:40.781000Z",
"date_modified": "2026-03-02T18:02:40.781000Z",
"file_hash": "3119aef2b824eafe0f5ec7c9e71b8cfb64f3a37a2e1d4cc9d5579c9b573b3c60",
"private": false,
"record": {
"abstract": "We investigate the power of quantum computers when they are required to\nreturn an answer that is guaranteed to be correct after a time that is\nupper-bounded by a polynomial in the worst case. We show that a natural\ngeneralization of Simon\u0027s problem can be solved in this way, whereas previous\nalgorithms required quantum polynomial time in the expected sense only, without\nupper bounds on the worst-case running time. This is achieved by generalizing\nboth Simon\u0027s and Grover\u0027s algorithms and combining them in a novel way. It\nfollows that there is a decision problem that can be solved in exact quantum\npolynomial time, which would require expected exponential time on any classical\nbounded-error probabilistic computer if the data is supplied as a black box.",
"arxiv_id": "quant-ph/9704027",
"authors": [
"Gilles Brassard",
"Peter Hoyer"
],
"categories": [
"quant-ph"
],
"doi": "10.1109/ISTCS.1997.595153",
"journal_ref": "Fifth Israeli Symposium on Theory of Computing and Systems\n (ISTCS\u002797), pp. 12-23, June 1997",
"title": "An Exact Quantum Polynomial-Time Algorithm for Simon\u0027s Problem",
"url": "https://arxiv.org/abs/quant-ph/9704027"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9304d616-32ca-4d45-8960-094b66b9481f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}