dorsal/arxiv
View SchemaA Lower Bound for Quantum Phase Estimation
| Authors | Arvid J. Bessen |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0412008 |
| URL | https://arxiv.org/abs/quant-ph/0412008 |
| DOI | 10.1103/PhysRevA.71.042313 |
| Journal | Phys. Rev. A 71, 042313 (2005) |
Abstract
We obtain a query lower bound for quantum algorithms solving the phase estimation problem. Our analysis generalizes existing lower bound approaches to the case where the oracle Q is given by controlled powers Q^p of Q, as it is for example in Shor's order finding algorithm. In this setting we will prove a log (1/epsilon) lower bound for the number of applications of Q^p1, Q^p2, ... This bound is tight due to a matching upper bound. We obtain the lower bound using a new technique based on frequency analysis.
{
"annotation_id": "34600f4c-2dcd-4342-9804-4794f1bd2111",
"date_created": "2026-03-02T18:02:12.968000Z",
"date_modified": "2026-03-02T18:02:12.968000Z",
"file_hash": "9a130d64255a9259637127088bce4d186289fe97b6502f52e2acb35b654201b6",
"private": false,
"record": {
"abstract": "We obtain a query lower bound for quantum algorithms solving the phase\nestimation problem. Our analysis generalizes existing lower bound approaches to\nthe case where the oracle Q is given by controlled powers Q^p of Q, as it is\nfor example in Shor\u0027s order finding algorithm. In this setting we will prove a\nlog (1/epsilon) lower bound for the number of applications of Q^p1, Q^p2, ...\nThis bound is tight due to a matching upper bound. We obtain the lower bound\nusing a new technique based on frequency analysis.",
"arxiv_id": "quant-ph/0412008",
"authors": [
"Arvid J. Bessen"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.71.042313",
"journal_ref": "Phys. Rev. A 71, 042313 (2005)",
"title": "A Lower Bound for Quantum Phase Estimation",
"url": "https://arxiv.org/abs/quant-ph/0412008"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "0de890a7-8f91-46d5-b35d-1e774b80d67c",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}