dorsal/arxiv
View SchemaA logarithmic-depth quantum carry-lookahead adder
| Authors | Thomas G. Draper, Samuel A. Kutin, Eric M. Rains, Krysta M. Svore |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0406142 |
| URL | https://arxiv.org/abs/quant-ph/0406142 |
| Journal | Quant. Inf. Comp. Vol. 6, No. 4-5, pp. 351-369 (2006) |
Abstract
We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.
{
"annotation_id": "f501e9b9-04d1-4178-af0d-c776c7ee459c",
"date_created": "2026-03-02T18:02:10.334000Z",
"date_modified": "2026-03-02T18:02:10.334000Z",
"file_hash": "910952d9c4696cc3ffbf80bb8eade85b450f274aeb8605c9ef1952ef07fe7ccc",
"private": false,
"record": {
"abstract": "We present an efficient addition circuit, borrowing techniques from the\nclassical carry-lookahead arithmetic circuit. Our quantum carry-lookahead\n(QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using\nO(n) ancillary qubits. We present both in-place and out-of-place versions, as\nwell as versions that add modulo 2^n and modulo 2^n - 1.\n Previously, the linear-depth ripple-carry addition circuit has been the\nmethod of choice. Our work reduces the cost of addition dramatically with only\na slight increase in the number of required qubits. The QCLA adder can be used\nwithin current modular multiplication circuits to reduce substantially the\nrun-time of Shor\u0027s algorithm.",
"arxiv_id": "quant-ph/0406142",
"authors": [
"Thomas G. Draper",
"Samuel A. Kutin",
"Eric M. Rains",
"Krysta M. Svore"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quant. Inf. Comp. Vol. 6, No. 4-5, pp. 351-369 (2006)",
"title": "A logarithmic-depth quantum carry-lookahead adder",
"url": "https://arxiv.org/abs/quant-ph/0406142"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "7752506a-4893-4b36-a48d-4a56bf4ee802",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}