dorsal/arxiv
View SchemaScalability of Shor's algorithm with a limited set of rotation gates
| Authors | Austin G. Fowler, Lloyd C. L. Hollenberg |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0306018 |
| URL | https://arxiv.org/abs/quant-ph/0306018 |
| DOI | 10.1103/PhysRevA.70.032329 |
| Journal | Phys. Rev. A 70, 032329 (2004) |
Abstract
Typical circuit implementations of Shor's algorithm involve controlled rotation gates of magnitude $\pi/2^{2L}$ where $L$ is the binary length of the integer N to be factored. Such gates cannot be implemented exactly using existing fault-tolerant techniques. Approximating a given controlled $\pi/2^{d}$ rotation gate to within $\delta=O(1/2^{d})$ currently requires both a number of qubits and number of fault-tolerant gates that grows polynomially with $d$. In this paper we show that this additional growth in space and time complexity would severely limit the applicability of Shor's algorithm to large integers. Consequently, we study in detail the effect of using only controlled rotation gates with $d$ less than or equal to some $d_{\rm max}$. It is found that integers up to length $L_{\rm max} = O(4^{d_{\rm max}})$ can be factored without significant performance penalty implying that the cumbersome techniques of fault-tolerant computation only need to be used to create controlled rotation gates of magnitude $\pi/64$ if integers thousands of bits long are desired factored. Explicit fault-tolerant constructions of such gates are also discussed.
{
"annotation_id": "c0774da7-5f28-4f0c-98b6-cf2a01e19943",
"date_created": "2026-03-02T18:01:59.973000Z",
"date_modified": "2026-03-02T18:01:59.973000Z",
"file_hash": "e68be3b30f74abce670511c246034505bc52d4f3c2b8de2ce3ccaa20f5a16d81",
"private": false,
"record": {
"abstract": "Typical circuit implementations of Shor\u0027s algorithm involve controlled\nrotation gates of magnitude $\\pi/2^{2L}$ where $L$ is the binary length of the\ninteger N to be factored. Such gates cannot be implemented exactly using\nexisting fault-tolerant techniques. Approximating a given controlled\n$\\pi/2^{d}$ rotation gate to within $\\delta=O(1/2^{d})$ currently requires both\na number of qubits and number of fault-tolerant gates that grows polynomially\nwith $d$. In this paper we show that this additional growth in space and time\ncomplexity would severely limit the applicability of Shor\u0027s algorithm to large\nintegers. Consequently, we study in detail the effect of using only controlled\nrotation gates with $d$ less than or equal to some $d_{\\rm max}$. It is found\nthat integers up to length $L_{\\rm max} = O(4^{d_{\\rm max}})$ can be factored\nwithout significant performance penalty implying that the cumbersome techniques\nof fault-tolerant computation only need to be used to create controlled\nrotation gates of magnitude $\\pi/64$ if integers thousands of bits long are\ndesired factored. Explicit fault-tolerant constructions of such gates are also\ndiscussed.",
"arxiv_id": "quant-ph/0306018",
"authors": [
"Austin G. Fowler",
"Lloyd C. L. Hollenberg"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.70.032329",
"journal_ref": "Phys. Rev. A 70, 032329 (2004)",
"title": "Scalability of Shor\u0027s algorithm with a limited set of rotation gates",
"url": "https://arxiv.org/abs/quant-ph/0306018"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "10822f48-2f4a-49d0-8cd7-8989b470d856",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}