dorsal/arxiv
View SchemaComputation at a distance
| Authors | Samuel A. Kutin, David Petrie Moulton, Lawren M. Smithline |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0701194 |
| URL | https://arxiv.org/abs/quant-ph/0701194 |
Abstract
We consider a model of computation motivated by possible limitations on quantum computers. We have a linear array of n wires, and we may perform operations only on pairs of adjacent wires. Our goal is to build a circuits that perform specified operations spanning all n wires. We show that the natural lower bound of n-1 on circuit depth is nearly tight for a variety of problems, and we prove linear upper bounds for additional problems. In particular, using only gates adding a wire (mod 2) into an adjacent wire, we can realize any linear operation in GL_n(2) as a circuit of depth 5n. We show that some linear operations require depth at least 2n+1.
{
"annotation_id": "0a4109c5-3c77-4297-9471-b37223a4c98d",
"date_created": "2026-03-02T18:02:34.534000Z",
"date_modified": "2026-03-02T18:02:34.534000Z",
"file_hash": "bd798baff5031b3e6ce99ada00b9a658bf54b11d367dd821d5eda0ac08c31775",
"private": false,
"record": {
"abstract": "We consider a model of computation motivated by possible limitations on\nquantum computers. We have a linear array of n wires, and we may perform\noperations only on pairs of adjacent wires. Our goal is to build a circuits\nthat perform specified operations spanning all n wires. We show that the\nnatural lower bound of n-1 on circuit depth is nearly tight for a variety of\nproblems, and we prove linear upper bounds for additional problems. In\nparticular, using only gates adding a wire (mod 2) into an adjacent wire, we\ncan realize any linear operation in GL_n(2) as a circuit of depth 5n. We show\nthat some linear operations require depth at least 2n+1.",
"arxiv_id": "quant-ph/0701194",
"authors": [
"Samuel A. Kutin",
"David Petrie Moulton",
"Lawren M. Smithline"
],
"categories": [
"quant-ph"
],
"title": "Computation at a distance",
"url": "https://arxiv.org/abs/quant-ph/0701194"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9d246e7f-9ab8-465a-a8e4-4953bb454c1b",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}