dorsal/arxiv
View SchemaElementary gates for quantum computation
| Authors | A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, H. Weinfurter |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9503016 |
| URL | https://arxiv.org/abs/quant-ph/9503016 |
| DOI | 10.1103/PhysRevA.52.3457 |
| Journal | Phys.Rev. A52 (1995) 3457 |
Abstract
We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values $(x,y)$ to $(x,x \oplus y)$) is universal in the sense that all unitary operations on arbitrarily many bits $n$ (U($2^n$)) can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical AND of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two-and three-bit quantum gates, the asymptotic number required for $n$-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary $n$-bit unitary operations.
{
"annotation_id": "36382292-cfb5-40f6-99c9-ed5d656a645e",
"date_created": "2026-03-02T18:02:37.286000Z",
"date_modified": "2026-03-02T18:02:37.286000Z",
"file_hash": "38c970467035d9f722bf4137fd6a8aa63c65947c587982fbf2ca3804af3c281c",
"private": false,
"record": {
"abstract": "We show that a set of gates that consists of all one-bit quantum gates (U(2))\nand the two-bit exclusive-or gate (that maps Boolean values $(x,y)$ to $(x,x\n\\oplus y)$) is universal in the sense that all unitary operations on\narbitrarily many bits $n$ (U($2^n$)) can be expressed as compositions of these\ngates. We investigate the number of the above gates required to implement other\ngates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2)\ntransformation to one input bit if and only if the logical AND of all remaining\ninput bits is satisfied. These gates play a central role in many proposed\nconstructions of quantum computational networks. We derive upper and lower\nbounds on the exact number of elementary gates required to build up a variety\nof two-and three-bit quantum gates, the asymptotic number required for $n$-bit\nDeutsch-Toffoli gates, and make some observations about the number required for\narbitrary $n$-bit unitary operations.",
"arxiv_id": "quant-ph/9503016",
"authors": [
"A. Barenco",
"C. H. Bennett",
"R. Cleve",
"D. P. DiVincenzo",
"N. Margolus",
"P. Shor",
"T. Sleator",
"J. Smolin",
"H. Weinfurter"
],
"categories": [
"quant-ph",
"cond-mat",
"hep-th"
],
"doi": "10.1103/PhysRevA.52.3457",
"journal_ref": "Phys.Rev. A52 (1995) 3457",
"title": "Elementary gates for quantum computation",
"url": "https://arxiv.org/abs/quant-ph/9503016"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1c2c03ff-15cf-49eb-8ef6-3820420ef70d",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}