dorsal/arxiv
View SchemaAn Arbitrary Two-qubit Computation In 23 Elementary Gates
| Authors | Stephen S. Bullock, Igor L. Markov |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0211002 |
| URL | https://arxiv.org/abs/quant-ph/0211002 |
| DOI | 10.1103/PhysRevA.68.012318 |
| Journal | Phys. Rev. A, 68(2003), no. 1, July 2003, 012318. |
Abstract
Quantum circuits currently constitute a dominant model for quantum computation. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worst-case upper bound of 23 elementary gates, of which at most 4 (CNOT) entail multi-qubit interactions. Our analysis shows that synthesis algorithms suggested in previous work, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm has a worst case of 61 gates of which 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis and operator theory. They are related to the canonical decomposition of a two-qubit gate with respect to the ``magic basis'' of phase-shifted Bell states, published previously. We further extend this decomposition in terms of elementary gates for quantum computation.
{
"annotation_id": "38c4150f-0b5d-427b-9ba2-0da01decbd5d",
"date_created": "2026-03-02T18:01:55.725000Z",
"date_modified": "2026-03-02T18:01:55.725000Z",
"file_hash": "0f8cec299501454c455b028e74205c1e65e85752132077bc3b8012fd08738312",
"private": false,
"record": {
"abstract": "Quantum circuits currently constitute a dominant model for quantum\ncomputation. Our work addresses the problem of constructing quantum circuits to\nimplement an arbitrary given quantum computation, in the special case of two\nqubits. We pursue circuits without ancilla qubits and as small a number of\nelementary quantum gates as possible. Our lower bound for worst-case optimal\ntwo-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2\nCNOTs. To this end, we constructively prove a worst-case upper bound of 23\nelementary gates, of which at most 4 (CNOT) entail multi-qubit interactions.\nOur analysis shows that synthesis algorithms suggested in previous work,\nalthough more general, entail much larger quantum circuits than ours in the\nspecial case of two qubits. One such algorithm has a worst case of 61 gates of\nwhich 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie\ntheory as well as the polar and spectral (symmetric Shur) matrix decompositions\nfrom numerical analysis and operator theory. They are related to the canonical\ndecomposition of a two-qubit gate with respect to the ``magic basis\u0027\u0027 of\nphase-shifted Bell states, published previously. We further extend this\ndecomposition in terms of elementary gates for quantum computation.",
"arxiv_id": "quant-ph/0211002",
"authors": [
"Stephen S. Bullock",
"Igor L. Markov"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevA.68.012318",
"journal_ref": "Phys. Rev. A, 68(2003), no. 1, July 2003, 012318.",
"title": "An Arbitrary Two-qubit Computation In 23 Elementary Gates",
"url": "https://arxiv.org/abs/quant-ph/0211002"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5cd9451a-2ac3-4076-a732-b7ea038ae77f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}