dorsal/arxiv
View SchemaArchitecture-Dependent Execution Time of Shor's Algorithm
| Authors | Rodney Van Meter, Kohei M. Itoh, Thaddeus D. Ladd |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0507023 |
| URL | https://arxiv.org/abs/quant-ph/0507023 |
| Journal | Proc. Mesoscopic Superconductivity + Spintronics 2006 |
Abstract
We show how the execution time of algorithms on quantum computers depends on the architecture of the quantum computer, the choice of algorithms (including subroutines such as arithmetic), and the ``clock speed'' of the quantum computer. The primary architectural features of interest are the ability to execute multiple gates concurrently, the number of application-level qubits available, and the interconnection network of qubits. We analyze Shor's algorithm for factoring large numbers in this context. Our results show that, if arbitrary interconnection of qubits is possible, a machine with an application-level clock speed of as low as one-third of a (possibly encoded) gate per second could factor a 576-bit number in under one month, potentially outperforming a large network of classical computers. For nearest-neighbor-only architectures, a clock speed of around twenty-seven gates per second is required.
{
"annotation_id": "776698d5-14aa-45a5-a30e-bf8234ce43ef",
"date_created": "2026-03-02T18:02:16.734000Z",
"date_modified": "2026-03-02T18:02:16.734000Z",
"file_hash": "f49923070e7fc7fe984523e96d5d31a1c330bab72c1d758682f171dc76385b7f",
"private": false,
"record": {
"abstract": "We show how the execution time of algorithms on quantum computers depends on\nthe architecture of the quantum computer, the choice of algorithms (including\nsubroutines such as arithmetic), and the ``clock speed\u0027\u0027 of the quantum\ncomputer. The primary architectural features of interest are the ability to\nexecute multiple gates concurrently, the number of application-level qubits\navailable, and the interconnection network of qubits. We analyze Shor\u0027s\nalgorithm for factoring large numbers in this context. Our results show that,\nif arbitrary interconnection of qubits is possible, a machine with an\napplication-level clock speed of as low as one-third of a (possibly encoded)\ngate per second could factor a 576-bit number in under one month, potentially\noutperforming a large network of classical computers. For nearest-neighbor-only\narchitectures, a clock speed of around twenty-seven gates per second is\nrequired.",
"arxiv_id": "quant-ph/0507023",
"authors": [
"Rodney Van Meter",
"Kohei M. Itoh",
"Thaddeus D. Ladd"
],
"categories": [
"quant-ph"
],
"journal_ref": "Proc. Mesoscopic Superconductivity + Spintronics 2006",
"title": "Architecture-Dependent Execution Time of Shor\u0027s Algorithm",
"url": "https://arxiv.org/abs/quant-ph/0507023"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "37a621fd-a83e-49d6-86f5-75643443d7d1",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}