dorsal/arxiv
View SchemaQuantum Carry-Save Arithmetic
| Authors | Phil Gossett |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9808061 |
| URL | https://arxiv.org/abs/quant-ph/9808061 |
Abstract
This paper shows how to design efficient arithmetic elements out of quantum gates using "carry-save" techniques borrowed from classical computer design. This allows bit-parallel evaluation of all the arithmetic elements required for Shor's algorithm, including modular arithmetic, deferring all carry propagation until the end of the entire computation. This reduces the quantum gate delay from O(N^3) to O(N log N) at a cost of increasing the number of qubits required from O(N) to O(N^2).
{
"annotation_id": "19aad9dd-dd0a-438c-80c1-5499013deda5",
"date_created": "2026-03-02T18:02:45.255000Z",
"date_modified": "2026-03-02T18:02:45.255000Z",
"file_hash": "6567d6650e551e74100bca065a3e2723c62f72fe000e49a1fff8fe18e2421f7b",
"private": false,
"record": {
"abstract": "This paper shows how to design efficient arithmetic elements out of quantum\ngates using \"carry-save\" techniques borrowed from classical computer design.\nThis allows bit-parallel evaluation of all the arithmetic elements required for\nShor\u0027s algorithm, including modular arithmetic, deferring all carry propagation\nuntil the end of the entire computation. This reduces the quantum gate delay\nfrom O(N^3) to O(N log N) at a cost of increasing the number of qubits required\nfrom O(N) to O(N^2).",
"arxiv_id": "quant-ph/9808061",
"authors": [
"Phil Gossett"
],
"categories": [
"quant-ph"
],
"title": "Quantum Carry-Save Arithmetic",
"url": "https://arxiv.org/abs/quant-ph/9808061"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "409b32f9-a43b-487f-a6a1-2f8dc1fef0d7",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}