dorsal/arxiv
View SchemaShor's algorithm on a nearest-neighbor machine
| Authors | Samuel A. Kutin |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0609001 |
| URL | https://arxiv.org/abs/quant-ph/0609001 |
Abstract
We give a new ``nested adds'' circuit for implementing Shor's algorithm in linear width and quadratic depth on a nearest-neighbor machine. Our circuit combines Draper's transform adder with approximation ideas of Zalka. The transform adder requires small controlled rotations. We also give another version, with slightly larger depth, using only reversible classical gates. We do not know which version will ultimately be cheaper to implement.
{
"annotation_id": "9e62b5b4-c412-4a48-ac62-1bb1075bd2e4",
"date_created": "2026-03-02T18:02:30.963000Z",
"date_modified": "2026-03-02T18:02:30.963000Z",
"file_hash": "ff535e142f3981bec3059de8ba66701b6bc1b507f50ae365437dee124e8a62ea",
"private": false,
"record": {
"abstract": "We give a new ``nested adds\u0027\u0027 circuit for implementing Shor\u0027s algorithm in\nlinear width and quadratic depth on a nearest-neighbor machine. Our circuit\ncombines Draper\u0027s transform adder with approximation ideas of Zalka. The\ntransform adder requires small controlled rotations. We also give another\nversion, with slightly larger depth, using only reversible classical gates. We\ndo not know which version will ultimately be cheaper to implement.",
"arxiv_id": "quant-ph/0609001",
"authors": [
"Samuel A. Kutin"
],
"categories": [
"quant-ph"
],
"title": "Shor\u0027s algorithm on a nearest-neighbor machine",
"url": "https://arxiv.org/abs/quant-ph/0609001"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "89560864-9fc7-4645-a93c-eb601d1fc86e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}