dorsal/arxiv
View SchemaPoly-locality in quantum computing
| Authors | Michael H. Freedman |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0001077 |
| URL | https://arxiv.org/abs/quant-ph/0001077 |
Abstract
A polynomial depth quantum circuit effects, by definition a poly-local unitary transformation of tensor product state space. It is a physically reasonable belief [Fy][L][FKW] that these are precisely the transformations which will be available from physics to help us solve computational problems. The poly-locality of discrete Fourier transform on cyclic groups is at the heart of Shor's factoring algorithm. We describe a class of poly-local transformations, including all the discrete orthogonal wavelet transforms in the hope that these may be helpful in constructing new quantum algorithms. We also observe that even a rather mild violation of poly-locality leads to a model without one-way functions, giving further evidence that poly-locality is an essential concept.
{
"annotation_id": "421ec5e7-6d82-4a74-a4ae-a878752140dc",
"date_created": "2026-03-02T18:01:35.858000Z",
"date_modified": "2026-03-02T18:01:35.858000Z",
"file_hash": "2ce027af253f267660e921fa398d7af70f941d044c7d2457577141d85dc8b0e5",
"private": false,
"record": {
"abstract": "A polynomial depth quantum circuit effects, by definition a poly-local\nunitary transformation of tensor product state space. It is a physically\nreasonable belief [Fy][L][FKW] that these are precisely the transformations\nwhich will be available from physics to help us solve computational problems.\nThe poly-locality of discrete Fourier transform on cyclic groups is at the\nheart of Shor\u0027s factoring algorithm. We describe a class of poly-local\ntransformations, including all the discrete orthogonal wavelet transforms in\nthe hope that these may be helpful in constructing new quantum algorithms. We\nalso observe that even a rather mild violation of poly-locality leads to a\nmodel without one-way functions, giving further evidence that poly-locality is\nan essential concept.",
"arxiv_id": "quant-ph/0001077",
"authors": [
"Michael H. Freedman"
],
"categories": [
"quant-ph",
"cs.NA"
],
"title": "Poly-locality in quantum computing",
"url": "https://arxiv.org/abs/quant-ph/0001077"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "31b256d9-d6e5-4f88-8121-4acdd93ce804",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}