dorsal/arxiv
View SchemaReversible addition circuit using one ancillary bit with application to quantum computing
| Authors | Phillip Kaye |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0408173 |
| URL | https://arxiv.org/abs/quant-ph/0408173 |
Abstract
Most of the work on implementing arithmetic on a quantum computer has borrowed from results in classical reversible computing (e.g. [VBE95], [BBF02], [DKR04]). These quantum networks are inherently classical, as they can be implemented with only the Toffoli gate. Draper [D00] has proposed an inherently "quantum" network for addition based on the quantum Fourier transform. His approach has the advantage that it requires no carry qubits (the previous approaches required O(n) carry qubits). The network in [D00] uses quantum rotation gates, which must either be implemented with exponential precision, or else be approximated. In this paper I give a network of O(n^3) Toffoli gates for reversibly performing in-place addition with only a single ancillary bit, demonstrating that inherently quantum techniques are not required to achieve this goal (provided we are willing to sacrifice quadratic circuit depth). After posting the original version of this note it was pointed out to me by C. Zalka that essentially the same technique for addition was used in [BCD+96]. The scenario in that paper was different, but it is clear how the technique they described generalizes to that in this paper.
{
"annotation_id": "3f4f070e-42f7-4e51-bfcc-dcb7cefb2f3c",
"date_created": "2026-03-02T18:02:10.219000Z",
"date_modified": "2026-03-02T18:02:10.219000Z",
"file_hash": "9b854635a504567552017478afcfeb480ccc185bb680261297ffc9664cf1b6cf",
"private": false,
"record": {
"abstract": "Most of the work on implementing arithmetic on a quantum computer has\nborrowed from results in classical reversible computing (e.g. [VBE95], [BBF02],\n[DKR04]). These quantum networks are inherently classical, as they can be\nimplemented with only the Toffoli gate. Draper [D00] has proposed an inherently\n\"quantum\" network for addition based on the quantum Fourier transform. His\napproach has the advantage that it requires no carry qubits (the previous\napproaches required O(n) carry qubits). The network in [D00] uses quantum\nrotation gates, which must either be implemented with exponential precision, or\nelse be approximated. In this paper I give a network of O(n^3) Toffoli gates\nfor reversibly performing in-place addition with only a single ancillary bit,\ndemonstrating that inherently quantum techniques are not required to achieve\nthis goal (provided we are willing to sacrifice quadratic circuit depth). After\nposting the original version of this note it was pointed out to me by C. Zalka\nthat essentially the same technique for addition was used in [BCD+96]. The\nscenario in that paper was different, but it is clear how the technique they\ndescribed generalizes to that in this paper.",
"arxiv_id": "quant-ph/0408173",
"authors": [
"Phillip Kaye"
],
"categories": [
"quant-ph"
],
"title": "Reversible addition circuit using one ancillary bit with application to quantum computing",
"url": "https://arxiv.org/abs/quant-ph/0408173"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a463e2b6-d212-4e19-96e9-37d0434a1429",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}