dorsal/arxiv
View SchemaImplementation of Shor's Algorithm on a Linear Nearest Neighbour Qubit Array
| Authors | Austin G. Fowler, Simon J. Devitt, Lloyd C. L. Hollenberg |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0402196 |
| URL | https://arxiv.org/abs/quant-ph/0402196 |
| Journal | Quant. Info. Comput. 4, 237-251 (2004) |
Abstract
Shor's algorithm, which given appropriate hardware can factorise an integer $N$ in a time polynomial in its binary length $L$, has arguable spurred the race to build a practical quantum computer. Several different quantum circuits implementing Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits within the computer can be interacted. While some quantum computer architectures possess this property, many promising proposals are best suited to realising a single line of qubits with nearest neighbour interactions only. In light of this, we present a circuit implementing Shor's factorisation algorithm designed for such a linear nearest neighbour architecture. Despite the interaction restrictions, the circuit requires just $2L+4$ qubits and to first order requires $8L^{4}$ gates arranged in a circuit of depth $32L^{3}$ -- identical to first order to that possible using an architecture that can interact arbitrary pairs of qubits.
{
"annotation_id": "63ff3bd9-49e4-4639-b8a3-7732e46f75ce",
"date_created": "2026-03-02T18:02:06.923000Z",
"date_modified": "2026-03-02T18:02:06.923000Z",
"file_hash": "83e9cf7cce44dcaaa7663d2259cd4419ceeac1f310e8de58add0bbe61d45e229",
"private": false,
"record": {
"abstract": "Shor\u0027s algorithm, which given appropriate hardware can factorise an integer\n$N$ in a time polynomial in its binary length $L$, has arguable spurred the\nrace to build a practical quantum computer. Several different quantum circuits\nimplementing Shor\u0027s algorithm have been designed, but each tacitly assumes that\narbitrary pairs of qubits within the computer can be interacted. While some\nquantum computer architectures possess this property, many promising proposals\nare best suited to realising a single line of qubits with nearest neighbour\ninteractions only. In light of this, we present a circuit implementing Shor\u0027s\nfactorisation algorithm designed for such a linear nearest neighbour\narchitecture. Despite the interaction restrictions, the circuit requires just\n$2L+4$ qubits and to first order requires $8L^{4}$ gates arranged in a circuit\nof depth $32L^{3}$ -- identical to first order to that possible using an\narchitecture that can interact arbitrary pairs of qubits.",
"arxiv_id": "quant-ph/0402196",
"authors": [
"Austin G. Fowler",
"Simon J. Devitt",
"Lloyd C. L. Hollenberg"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quant. Info. Comput. 4, 237-251 (2004)",
"title": "Implementation of Shor\u0027s Algorithm on a Linear Nearest Neighbour Qubit Array",
"url": "https://arxiv.org/abs/quant-ph/0402196"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8fedae5e-8661-45f8-b109-9985b4c27502",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}