dorsal/arxiv
View SchemaThe simplified Toffoli gate implementation by Margolus is optimal
| Authors | Guang Song, Andreas Klappenecker |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0312225 |
| URL | https://arxiv.org/abs/quant-ph/0312225 |
Abstract
Unitary operations are expressed in the quantum circuit model as a finite sequence of elementary gates, such as controlled-not gates and single qubit gates. We prove that the simplified Toffoli gate by Margolus, which coincides with the Toffoli gate up to a single change of sign, cannot be realized with less than three controlled-not gates. If the circuit is implemented with three controlled-not gates, then at least four additional single qubit gates are necessary. This proves that the implementation suggested by Margolus is optimal.
{
"annotation_id": "c7a37bf1-d853-4f7e-826c-88cae5b94860",
"date_created": "2026-03-02T18:02:03.422000Z",
"date_modified": "2026-03-02T18:02:03.422000Z",
"file_hash": "b08993c51b0d9bfd5ec44232dba3b51d96191b1be502368eb44b364eafcaec5b",
"private": false,
"record": {
"abstract": "Unitary operations are expressed in the quantum circuit model as a finite\nsequence of elementary gates, such as controlled-not gates and single qubit\ngates. We prove that the simplified Toffoli gate by Margolus, which coincides\nwith the Toffoli gate up to a single change of sign, cannot be realized with\nless than three controlled-not gates. If the circuit is implemented with three\ncontrolled-not gates, then at least four additional single qubit gates are\nnecessary. This proves that the implementation suggested by Margolus is\noptimal.",
"arxiv_id": "quant-ph/0312225",
"authors": [
"Guang Song",
"Andreas Klappenecker"
],
"categories": [
"quant-ph"
],
"title": "The simplified Toffoli gate implementation by Margolus is optimal",
"url": "https://arxiv.org/abs/quant-ph/0312225"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5280822b-b9f6-4065-bff4-d1df88afc4f4",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}